HashMap 底层结构是什么JDK 8 中 HashMap 的数据结构是数组链表红黑树。在知道了其底层的结构之后还需要知道这每一个结构的作用以及他们之间的相互转换关系所以接下来要去分析 数组链表和红黑树之间是存储了哪些信息以及相互之间是怎么进行转换的数组用来存储键值对每个键值对可以通过索引直接拿到索引是通过对键的哈希值进行进一步的hash()处理得到的。当多个键经过哈希处理后得到相同的索引时需要通过链表来解决哈希冲突——将具有相同索引的键值对通过链表存储起来。不过链表过长时查询效率会比较低于是当链表的长度超过 8 时且数组的长度大于 64链表就会转换为红黑树。红黑树的查询效率是 O(logn)比链表的 O(n) 要快。怎么处理哈希冲突的问题这些都是要答到上面提到了hash()方法这里应该去做相对应的处理以及既然提到了底层的结构里面有数组什么的就需要考虑到需要进行扩容等机制hash()方法的目标是尽量减少哈希冲突保证元素能够均匀地分布在数组的每个位置上。【hash()的作用】如果键的哈希值已经在数组中存在其对应的值将被新值覆盖。【覆盖】HashMap 的初始容量是 16随着元素的不断添加HashMap 就需要进行扩容阈值是capacity * loadFactorcapacity 为容量loadFactor 为负载因子默认为 0.75。【扩容机制】扩容后的数组大小是原来的 2 倍然后把原来的元素重新计算哈希值放到新的数组中。HashMap 什么时候扩容首先需要答到的就是hashmap如果要进行扩容的话会扩容到原来的多少倍---接着就是讲数组元素重新进行一个分配的问题对应的进行扩容的时候我们需要考虑三种情况只有一个元素的时候当前桶中只有一个元素应该怎么做如果是红黑树需要答到用到了spilt()方法来分裂树的节点保证树的平衡如果是链表需要注意 通过旧键的哈希值与旧的数组大小取模来作为条件判断当前的数组如何进行扩容操作扩容时HashMap 会创建一个新的数组其容量是原来的两倍。然后遍历旧哈希表中的元素将其重新分配到新的哈希表中。如果当前桶中只有一个元素那么直接通过键的哈希值与数组大小取模锁定新的索引位置e.hash (newCap - 1)。如果当前桶是红黑树那么会调用split()方法分裂树节点以保证树的平衡。如果当前桶是链表会通过旧键的哈希值与旧的数组大小取模(e.hash oldCap) 0来作为判断条件如果条件为真元素保留在原索引的位置否则元素移动到原索引 旧数组大小的位置。为什么负载因子是 0.75之前我们有提到过hashmap的扩容机制这里面提到了0.75负载因子是什么负载因子过大或者过小都会有什么样的问题呢负载因子load factor是一个介于 0 和 1 之间的数值用于衡量哈希表的填充程度。它表示哈希表中已存储的元素数量与哈希表容量之间的比例。负载因子过高接近 1会导致哈希冲突增加影响查找、插入和删除操作的效率。负载因子过低接近 0会浪费内存因为哈希表中有大量未使用的空间。默认的负载因子是 0.75这个值在时间和空间效率之间提供了一个良好的平衡。为什么容量要是 2 的幂是为了快速定位元素在底层数组中的下标。HashMap 是通过hash (n-1)来定位元素下标的n 为数组的大小也就是 HashMap 底层数组的容量。数组长度-1 正好相当于一个“低位掩码”——掩码的低位最好全是 1这样 运算才有意义否则结果一定是 0。2 幂次方刚好是偶数偶数-1 是奇数奇数的二进制最后一位是 1也就保证了hash (length-1)的最后一位可能为 0也可能为 1取决于 hash 的值这样可以保证哈希值的均匀分布。HashMap put 流程是什么哈希寻址 → 处理哈希冲突链表还是红黑树→ 判断是否需要扩容 → 插入/覆盖节点。第一步进行哈希寻址的操作通过 hash 方法进一步扰动哈希值以减少哈希冲突。第二步进行第一次的数组扩容并使用哈希值和数组长度进行取模运算确定索引位置。如果当前位置为空直接将键值对插入该位置否则判断当前位置的第一个节点是否与新节点的 key 相同如果相同直接覆盖 value如果不同说明发生哈希冲突。如果是链表将新节点添加到链表的尾部如果链表长度大于等于 8则将链表转换为红黑树。每次插入新元素后检查是否需要扩容如果当前元素个数大于阈值capacity * loadFactor则进行扩容扩容后的数组大小是原来的 2 倍并且重新计算每个节点的索引进行数据重新分布。只重写元素的 equals 方法没重写 hashCodeput 的时候会发生什么?如果只重写 equals 方法没有重写 hashCode 方法那么会导致 equals 相等的两个对象hashCode 不相等这样的话两个对象会被 put 到数组中不同的位置导致 get 的时候无法获取到正确的值。HashMap 为什么线程不安全HashMap 不是线程安全的主要有以下几个问题①、多线程下扩容会死循环。JDK7 中的 HashMap 使用的是头插法来处理链表在多线程环境下扩容会出现环形链表造成死循环。不过JDK 8 时通过尾插法修复了这个问题扩容时会保持链表原来的顺序。②、多线程在进行 put 元素的时候可能会导致元素丢失。因为计算出来的位置可能会被其他线程覆盖掉比如说一个线程 put 3 的时候另外一个线程 put 了 7就把 3 给弄丢了。这里的问题就是在多线程环境下同时put的话会有可能导致元素的丢失问题比如你们都是指向同一个数组位置你们put的位置是一样如果这时候两个元素都要添加到这个位置上就有可能导致其中一个元素还没有完成插入的时候计算出来的位置就被其他线程覆盖掉了③、put 和 get 并发时可能导致 get 为 null。线程 1 执行 put 时因为元素个数超出阈值而扩容线程 2 此时执行 get就有可能出现这个问题。这个位置的话主要强调的就是在 hashmap进行扩容的时候如果同时发生了putget操作有可能导致get出来的值是一个空值null那怎么去解决hashmap的线程安全问题呢在早期的 JDK 版本中可以用 Hashtable 来保证线程安全。Hashtable 在方法上加了 synchronized 关键字更优雅的解决方案是使用并发工具包下的 ConcurrentHashMap使用了CAS synchronized 关键字来保证线程安全。JDK 1.7 和 JDK 1.8 的 HashMap 有什么区别那就主要讲一下JDK8对于hashmap做了哪些优化吧①、底层数据结构由数组 链表改成了数组 链表或红黑树的结构。如果多个键映射到了同一个哈希值链表会变得很长在最坏的情况下当所有的键都映射到同一个桶中时性能会退化到 O(n)而红黑树的时间复杂度是 O(logn)。②、链表的插入方式由头插法改为了尾插法。头插法在扩容后容易改变原来链表的顺序。③、扩容的时机由插入时判断改为插入后判断这样可以避免在每次插入时都进行不必要的扩容检查因为有可能插入后仍然不需要扩容。④、哈希扰动算法也进行了优化。JDK 7 是通过多次移位和异或运算来实现的。JDK 8 让 hash 值的高 16 位和低 16 位进行了异或运算让高位的信息也能参与到低位的计算中这样可以极大程度上减少哈希碰撞。