链接： https://www.jianshu.com/p/a2c96f79a98d

HashMap

1.HashMap的结构

Entry数组，每一个节点都有一个Node，Node有next，即链表

                1.7 链表

                1.8 链表或者红黑树

2.HashMap的put操作

（1）判断key是否存在，存在，直接将value替换

（2）检查容量是否达到ThreadHold = size * 0.75，如果有，则扩容。

（3）扩容的时候，

                  Java1.7头插法；可能引起死循环

                 Java1.8尾插法，映射到一个桶上的节点如果小于8个，链表的形式，如果是大于8个，则直接转化成红黑树。可能因为覆盖，导致元素丢失。

ConcurrentHashMap

1.结构

          1.7：Segment[ ]数组，每一个数组用Lock方法加锁，执行更新与扩容

          1.8:   去掉了Segment数组，结构与HashMap一致

2.插入操作

          1.7：直接加锁，链表上添加

          1.8：

                    a. 当定位到的桶是null的时候，使用CAS插入，每一个节点都是volatile的；

                    b. 当已经有元素的时候，使用Synchronized(f), f是桶上的节点。然后判断用不用变成红黑树

红黑树和平衡二叉树的比较，插入的时候调整的旋转次数比平衡二叉树少

红黑树与平衡二叉树的查找性能相同。但是当插入节点和删除节点从而破坏树的平衡性时，红黑树需要做旋转调整的次数比平衡二叉树所需的旋转调整的次数要少的多，其查找，插入，删除的操作时间复杂度均为O(Log2n)。