HashMap

结构：数组+链表+红黑树 （链表元素>8时变为红黑树）
如何解决哈希冲突：链地址法
哈希算法：与运算

static int indexFor(int h, int length) {   // h = key.hashcode();
       return h & (length-1);  
   }  

实现原理
Entry数组，每个Entry包含一个key-value对

// 数组长度是2的次方
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 包含参数：key, value, hash, next

参数
default initial capacity: 16
default load factor：0.75

源码知识点
构造方法没有为数组分配内存空间，put方法中分配
数组长度一定为2的次幂

public V put(K key, V value) {
        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold); //为主干数组分配存储空间
        }
       //如果key为null，存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
        int i = indexFor(hash, table.length);//获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
        addEntry(hash, key, value, i);//新增一个entry
        return null;
    }

get方法

1. h = hash(key.hashcode())
2. indexFor(h) 找到对应位置
3. 遍历链表用equals()找到结果

size超过阈值后数组扩容
元素个数 > 数组长度 * load factor
新建一个长度为原来2倍的数组，重新计算元素的位置，将原数组拷贝过来

为什么数组长度一定是2的整数倍
1.使用&计算比%速度快 h & (length - 1)
2.为保证散列值的均匀性，减少碰撞：length-1是奇数，二进制末位是1，计算结果有奇数有偶数。如果是偶数，计算结果全部为偶数。

其他
允许key为null，存在table[0]

HashTable/SynchronizedHashTable
key不允许为null
线程安全，put get 都用synchronized，效率低

ConcurrentHashMap
线程安全
jdk1.8以前：Segment分段锁+HashEntry，Segment extends ReentrantLock
jdk1.8用CAS+synchronized+Node，锁的颗粒度更小

Node: 
key
volatile value  确保可见性，读不需要加锁
hash
volatile next

put方法：
1.8以前：给一个segment加锁后操作
1.8以后：直接定位到桶，1. 桶为空：直接加 2. 数组正在扩容：帮助数组扩容 3. 加syncronized进行操作

扩容
· 扩容前在操作过的桶上标记-1，其他线程跳过。
· 头插改为尾插
· 在扩容的时候每个线程都有处理的步长，最少为16，在这个步长范围内的数组节点只有自己一个线程来处理

image.png

参考1