MAP哈希表( 二 )

在()中，我们看到在这个函数里面使用到了2次()方法， ()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & )是否为0 ，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
4.是怎么解决哈希冲突的？
什么是哈希冲突？当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做冲突（哈希碰撞）
hash()函数
相比于返回的int类型，初始的容量大小16要远小于int类型的范围如果使用取余，那么相当于参与运算的只有的低位，高位是没有起到任何作用的，所以我们的思路就是让取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，与自己右移16位进行异或运算（高低位异或）
链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的中存在大量数据时，加入我们某个下对应的链表有n个元素，那么遍历时间复杂度就为O(n) ，为了针对这个问题， JDK1.8在中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)
总结：
①使用链地址法（使用散列表）来链接拥有相同hash值的数据
②使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均
③引入红黑树进一步降低遍历的时间复杂度，使得遍历更快(O(N) -> O(logN))
5.能否使用任何类作为 Map 的 key？
可以使用任何类作为 Map 的 key ，然而在使用之前，需要考虑以下几点：
①如果类重写了 () 方法，也应该重写 () 方法
②类的所有实例需要遵循与 () 和 () 相关的规则
③如果一个类没有使用 () ，不应该在 () 中使用它
④用户自定义 Key 类最佳实践是使之为不可变的，这样 () 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 () 和 () 在未来不会改变，这样就会解决与可变相关的问题了
6.为什么中、这样的包装类适合作为K？
、等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
①都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
②内部已重写了()、()等方法，遵守了内部的规范，不容易出现Hash值计算错误的情况
7.如果使用作为的Key ，应该怎么办呢？
重写()和()方法
①重写()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞
②重写()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x ， x.(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性