HashMap的put方法的具体流程？
putVal方法执行流程图
①.判断数组table是否为空或length=0，是的话就执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中 执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value 即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
HashMap的扩容操作是怎么实现的？
JDK1.7扩容机制
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时（即HashMap.Size > Capacity * LoadFactor ，LoadFactor 是负载因子）就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。HashMap的默认初始容量为16，负载因子0.75；当我们通过HashMap的有参构造自定义一个初始容量时，给定的值必须是2的幂次方值；
根据加载因子规则，当 时，hashMap会进行一次扩容操作；一次扩容流程可划分为两个步骤：
resize ： 创建一个新的Entry空数组，长度是原数组的2倍
transfer：旧数组中元素往新数组中迁移
HashMap中扩容是调用resize()方法
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果当前的数组长度已经达到最大值，则不在进行调整 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //根据传入参数的长度定义新的数组 Entry[] newTable = new Entry[newCapacity]; //按照新的规则，将旧数组中的元素转移到新数组中 transfer(newTable); table = newTable; //更新临界值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
代码中可以看到，如果原有table长度已经达到了上限，就不再扩容了。没有达到就以原来数组的两倍进行扩容
transfer方法的作用是把原table的Node放到新的table中，jdk1.7使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致环状节点。
//旧数组中元素往新数组中迁移 void transfer(Entry[] newTable) { //旧数组 Entry[] src = table; //新数组长度 int newCapacity = newTable.length; //遍历旧数组 for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置 e.next = newTable[i];//实现链表结构，新加入的放在链头，之前的的数据放在链尾 newTable[i] = e; e = next; } while (e != null); } } }
其中的while循环描述了头插法的过程
JDK1.8扩容
HashMap触发扩容条件
hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容
在 JDK 1.8 中，当某个桶中的链表长度大于等于 8 时，会判断当前的 HashMap 的容量是否大于等于 64。如果小于 64，则会进行 2 倍扩容；如果大于等于 64，则将链表转换为红黑树，以提高查询效率。
jdk1.8的HashMap求桶的位置
HashMap求桶的位置一共分为三个过程
- 求key的hashcode
- 调用hash函数得到hash值，将hashcode的高16位和低16位进行异或操作。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
- 通过(length- 1) & hash ，将hash值与length-1进行与操作，求桶的位置（其中hash值是上面hash函数得到的值，length是table数组的长度）
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
注意：不是得到hash值就知道把元素存在数组中的哪个位置，而是还要经过(length- 1) & hash之后才可以得到数组的位置，这样是为了减少hash冲突
无论是JDK7还是JDK8，HashMap的扩容都是每次扩容为原来的两倍，即会产生一个新的数组newtable，JDK1.8和1.7的扩容其实差不多，只是把原来数组中的元素全部放到新的只不过元素求桶的位置的方法不太一样。
在JDK7中就是按照上述写的三个步骤重新对元素求桶的位置，但是第三步与的值是新的数组的长度-1，也就是newCap-1。
if (e.next == null) newTab[e.hash & (newCap - 1)] = e;//插入新值
但是JDK8中就不是和newCap，而是直接与oldCap，也就是将hash值与旧数组的长度（oldCap）进行与操作。
if ((e.hash & oldCap) == 0) { newTab[j] = loHead; }else{ newTab[j + oldCap] = hiHead; }
如果与oldCap与的结果是0，那么就代表当前元素的桶位置不变。
如果结果为1，那么桶的位置就是原位置+原数组长度（oldCap）
骚戴理解：需要注意的是，虽然 JDK 8 中重新计算元素在新数组中的位置时，与旧数组的长度进行与操作的方式不同于 JDK 7 中的取模运算，但它们的本质是相同的，都是为了保证元素在新数组中的位置能够均匀地分布，避免哈希冲突。
为什么HashMap的负载因子为0.75呢？
负载因子是一个比例值，表示 HashMap 中元素的数量与容量的比值。负载因子越大，填充因子越小，就越能减少空间浪费，但是会增加哈希冲突的概率。负载因子越小，填充因子越大，就越能减少哈希冲突的概率，但是会增加空间浪费。
在 JDK 1.8 中，HashMap 的默认负载因子为 0.75。这个值是经过实验和优化得出的。当负载因子为 0.75 时，HashMap 的空间利用率比较高，同时哈希冲突的概率也比较低，可以达到较好的性能表现。如果负载因子设置得太小，会导致 HashMap 频繁地进行扩容操作，降低性能；如果负载因子设置得太大，会导致哈希冲突的概率增加，也会降低性能。
需要注意的是，在实际应用中，负载因子的选择应该根据具体情况来确定。如果应用中哈希冲突较少，可以适当提高负载因子，以减少空间浪费；如果哈希冲突较多，可以适当降低负载因子，以提高性能。
HashMap是怎么解决哈希冲突的？
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的
使用链地址法（使用散列表）来链接拥有相同hash值的数据；
使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：
根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。
数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，但插入和删除容易；
所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下， 但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表（就是一直发生冲突，然后就最后成为了一条单链表），所以我们还需要对hashCode作一定的优化
hash()函数
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值 出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：
static final int hashCode(Object key){ int h; //与自己右移16位进行异或运算（高低位异或） return (key==null)? 0 : (h==key.hashCode()) ^ (h>>>16)// }
这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；
JDK1.8新增红黑树
通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希 碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的
- 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
- 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
- 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
通常hash冲突的四种解决方法
链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
开放定址法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到空的哈希地址。
再哈希法：即发生冲突时，由其他的函数再计算一次哈希值。
建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。
能否使用任何类作为 Map 的 key？
在 Java 中，可以使用任何类作为 Map 的 key，只要该类正确地实现了 `hashCode()` 和 `equals()` 方法。`hashCode()` 方法用于计算对象的哈希码，`equals()` 方法用于判断两个对象是否相等。
在使用自定义类作为 Map 的 key 时，需要确保该类正确地实现了 `hashCode()` 和 `equals()` 方法。如果没有正确实现这两个方法，可能会导致 HashMap 中的元素无法正确地存储和检索，甚至会导致 HashMap 出现死循环等问题。
在实现 `hashCode()` 和 `equals()` 方法时，需要遵循以下原则：
- 如果两个对象相等，它们的哈希码必须相等。
- 如果两个对象的哈希码相等，它们不一定相等。
- `equals()` 方法必须满足自反性、对称性、传递性和一致性。
需要注意的是，如果使用可变对象作为 Map 的 key，那么在该对象发生变化时，它的哈希码也会发生变化。这可能会导致该对象无法正确地从 HashMap 中检索出来。因此，通常建议使用不可变对象作为 Map 的 key。
为什么HashMap中String、Integer这样的包装类适合作为Key？
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
1、都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
2、内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况；
如果使用自定义对象作为HashMap的Key，应该怎么办呢？
必须同时重写hashCode()和equals()方法，同时重写这两个方法是为了保证使用自定义对象作为HashMap的key时，key是唯一的，假设现在没有重写这两个方法，然后存入两个自定义的相同对象，先调用Object的hashCode()方法，由于Object的hashCode()方法是比较的是两个不同引用地址的对象，所以自定义的两个相同对象的的hashCode的结果不一样，那就会被判定为两个不同的对象，都会存到HashMap中作为key，这就不符合key的唯一性了，其实原因和下面的Set一样
为什么重写equals时必须重写hashCode方法？
如果只重写了 equals 方法，那么默认情况下，假设存了两个自定义的内容相同的对象到Set中，Set 进行去重操作时，会先判断两个对象的 hashCode 是否相同，此时因为没有重写 hashCode 方法，所以会直接执行 Object 中的 hashCode 方法，而 Object 中的 hashCode 方法对比的是两个不同引用地址的对象，那么得到的两个Hash值是不一样的，那么 equals 方法就不会执行了，这两个对象就会被判断为不是相等的，于是就在 Set 集合中插入了两个相同的对象（这里的相同是指的内容相同）。
但是，如果在重写 equals 方法时，也重写了 hashCode 方法，那么在执行判断时会去执行重写的 hashCode 方法，此时对比的是两个对象的所有属性的 hashCode 是否相同，于是调用 hashCode 返回的结果就是 true，再去调用 equals 方法，发现两个对象确实是相等的，于是就返回 true 了，因此 Set 集合就不会存储两个一模一样的数据了，于是整个程序的执行就正常了。
总结
hashCode 和 equals 两个方法是用来协同判断两个对象是否相等的，采用这种方式的原因是可以提高程序插入和查询的速度，如果在重写 equals 时，不重写 hashCode，就会导致在某些场景下，例如将两个相等的自定义对象存储在 Set 集合时，就会出现程序执行的异常，为了保证程序的正常执行，所以我们就需要在重写 equals 时，也一并重写 hashCode 方法才行。
HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
在理论上，可以使用 `hashCode()` 处理后的哈希值直接作为 `table` 数组的下标，但是这种做法可能会导致哈希冲突，即不同的键可能会产生相同的哈希值，从而导致它们被映射到相同的 `table` 下标位置，这就会影响 HashMap 的性能。
为了解决这个问题，HashMap 使用了一种称为“拉链法”的解决方案。具体地，HashMap 中的每个桶都是一个链表，当多个键映射到同一个桶时，它们会被存储在该桶对应的链表中。在检索时，HashMap 会先根据键的哈希值找到对应的桶，然后再在该桶对应的链表中查找键值对。
当然，如果链表过长，会影响 HashMap 的性能。因此，在 JDK 8 中，当链表长度超过一定阈值（默认为 8）时，HashMap 会将链表转换为红黑树，以提高查找效率。这种做法可以在大部分情况下保证 HashMap 的性能。
HashMap 的长度为什么是2的幂次方
因为这样可以让计算桶位置的操作更加高效。
具体来说，如果 HashMap 的长度是 2 的幂次方，那么计算桶位置时可以使用位运算来代替除法运算，从而提高计算速度。
我们都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算 hash(KEY) % 数组长度
HashMap为了存取高效，就要尽量减少碰撞，将数据分配均匀，那么如何分配均匀，此时主要靠将数据存入到那个链表中的算法，这个算法就是 hash(KEY) & (length - 1)。& 是按位与运算，是一个位运算，而在计算机中位运算的效率很高，% 计算比 & 慢很多,这就是不用%运算的原因,为了保证 & 的计算结果等于 % 的结果需要把 length 减 1。
hash(KEY) & (length - 1)=hash(KEY) %length
既然两个计算出的hash值是相同的那当然是用效率更高的&
我做了一个小实验：
假设现在数组的长度：2 ^ 14 = 16384
String key = "zZ1!." 的 hash 值为 115398910
public static void main(String[] args) { String key = "zZ1!."; System.out.println(key.hashCode());// 115398910 }
hash & (length - 1) = 115398910 & 16383 = 6398 （你可以使用电脑的计算机验证一下是不是对的）6398 的二进制是 0001100011111110
hash % length = 115398910 % 16384 = 6398
这样可以大大提高计算速度，因为按位与运算比取模运算要快得多。
另外，长度为 2 的幂次方的数组也可以更好地处理哈希冲突。在使用链表解决哈希冲突时，如果数组长度是 2 的幂次方，那么每个桶的链表长度最多只有 8 个元素，这样可以保证链表的查找效率。如果数组长度不是 2 的幂次方，那么桶的数量可能不能均匀分布，从而导致某些桶的链表长度很长，影响查找效率。
因此，为了提高 HashMap 的性能，通常建议将长度设置为 2 的幂次方。
骚戴理解：如果数组长度是 2 的幂次方，每个桶的链表长度最多只有 8 个元素是因为 JDK 1.8 中 HashMap 的实现使用了一种称为“树化”的策略，当某个桶中的链表长度超过了 8 个元素时，会将该链表转换成红黑树，以提高查找效率。
树化操作的前提条件是桶中的链表长度超过了阈值（默认为 8），而如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的。例如，如果数组长度是 16，那么对于任意的哈希值，它与 15 的按位与操作的结果一定是在 0 到 15 之间。
因此，如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的，也就是说，它一定可以作为桶的下标。而由于数组长度是 2 的幂次方，因此桶的数量也是 2 的幂次方，这样就可以保证桶的数量和数组长度是一致的，从而可以保证每个桶的链表长度最多只有 8 个元素。
需要注意的是，这种情况只针对 JDK 1.8 中 HashMap 的实现，如果使用其他版本的 HashMap 或者其他哈希表实现，可能不具备这种性质。
那为什么是两次扰动呢？
答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；
HashMap 与 HashTable 有什么区别？
线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap 吧！）；
效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外， HashTable 基本被淘汰，不要在代码中使用它；
对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
初始容量和扩容机制：HashTable 的初始容量为 11，而 HashMap 的初始容量为 16。当 HashTable 中元素的数量超过了容量的 0.75 倍时，会自动扩容为原来的 2 倍。而 HashMap 中元素的数量超过了容量的 0.75 倍时，会自动扩容为原来的 2 倍，并且扩容后的容量一定是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
骚戴理解：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用， 推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用ConcurrentHashMap 替代。
如何决定使用 HashMap 还是 TreeMap？
在选择 HashMap 还是 TreeMap 时，需要根据具体的需求和场景来决定。
1. 查找效率：如果主要是进行查找操作，而对插入和删除操作的效率要求不高，那么可以选择 TreeMap。因为 TreeMap 内部采用红黑树实现，可以保证元素有序，并且查找效率比 HashMap 更高，时间复杂度为 O(log n)。
2. 插入和删除效率：如果主要是进行插入和删除操作，而对查找操作的效率要求不高，那么可以选择 HashMap。因为 HashMap 内部采用哈希表实现，可以保证插入和删除操作的效率比 TreeMap 更高，时间复杂度为 O(1)。
3. 内存占用：如果需要对大量数据进行操作，并且内存占用是一个问题，那么可以选择 HashMap。因为 HashMap 内部采用哈希表实现，可以保证元素存储在数组中，占用的内存比 TreeMap 更小。
4. 元素有序性：如果需要对元素进行排序，那么必须选择 TreeMap。因为 TreeMap 内部采用红黑树实现，可以保证元素有序。
综上所述，如果需要进行查找操作并且对元素有序性要求较高，可以选择 TreeMap；如果需要进行插入和删除操作并且对内存占用要求较高，可以选择 HashMap。如果需要同时兼顾查找效率和插入删除效率，可以使用 LinkedHashMap，它是基于哈希表和双向链表实现的，可以保证元素有序，并且插入和删除操作的效率比 TreeMap 更高。
