HashMap、ConcurrentHashMap

HashMap

1、在jdk1.7之前是Entry数组+链表，在jdk1.8之后为Node数组+链表，

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}

如上，当链表长度大于7之后，将会通过treeifyBin方法将链表转化为红黑树(漫画：什么是红黑树？)。
2、初始容量capacity为16，初始负载因子loadFactor为0.75f，当size超过capacity*loadFactor后，capacity将会翻倍。
3、负载因子是空间与效率的一种平衡，负载因子越大，散列的装填程度高，因此索引效率低，负载因子越小，散列的装填越稀疏，空间浪费多，但是索引效率高。
4、在使用HashMap时尽量指定容量大小，避免扩容带来的性能损耗。例如要存1000个数据，1000/0.75 = 1333，1024<1333<2048，所以容量定为2048。
5、因为哈希算法是与size-1做&运算，2的幂次方-1的二进制结果是n个1，做&运算则结果种类越多，即分布越均匀。(知道为啥HashMap里面的数组size必须是2的次幂？)

ConcurrentHashMap

jdk1.7

1、采用Segment + HashEntry的方式进行实现，结构如下：

ConcurrentHashMap初始化时，计算出Segment数组的大小ssize和每个Segment中HashEntry数组的大小cap，并初始化Segment数组的第一个元素；其中ssize大小为2的幂次方，默认为16，cap大小也是2的幂次方，最小值为2，最终结果根据根据初始化容量initialCapacity进行计算，计算过程如下：

if (c * ssize < initialCapacity)
    ++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
    cap <<= 1;

其中Segment在实现上继承了ReentrantLock，这样就自带了锁的功能。
2、定位元素要进行两次哈希，第一次定位到Segment，第二次定位到数组里的某个位置。
3、size实现，Segment中元素累加。
先采用不加锁的方式，连续计算元素的个数，最多计算3次：
如果前后两次计算结果相同，则说明计算出来的元素个数是准确的；
如果前后两次计算结果都不同，则给每个Segment进行加锁，再计算一次元素的个数；

jdk1.8

1、在1.8中直接使用Node数组，并通过CAS和Synchronized保证并发安全，结构如下：

if (tab == null || (n = tab.length) == 0)
       tab = initTable();

如上putVal方法中的一段语句，在进行第一次put操作时才会调用initTable()进行初始化。
2、当链表长度超过7时，会调用treeifyBin方法将链表转化为红黑树。
3、size实现，使用一个volatile类型的变量baseCount记录元素的个数。

---

注：非原创