jdk7 
jdk 8 , 在链表长度大于8时 转为红黑树

 

数组 + 链表
数组里存放链表表头
使用链表解决哈希冲突

单链表头部插入的缺点， 扩容时 改变了链表元素的顺序 ，可能形成环
java8 使用 尾部插入 

key  hash  equals 

public HashMap(int initialCapacity, float loadFactor)

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

扩容 增加桶数 减少链表长度 提升性能 


int hash = (key == null) ? 0 : hash(key);

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}


static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
}
    
length must be a non-zero power of 2
数组容量为什么必须是2的n次幂
使用位运算代替取模
   

允许key为null, 放到数组下标为0的位置
Null keys always map to hash 0, thus index 0

putForNullKey(value);

addEntry(0, null, value, 0);

void addEntry(int hash, K key, V value, int bucketIndex) {
         //当元素个数达到临界值，进行扩容，两倍容量。
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        //创建新的元素
        createEntry(hash, key, value, bucketIndex);
}
 

void createEntry(int hash, K key, V value, int bucketIndex) {
        //单链表头插入 ，先将表头元素记录下来，再将新表头重新赋值。
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash,  key, value, e);
        size++;
}


被修改的次数(fial-fast机制)
modCount
if (modCount != expectedModCount)
                throw new ConcurrentModificationException();