Java HashMap behavior is not up to O(1) mark

Question

When I run this program

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);
        }
}

and MyHashMap.java has

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);
}

OUTPUT:

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

Why some keys go to same bucket, even when only 11 keys are stored in map of size 16? E.g. bucket at index 2, and 11 has two keys each

EDIT: After Reading inputs below One question : What will be the complexity in above case where HashMap & Integer of Java is used. Is it O(1) ?

Answer 1

Because it's impossible, without knowing all the keys in advance, to design an algorithm that will guarantee that they will be evenly distributed. And even when knowing all the keys in advance, if two of them have the same hashCode, they will always be in the same bucket.

That doesn't mean the HashMap isn't O(1). Even assuming that every bucket has 2 entries, regardless of the number of entries in the map, that still makes every get operation execute in time that doesn't depend on the number of entries in the map, which is the definition of O(1).