hashmap算法复杂度为什么为O(1)_JAVA_编程开发_程序员俱乐部

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;