日歷

2008年11月

日

一

二

三

四

五

六

統計

隨筆 - 12
文章 - 1
評論 - 7
引用 - 0

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

一道小而精巧的筆試題——Set、equals、類型轉換……

題目：

public class SetSize {

public static void main(string[] args) {

Set<Short> set = new HashSet<Short>();

for(short i = 0; i < 10; i++) {

set.add(i);

set.remove(i - 1);

}

System.out.println(set.size());

}

上面代碼輸出結果為10，為什么？

題目乍一看很簡單，不就是一個HashSet么，但看完了題目又覺得困惑：對啊，怎么會是10？真難為自己還特意花了一些時間學習Java的Collection Framework，居然連這么小的一個題目都吃不透，汗顏啊……

看了半天，沒有思路，跳過去做其他題，待到收卷前10分鐘，不甘心，再回過頭來看這道題。發現一個值得懷疑的地方：Set<Short> set = ……
為什么要特意設定是Short？再看到下面的i - 1，馬上感覺到似乎和類型轉換有關。

目前可以肯定的是：
1. set存儲的元素是Short類型
2. 調用remove方法時，i - 1會自動轉型為int，也就是說，傳給remove方法的參數是一個int值

接下來呢？int值會被自動包裝成Integer還是Short？對Java的泛型和Auto-Boxing不是很了解，于是在這犯迷糊了，只好將目前的思路草草寫了幾筆，交卷……

作為一名后知后覺的Java愛好者，自然不能放過這么有意思的題目。如是回來之后，上機親自試驗，輸入試題程序，出來的結果果然是10（嗯，沒騙我……）。然后驗證自己的猜測：將Set<Short>改為Set<Integer>，輸出結果……1！

看來我還是有一定的嗅覺的……

接下來就是探索原因了

首先驗證一下i - 1得到的結果會不會有錯：-1，0，1，……8。嗯，是對的

然后驗證一下每次remove之后有沒有真的remove掉指定的值……發現沒有。

苦思……

經一位精研C++的同學提醒：是不是因為存的是short，但刪的是int，所以不能刪？

試驗一下：

short temp = 1;

Short s = new Short(temp); //不能是new Short(1)，否則編譯出錯

Integer i = new Integer(1);

System.out.println(s.equals(i));

輸出結果……false！看來終于找到真正的原因了。

查看一下Short.equals()方法的源代碼：

public boolean equals(Object obj) {

if (obj instanceof Short) {

return value == ((Short)obj).shortValue();

}

return false;

}

ft……居然不是同一類型的就無視……這跟胸懷廣闊的集合框架背道而馳啊……當然，這是我的錯

目前可以大致推斷：因為set中存入的是值為0～9的Short型對象，而每次刪除是是要求刪除值為－1～8的Integer型對象，但值相同的Short與Integer看來并不“相等”，所以無法刪除。

那就看一下HashSet的remove方法究竟干了些什么

public boolean remove(Object o) {

return map.remove(o)==PRESENT;

}

public V remove(Object key) {

Entry<K,V> e = removeEntryForKey(key);

return (e == null ? null : e.value);

}

終于到主菜了……

/**

* Removes and returns the entry associated with the specified key

* in the HashMap. Returns null if the HashMap contains no mapping

* for this key.

final Entry<K,V> removeEntryForKey(Object key) {

int hash = (key == null) ? 0 : hash(key.hashCode());

int i = indexFor(hash, table.length);

Entry<K,V> prev = table[i];

Entry<K,V> e = prev;

while (e != null) {

Entry<K,V> next = e.next;

Object k;

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k)))) {

modCount++;

size--;

if (prev == e)

table[i] = next;

else

prev.next = next;

e.recordRemoval(this);

return e;

}

prev = e;

e = next;

}

return e;

}

代碼就不用解釋了，大家都看得懂。

HashSet里面刪除一個元素時，首先要根據傳進來對象的hash值從hash table中找到對應的“Entry”，當然，難免會有碰撞的情況，這時需要遍歷一下來找到真正需要刪除的對象。一直到這一步，Short和Integer的差異還沒有體現出來，因為它們返回的hash值是相同的，但當執行key.equals(k)的時候，就“不相等”了，因此找不到要刪除的元素，刪除失敗

小小的一道題，囊括了Java方方面面的細節，果然語言這個東西博大精深啊，有時候你以為自己很明白了，但隨便揪出一個細節來就足以打到你……

大家還是好好學習，天天向上吧

posted on 2008-11-02 19:52 This is Wing 閱讀(645) 評論(3) 編輯收藏所屬分類: Java基礎

評論:

# re: 一道小而精巧的筆試題——Set、equals、類型轉換…… sclsch Posted @ 2008-11-04 09:23
講得不錯啊。學習了。回復更多評論
# re: 一道小而精巧的筆試題——Set、equals、類型轉換…… sclsch Posted @ 2008-11-04 09:47
請講講
removeEntryForKey
這段代碼吧，
我是新手，看不懂。回復更多評論
# re: 一道小而精巧的筆試題——Set、equals、類型轉換…… This is Wing Posted @ 2008-11-04 16:02
@sclsch
其實我建議你先去回顧一下數據結構中的哈希表，比如怎么存儲，怎么解決碰撞，怎么查找……這些都是很基礎的東西，很多地方都要用到。相信當你搞懂哈希表之后，自然也就知道上面的代碼是在做什么了回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 垃圾回收（轉載）一道小而精巧的筆試題——Set、equals、類型轉換…… 對象的序列化和反序列化（轉載＋原創） java線程基本知識小結靜態Proxy與動態Proxy用法淺析 The Collections Framework (摘要）- Part 4 The Collections Framework (摘要）- Part 3 The Collections Framework (摘要）- Part 2 The Collections Framework (摘要）- Part 1


Copyright © This is Wing	Powered by: 博客園模板提供：滬江博客

導航

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜