Hashmap
JDK1.7中
使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表；
在hash函数特别差的情况下，比如说所有key的hashcode都相同，这个链表可能会很长，那么put/get操作都可能需要遍历这个链表，也就是最差情况下时间复杂度为O（n）。
JDK1.8中
使用一个Node数组来存储数据，但是这个Node可能是链表结构，也可能是红黑树结构；如果插入的元素key的hashcode值相同，那么这些key也会被定位到Node数组的同一个格子里，如果不超过8个使用链表存储，超过8个，会调用treeifyBin函数，将链表转换为红黑树。那么即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O（logn）的开销。
红黑树：
每个节点不是红的就是黑的；
根节点是黑的；
叶节点都是黑色，叶子节点指的是为空的节点；
如果一个节点是红色的，那么子节点必须为黑色；
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
ConcurrentHashMap
JDK1.7中
使用segment+hashentry来实现。ConcurrentHashMap在初始化时，计算出segement数组的大小ssize和每个segment中HashEntry数组的大小cap，并初始化segement数组的第一个元素，其中ssize大小为2的幂次方，默认为16，cap大小也是2的幂次方，最小值为2。segement在实现上继承了ReetrantLock，这样就自带了锁的功能。
put实现：当执行put方法插入数据的时候，先通过hash值在segment中找到对应的位置，然后如果相应位置的segment还未初始化，则通过CAS进行赋值，接着执行segment对象的put方法通过加锁机制插入数据。
size实现：因为concurrenthashmap是可以并发插入数据的，所以准确计算元素时有一定的难度，所以是先采用不加锁的方式，连续计算元素的个数，最多计算3次，如果前后两次计算结果相同，那么说明元素个数是准确的；如果前后两次计算结果都不相同，则给每个segment加锁，再计算一次元素的个数。
JDK1.8中
放弃了segment的设计，取而代之的是Node+CAS+Synchronized来保证并发安全。只有在执行第一次put方法时，才会调用initTable（）初始化Node数组。
put实现：
如果Node还未初始化，那么通过CAS插入相应的数据；
如果Node不为空，且当前该节点不处于移动状态，那么对该节点加synchronized锁，如果该节点hash不小于0，则遍历链表更新节点或者插入新节点；
如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；
如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；
如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；
size实现：1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount。因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数。
PS.两者在1.8之前都是头插，1.8之后都是尾插。
网友评论