Java HashMap 行为不符合 O(1) 标记

Question

当我运行这个程序时

public class MyHashMapOperationsDebug {

    public static void main(String[] args) {
        MyHashMap hashMap = new MyHashMap();//MyHashMap is replica of HashMap
        for (int i=1;i<=11;i++)
        hashMap.put(i, i+100);
        }
}

和MyHashMap.java有

void addEntry(int hash, K key, V value, int bucketIndex) {  //replica of HashMap's addEntry method  

Entry<K,V> e = table[bucketIndex];
**System.out.println("bucketIndex : " + bucketIndex);**
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

输出:

bucketIndex : 7  
bucketIndex : 14  
bucketIndex : 4  
bucketIndex : 13  
bucketIndex : 1  
bucketIndex : 8  
bucketIndex : 2  
bucketIndex : 11  
bucketIndex : 11  
bucketIndex : 2  
bucketIndex : 8  

即使只有 11 个键存储在大小为 16 的映射中，为什么有些键会进入同一个存储桶？例如。索引为 2 和 11 的桶各有两个键

编辑:阅读下面的输入后 一个问题:在上述情况下，使用 Java 的 HashMap 和 Integer 的复杂性是什么？是 O(1) 吗？

Answer 1

因为如果事先不知道所有 key ，就不可能设计出一种算法来保证它们均匀分布。即使事先知道所有键，如果其中两个具有相同的 hashCode，它们也将始终在同一个桶中。

这并不意味着 HashMap 不是 O(1)。即使假设每个桶都有 2 个条目，无论映射中的条目数如何，这仍然会使每个 get 操作及时执行，这不依赖于映射中的条目数，这是 O(1 ).