Java Hash Map containsValue的时间复杂度是多少呢

Question

这是它的源码： public boolean containsValue(Object value) {         Node<K,V>[] tab; V v;         if ((tab = table) != null && size > 0) {             for (int i = 0; i < tab.length; ++i) {                 for (Node<K,V> e = tab[i]; e != null; e = e.next) {                     if ((v = e.value) == value ||                         (value != null && value.equals(v)))                         return true;                 }             }         }         return false;     }是在遍历数组里先得到头节点，然后再遍历链表得到value，，时间复杂度是O(n)还是O(n²)

Answer 1

介于O(n)和O(n²)之间，更接近于O(n)，取决于key的hash重合度，如果所有的value都分布于单独的key，则复杂度就是O(n)。