HashMap 1.8和1.7 扩容图解
1.HashMap的数据结构：
在jdk1.8之后的改变主要目的是提高查找效率。
数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
在1.8之后entry数组变成了node节点数组，同样有key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。
JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
2.put方法:
①在key的hashCode相等，且key也相同的情况下，HashMap在执行put操作的时候，会进行覆盖操作，新值将覆盖旧值，所以最后输出为"{Aa=def}"。
②在key的hashCode相等，但key不相同（如"Aa"与"BB"）的情况下，HashMap在执行put操作的时候，就会进行链表式存储，并且采用的是头插法，即新值处于链表头，最开始的值处于链表尾。
2.扩容机制
扩容的原因：hashMap的默认大小是16，当容量达到负载因子0.75时，会触发扩容机制（transfer方法），原数组的2倍。
jdk1.7时扩容时会执行transfer()方法：
创建一个新的Entry空数组，长度是原数组的2倍.
遍历原Entry数组，重新reHash到新的数组中，因为长度改变，Hsah的规则也会改变。
使用头插法，从头部插入数据。
触发了扩容后 1.7 是先扩容后插入新值的，1.8 先插值再扩容
jdk1.8时扩容时会执行reSize()方法：
创建的不是Entry数组，而是一个Node节点数组
会使用尾插法，插入数据。
让我们回顾一下Hash公式：
index = HashCode（Key） & （Length - 1）
3.并发下的不安全性
两个线程同时执行了put()操作，并进入了transfer()环节，可能造成闭环，导致在get时会出现死循环。
4.与HashTable的比较：
Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map，Cloneable, Serializable接口。
在put方法上加上synchronized关键字。
数组+链表 的数据结构
5.HashMap与ConcurrentHashMap的比较
hashMap可以存（null，null），null的k允许存在一个。ConcurrentHashMap不允许k有null出现，否则回报控指针错误
6.HashMap为什么使用红黑树而不是AVL树
AVL树和红黑树有几点比较和区别：
（1）AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。
（2）红黑树更适合于插入修改密集型任务。
（3）通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。
总结：
（1）AVL以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作次数。
（2）两种实现都缩放为a O(lg N)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
（3）在AVL树中，从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中，差异可以是2倍。
（4）两个都给O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。
网友评论