Java HashMap 復雜度的問題

containsKey的復雜度是O(1)，它是直接根據給定的參數key來計算hashcode，看看相關位置上是否有。如果相關位置已被占用，就繼續尋找下壹個位置。下面是JDK實現containsKey的主要代碼：

int hash = hash(k);

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

Entry e = table[i];

while (e != null) {

if (e.hash == hash && eq(k, e.key))

return true;

e = e.next;

}

containsValue的復雜度是O(n)，對於hashmap，value是依賴於key的，所以只能遍歷整個集合。以下是JDK實現的主要代碼：

Entry[] tab = table;

for (int i = 0; i < tab.length ; i++)

for (Entry e = tab[i] ; e != null ; e = e.next)

if (value.equals(e.value))

return true;

return false;