Ray_YC's Blog

面试知识点总结

 
  • 2024年 02月18日

HashMap

HashMap数据结构图

Image

这张图囊括了HashMap中最基础的几个点：

  1. Java中HashMap的实现的基础数据结构是数组，每一对key->value的键值对组成Entity类以双向链表的形式存放到这个数组中

  2. 元素在数组中的位置由key.hashCode()的值决定，如果两个key的哈希值相等，即发生了哈希碰撞，则这两个key对应的Entity将以链表的形式存放在数组中

  3. 调用HashMap.get()的时候会首先计算key的值，继而在数组中找到key对应的位置，然后遍历该位置上的链表找相应的值。

当然这张图中没有体现出来的有两点：

  1. 为了提升整个HashMap的读取效率，当HashMap中存储的元素大小等于桶数组大小乘以负载因子的时候整个HashMap就要扩容，以减小哈希碰撞，具体细节我们在后文中讲代码会说到
  2. 在Java 8中如果桶数组的同一个位置上的链表数量超过一个定值，则整个链表有一定概率会转为一棵红黑树。
  3. 整体来看，整个HashMap中最重要的点有四个：初始化，数据寻址-hash方法，数据存储-put方法,扩容-resize方法，只要理解了这四个点的原理和调用时机，也就理解了整个HashMap的设计。

##问题：

HashMap内部的bucket数组长度为什么一直都是2的整数次幂？

  • 获取hash值的代码 
    static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/* 
这里比较重要的是
(h = key.hashCode()) ^ (h >>> 16)
这个位运算其实是将key.hashCode()计算出来的hash值的高16位与低16位继续异或
*/
    1. 可以通过(table.length - 1) & key.hash()这样的位运算快速寻址，
    2. 在HashMap扩容的时候可以保证同一个桶中的元素均匀的散列到新的桶中，具体一点就是同一个桶中的元素在扩容后一般留在原先的桶中，一般放到了新的桶中。 ```markdown

在HashMap这个特殊的数据结构中，hash函数承担着寻址定址的作用，其性能对整个HashMap的性能影响巨大，那什么才是一个好的hash函数呢？

  1. 计算出来的哈希值足够散列，能够有效减少哈希碰撞
  2. 本身能够快速计算得出，因为HashMap每次调用get和put的时候都会调用hash方法 ```

HashMap默认的bucket数组是多大

默认是16，即使指定的大小不是2的整数次幂，HashMap也会找到一个最近的2的整数次幂来初始化桶数组。

HashMap什么时候开辟bucket数组占用内存

答：在第一次put的时候调用resize方法

HashMap何时扩容？

答：当HashMap中的元素数量超过阈值时，阈值计算方式是capacity * loadFactor，在HashMap中loadFactor是0.75

桶中的元素链表何时转换为红黑树，什么时候转回链表，为什么要这么设计？

答：当同一个桶中的元素数量大于等于8的时候元素中的链表转换为红黑树，反之，当桶中的元素数量小于等于6的时候又会转为链表，这样做的原因是避免红黑树和链表之间频繁转换，引起性能损耗

Java 8中为什么要引进红黑树，是为了解决什么场景的问题？

答：引入红黑树是为了避免hash性能急剧下降，引起HashMap的读写性能急剧下降的场景，正常情况下，一般是不会用到红黑树的，在一些极端场景下，假如客户端实现了一个性能拙劣的hashCode方法，可以保证HashMap的读写复杂度不会低于O(lgN)

HashMap如何处理key为null的键值对？

答：放置在桶数组中下标为0的桶中

put 方法的思路

  1. 调用key的hashCode方法计算哈希值，并据此计算出数组下标index
  2. 如果发现当前的桶数组为null，则调用resize()方法进行初始化
  3. 如果没有发生哈希碰撞，则直接放到对应的桶中
  4. 如果发生哈希碰撞，且节点已经存在，就替换掉相应的value
  5. 如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上
  6. 如果碰撞后为链表，添加到链表尾，如果链表长度超过TREEIFY_THRESHOLD默认是8，则将链表转换为树结构
  7. 数据put完成后，如果HashMap的总数超过threshold就要resize

    resize() 方法

    • 如果在put数据之后超过了threshold的值，则需要扩容，扩容意味着桶数组大小变化，我们在前文中分析过，HashMap寻址是通过index =(table.length - 1) & key.hash() ;来计算的，现在table.length发生了变化，势必会导致部分key的位置也发生了变化。 如果在即将扩容的那个位上key.hash()的二进制值为0，则扩容后在桶中的地址不变，否则，扩容后的最高位变为了1，新的地址也可以快速计算出来newIndex = oldCap + oldIndex;

– 返回顶部 –

搜索