[数据结构与算法]HashMap

1.7和1.8的区别

????????1.7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1.8

• 头插法? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 尾插法

• hash()->4次扰动? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??hash()->1次扰动??

• 先扩容再插入? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 先插入再扩容?

• 数组+链表? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?数组+链表/红黑树

2. 1.8HashMap插入原理

????????1. 搅动获得hash值；

????????2. 判断数组是否为空，为空进行扩容，看看是否指定容量;

????????3?. 不为空的，计算hash与（n-1）&hash计算存放在数组的下标index;

????????4. 1查看key是否存在，没有直接插入；

? ??????????2.查看key是否存在，有直接覆盖

? ? ? ? ? ? 3.没有看看是为红黑树：如果是红黑树（前链表长度>=8 数组长度>64)遍历插入

? ? ? ? ? ? 4.如果不是红黑树判断是否存在key。存在覆盖；不存在插入后还要看是否转换成红黑树

? ? ? ? ? ? 5. 如果不是树节点，插入链表中；然后判断链表长度是否大于8并且数组长度大于64，如果

满足链表转换为红黑树

具体看图（图片来自于网络）

????????????????

3.hashmap初始化

????????一般如果new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。

4.hashmap的扩容机制

????????当数组长度达到（最大程度*负载因子（0.75））的就会扩容数组。扩容大小为原数组的二倍。

????????扩容引子为什么为0.75：

• 负载因子过大，虽然空间利用率上去了，但是时间效率降低了（大量的hash冲突）。

• 负载因子太小，虽然时间效率提升了，但是空间利用率降低了

• 负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

hashmap扩容为什么是2倍：HashMap计算添加元素的位置时，使用的（hash运算）位运算，这是特别高效的运算；另外，HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！

4.hashmap为什么1.8采用红黑树

链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，红黑树拥有更高的查找性能

为什么不直接用红黑树：

因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。红黑树的空间复杂度比较大，只有节点足够多，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

为什么是大于8才扩容：

链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。

节点数大于8转为红黑树 节点数小于6转化为链表

红黑树特点

红黑树核心是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

1. 节点是红色或黑色。

2. 根节点是黑色。

3. 从每个叶子到根的所有路径上不能有两个连续的红色节点

4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树是平衡二叉树 平衡二叉树的特点：

1. 所有节点最多拥有两个子节点，即度不大于2；

2. 左子树的键值小于根的键值，右子树的键值大于根的键值；

3. 任何节点的两个子树的高度最大差为1。