HashMap(二)
为什么在JDK8中HashMap要转成红黑树
为什么不继续使用链表
我们知道，HashMap解决hash冲突是通过拉链法完成的，在JDK8之前，如果产生冲突，就会把新增的元素增加到当前桶所在的链表中。 这样就会产生一个问题，当某个bucket冲突过多的时候，其指向的链表就会变得很长，这样如果put或者get该bucket上的元素时，复杂度就无限接近于O(N)，这样显然是不可以接受的。 所以在JDK1.7的时候，在元素put之前做hash的时候，就会充分利用扰动函数，将不同KEY的hash尽可能的分散开。不过这样做起来效果还不是太好，所以当链表过长的时候，我们就要对其数据结构进行修改。
为什么是红黑树
红黑树是一种自平衡的二叉查找树，相比于普通的二叉查找树和二叉平衡树，红黑树具有以下优势：
- 自平衡性：红黑树通过对节点进行颜色标记和旋转操作来保持树的平衡，使得树的高度保持在O(log n)的水平。而普通的二叉查找树和二叉平衡树在插入和删除操作后可能会导致树的不平衡，从而使得查找操作的性能下降。
- 插入和删除操作的效率更高：红黑树通过旋转操作来保持树的平衡，而不需要像二叉平衡树那样频繁地进行节点的调整。相比于二叉平衡树，红黑树的插入和删除操作的时间复杂度更低。
- 内存占用更小：红黑树相比于二叉平衡树，需要额外存储每个节点的颜色信息，但相对于普通的二叉查找树，红黑树的内存占用也是可接受的。
综上所述，红黑树在保持二叉查找树的查找性能的同时，通过自平衡的特性提高了插入和删除操作的效率。因此，在需要平衡性能和空间消耗的场景下，选择红黑树作为数据结构是合理的选择。
HashMap的hash方法
hash方法的功能是根据Key来定位这个K-V在链表数组中的位置的。也就是hash方法的输入应该是个Object类型的Key，输出应该是个int类型的数组下标。
最简单的话，我们只要调用Object对象的hashCode()方法，该方法会返回一个整数，然后用这个数对HashMap或者HashTable的容量进行取模就行了。只不过，在具体实现上，考虑到效率等问题，HashMap的实现会稍微复杂一点。他的具体实现主要由两个方法int hash(Object k)和int indexFor(int h, int length)来实现的（JDK 1.8中不再单独有indexFor方法，但是在计算具体的table index时也用到了一样的算法逻辑，具体代码可以看putVal方法）。
hash ：该方法主要是将Object转换成一个整型。 indexFor ：该方法主要是将hash生成的整型转换成链表数组中的下标。
- 使用位运算(&)来代替取模运算(%)，因为位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
- 对hashcode进行扰动计算，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。
HashMap的put方法
- 首先，put方法会计算键的哈希值(通过调用hash方法)，并通过哈希值计算出在数组中的索引位置。
- 如果该位置上的元素为空，那么直接将键值对存储在该位置上。
- 如果该位置上的元素不为空，那么遍历该位置上的元素，如果找到了与当前键相等的键值对，那么将该键值对的值更新为当前值，并返回旧值。
- 如果该位置上的元素不为空，但没有与当前键相等的键值对，那么将键值对插入到链表或红黑树中（如果该位置上的元素数量超过了一个阈值，就会将链表转化为红黑树来提高效率）。
- 如果插入成功，返回null；如果插入失败，返回被替换的值。
- 插入成功后，如果需要扩容，那么就进行一次扩容操作。
HashMap的get方法
- 首先，需要计算键的哈希值，并通过哈希值计算出在数组中的索引位置。
- 如果该位置上的元素为空，说明没有找到对应的键值对，直接返回null。
- 如果该位置上的元素不为空，遍历该位置上的元素，如果找到了与当前键相等的键值对，那么返回该键值对的值。
- 如果该位置上的元素不为空，但没有与当前键相等的键值对，那么就需要在链表或红黑树中继续查找。
- 遍历链表或红黑树，查找与当前键相等的键值对，找到则返回该键值对的值，否则返回null。
HashMap的remove方法
- 首先，remove方法会计算键的哈希值，并通过哈希值计算出在数组中的索引位置。
- 如果该位置上的元素为空，说明没有找到对应的键值对，直接返回null。
- 如果该位置上的元素不为空，检查是否与当前键相等，如果相等，那么将该键值对删除，并返回该键值对的值。
- 如果该位置上的元素不为空，但也与当前键不相等，那么就需要在链表或红黑树中继续查找。
- 遍历链表或者红黑树，查找与当前键相等的键值对，找到则将该键值对删除，并返回该键值对的值，否则返回null。