浅谈hashmap

        学习了java这么久没有看过hashmap源码，近期才来了解hashmap的底层结构，虽然网上有很多关于hashmap的文章但是我还是想学习总结一下。

        在jdk1.8之前hashmap是数组+链表的形式，jdk1.8变成了数组+链表+红黑树的结构，核心都是为了提高查询速度，现在聊下hashmap的数据结构基于jdk1.8。

基础结构图 node类

node对象属性

hash：key的哈希值

key：节点的key，类型和定义HashMap时的key相同

value：节点的value，类型和定义HashMap时的value相同

next：该节点的下一节点

        当它第一次put时候，它才会进行初始化扩容默认大小capacity是16第二次是32第三次是64就算设置初始化20，大小也是32，每次扩容都是2的幂，之所以每次扩容都为2的幂是为了符合Hash算法均匀分布的原则，防止取模运算后有些index结果的出现几率会更大，而有些index结果永远不会出现，为了index分布的更加均匀，所以采取2的幂。可以参考hashmap

        每次进行put时，他会计算key的hash值，然后通过位运算进行取模(n -1) & hash，然后求出放置到数组的i位置，如果tab[i]为空，将node放置到这个位置，同时node.next为null，如果tab[i]不为空将会进行判断这个key值是否相等(毕竟hashcode肯定是相同)，如果key值相等将会替换掉这个node，如果key值不相等将会在这个node插入在链表的末端连着上个的next，同时新的node的next为null。

       而且hashmap还有个负载因子loadFactor（默认0.75）、capacity容量大小（默认16）和threshold（loadFactor * capacity），这个负载因子主要是用来衡量HashMap满的程度，它主要是设置一个界限，当map的容量除以capacity总容量大小>=loadFactor，其实就是map当前容量大于threshold将会进行扩容。

put方法

        如果当链表的节点的长度大于TREEIFY_THRESHOLD（默认是8）的时候将会转成红黑树，但是如果tab长度小于MIN_TREEIFY_CAPACITY（默认值是64），它不会转红黑树而是将进行扩容再次散列（(n -1) & hash取模，因为扩容后长度变动，重新散列后node下标会变动达到防止链表过长的目的）避免链表过长。

链表转红黑树

        因为hashmap是非线程安全的，如果多线程操作hashmap扩容时可能会发生死锁的问题，假设我们有两个线程A、B，hashmap容量为2，A线程放入key T1、T2、T3、T4、T5，同时T1、T2和T3的hash值相同，形成一个链表T1->T2->T3,而T4、T5hash值不相同，于是这时候容量不足，需要进行扩容（rehash），于是新建一个更大容量的hash表，将数据从老的hash表中进行迁移，这时候B线程进来了，A线程挂起，这时候B线程发现容量不足也需要扩容，这时候线程B扩容的之后的链表为T1->T2,然后B线程执行完了，A线程继续执行，将链表变成了T2->T1,这时候形成了T1.next=T2，T2.next=T1,所以当用户对这个key进行取值的时候将会陷入死循环卡在那没有反应。

        如果需要多线程操作hashmap可以使用ConcurrenHashmap进行替代，ConcurrenHashmap是一个线程安全的hashtable，这时候就有人问为什么不直接使用hashtable，虽然hashtable也是线程安全的但是hashtable锁定的是一整个hash表，效率较为低下，而ConcurrenHashmap可以做到读取数据不进行加锁实现段锁，因为其内部结构有个Segment的存在，使其进行写操作的时候可以将锁的粒度保持尽量小。