- HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8
- 为什么HashMap的默认负载因子是0.75，而不是0.5或者是整数1呢？
- 为什么HashMap的默认大小为16？
- HashMap的put方法的具体流程？
- HashMap的扩容操作是怎么实现的？
- HashMap是使用了哪些方法来有效解决哈希冲突？
- 如果使用Object作为HashMap的Key，应该怎么办呢？
- HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
- HashMap 与 HashTable 有什么区别？
HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8
JDK1.7：Entry数组 + 链表
JDK1.8：Node 数组 + 链表/红⿊树，当链表上的元素个数超过 8 个并且数组⻓度 >= 64 时⾃动转化成红⿊树，节点变成树节点，以提⾼搜索效率和插⼊效率到 O(logN)。Entry 和 Node 都包含 key、value、hash、next 属性。
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制，他会保证容量(capacity)的值永远都是2的幂 为了保证负载因子x容量的结果是一个整数，这个值是0.75(4/3)比较合理，因为这个数和任何2的次幂乘积结果都是整数。
理论上来讲，负载因子越大，导致哈希冲突的概率也就越大，负载因子越小，费的空间也就越大,这是一个无法避免的利弊关系，所以通过一个简单的数学推理，可以测算出这个数值在0.75左右是比较合理的
调用put方法新增一个数据时会使用[table.length-1]*hash进行下标的计算，因为是将二进制进行按位于，(16-1) 是 1111,末位是1，这样也能保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。
那为什么不是8,4呢？ 因为是8或者4的话很容易导致map扩容影响性能，如果分配的太大的话又会浪费资源，所以就使用16作为初始大小。
当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
第一种就是数组下标下内容为空
这种情况没什么好说的，为空据直接占有这个slot槽位就好了，然后把当前.put方法传进来的key和value包装成一个node对象,放到这个slot中就好了。
第二种情况就是数组下标下内容不为空，但它引用的node还没有链化
这种情况下先要对比一下这个node对象的key与当前put对象的key是否完全.相等，如果完全相等的情况下，就行进行replace操作，把之前的槽位中node.下的value替换成新的value就可以了，否则的话这个put操作就是一个正儿.八经的hash冲突,这种情况在slot槽位后面追加一个node就可以了,用尾插法 ( 前面讲过，jdk7是把新增元素添加到头部节点，而jdk8则添加到尾部节点)。
第三种就是该数组下标下内容已经被链化了
这种情况和第二种情况处理很相似，首先也是迭代查找node，看看链表上中元素的key，与当前传过来的key是否完全一致，如果完全一致的话还是repleace操作，用put过来的新value替换掉之前node中的value，否则的话就是一致迭代到链表尾节点也没有匹配到完全一致的node，就和之前的一样，把put进来数据包装成node追加到链表的尾部，再检查一下当前链表的长度，有没有达到树化阈值，如果达到了阈值就调用一个树化方法，树化操作都是在这个方法里完成的。
第四种情况就是冲突很严重的情况下，这个链表已经转化成红黑树了
红黑树就比较复杂 要将清楚这个红黑树还得从TreeNode说起 TreeNode继承了Node结构，在Node基础上加了几个字段，分别是指向父节点parent字段，指向左子节点left字段，指向右子节点right字段，还有一个表示颜色的red字段，这就是TreeNode的基本结构，然后红黑树的插入操作，首先找到一个合适的插入点，就是找到插入节点的父节点，然后红黑树它又满足二叉树的所有特性，所以找这个父节点的操作和二叉树排序是完全一致的，然后说一下这个二叉树排序，其实就是二分查找算法映射出来的结构，就是一个倒立的二叉树，然后每个节点都可以有自己的子节点，本且左节点小于但前节点，右节点大于当前节点，然后每次向下查找一层就能那个排除掉一半的数据，查找效率非常的高效，当查找的过程中也是分情况的。
首先第一种情况就是一直向下探测，直到查询到左子树或者右子树位null，说明整个树中，并没有发现node链表中的key与当前put key一致的TreeNode,那此时探测节点就是插入父节点的所在了，然后就是判断插入节点的hash值和父节点的hash值大小决定插入到父节点的左子树还是右子树。当然插入会打破平衡，还需要一个红黑树的平衡算法保持平衡。
- 在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
- 每次扩展的时候，都是扩展2倍；
- 扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
当我们把 table[i] 位置的所有 Node 迁移到 newtab 中去的时候：这⾥⾯的 node 要么在 newtab 的 i 位置（不变），要么在 newtab 的 i + n 位置。也就是我们可以这样处理：把 table[i] 这个桶中的 node 拆分为两个链表 l1和 l2：如果 hash & n == 0，那么当前这个 node 被连接到 l1 链表；否则连接到 l2 链表。这样下来，当遍历完table[i] 处的所有 node 的时候，我们得到两个链表 l1 和 l2，这时我们令 newtab[i] = l1，newtab[i + n] = l2，这就完成了 table[i] 位置所有 node 的迁移（rehash），这也是 HashMap 中容量⼀定的是 2 的整数次幂带来的⽅便之处。
- 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
- 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
- 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
重写hashCode()和equals()方法。
重写hashCode()是因为需要计算存储数据的存储位置。
重写equals()方法是保证key在哈希表中的唯一性。
hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）-2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
那怎么解决呢？
HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；
线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
**初始容量大小和每次扩充容量大小的不同 **： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
