HashMap的实现方式？

基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。

JDK7中HashMap采用的是位桶+链表的方式，我们常说的散列链表的方式，

而JDK8中采用的是位桶+链表/红黑树的方式，也是非线程安全的。

当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。

JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，

会被调整成一颗红黑树。这就是JDK7与JDK8中HashMap实现的最大区别。

HashMap的扩容策略

void transfer(Entry[] newTable) {    
    Entry[] src = table;                   //src引用了旧的Entry数组    
    int newCapacity = newTable.length;    
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组    
        Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素    
        if (e != null) {    
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）    
            do {    
                Entry<K, V> next = e.next;    
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置    
                e.next = newTable[i]; //标记[1]    
                newTable[i] = e;      //将元素放在数组上    
                e = next;             //访问下一个Entry链上的元素    
            } while (e != null);    
        }    
    }    
}  

对于扩容操作，底层实现都需要新生成一个数组，

然后拷贝旧数组里面的每一个Node链表到新数组里面，

这个方法在单线程下执行是没有任何问题的，但是在多线程下面却有很大问题，

主要的问题在于基于头插法的数据迁移，会有几率造成链表倒置，从而引发链表闭链，

导致程序死循环，并吃满CPU。

JDK7的ConcurrentHashMap扩容

在JDK7的时候，这种安全策略采用的是分段锁的机制，

ConcurrentHashMap维护了一个Segment数组，

Segment这个类继承了重入锁ReentrantLock，并且该类里面维护了一个 HashEntry<K,V>[] table数组，在写操作put，remove，扩容的时候，会对Segment加锁，所以仅仅影响这个Segment，不同的Segment还是可以并发的，所以解决了线程的安全问题，同时又采用了分段锁也提升了并发的效率

JDK8的ConcurrentHashMap扩容 

在JDK8中彻底抛弃了JDK7的分段锁的机制，新的版本主要使用了Unsafe类的CAS自旋赋值+synchronized同步+LockSupport阻塞等手段实现的高效并发，代码可读性稍差。 

ConcurrentHashMap的JDK8与JDK7版本的并发实现相比，

最大的区别在于JDK8的锁粒度更细，理想情况下talbe数组元素的大小就是其支持并发的最大个数，在JDK7里面最大并发个数就是Segment的个数，默认值是16，

可以通过构造函数改变一经创建不可更改，这个值就是并发的粒度，每一个segment下面管理一个table数组，加锁的时候其实锁住的是整个segment，

这样设计的好处在于数组的扩容是不会影响其他的segment的，

简化了并发设计，不足之处在于并发的粒度稍粗，

所以在JDK8里面，去掉了分段锁，将锁的级别控制在了更细粒度的table元素级别，

也就是说只需要锁住这个链表的head节点，并不会影响其他的table元素的读写，

好处在于并发的粒度更细，影响更小，从而并发效率更好，但不足之处在于并发扩容的时候，

由于操作的table都是同一个，

不像JDK7中分段控制，所以这里需要等扩容完之后，所有的读写操作才能进行，

HashMap如果初始时 传入容量为10，那么初始容量应该为多少呢？

HashMap默认初始容量：16 (即2<<3)

别问为什么，太大浪费内存，太小频繁扩容，16是一个在性能和资源之间相对折中的选择；

我们可以在new HashMap时显式指定容量大小

HashMap<String, Object> map = new HashMap<>(10);

你指定容量大小后，实际初始容量大小并不是你指定的容量大小，

因为HashMap的发明者认为实际需要的容量大小往往大于你在new HashMap时预估的大小，所以HashMap底层会对你指定的大小进行处理，处理后的大小才是实际容量大小；

底层容量处理

Hash会选择大于该数字的第一个2的幂作为容量

比如

new HashMap<>(3)，那么实际初始容量大小为4；
new HashMap<>(5)，那么实际初始容量大小为8；
new HashMap<>(7)，那么实际初始容量大小为8；
new HashMap<>(10)，那么实际初始容量大小为16；
new HashMap<>(13)，那么实际初始容量大小为32；