1,HashMap 的结构是怎样的?
二维结构,第一维是数组,第二维是链表
2,Get 方法的流程是怎样的?
先调用 Key 的 hashcode 方法拿到对象的 hash 值,然后用 hash 值对第一维数组的长度进行取模,得到数组的下标.这个数组下标所在的元素就是第二维链表的表头.然后遍历这个链表,使用 Key 的 equals 同链表元素进行比较,匹配成功即返回链表元素里存放的值.
3,Get 方法的时间复杂度是多少?
HashMap 中,如果 key 经过 hash 算法得出的数组索引位置全部不相同,即 Hash 算法非常好,那样的话,getKey 方法的时间复杂度就是 O(1),如果 Hash 算法技术的结果碰撞非常多,假如 Hash 算极其差,所有的 Hash 算法结果得出的索引位置一样,那样所有的键值对都集中到一个桶中,或者在一个链表中,或者在一个红黑树中,时间复杂度分别为 O(n) 和 O(lgn).
4,请解释一下 HashMap 的参数 loadFactor,它的作用是什么?
loadFactor 表示 HashMap 的拥挤程度,影响 hash 操作到同一个数组位置的概率.默认 loadFactor 等于 0.75,当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap 太挤了,需要扩容,在 HashMap 的构造器中可以定制 loadFactor.
5,请说明一下 HashMap 扩容的过程?
扩容需要重新分配一个新数组,新数组是老数组的 2 倍长,然后遍历整个老结构,把所有的元素挨个重新 hash 分配到新结构中去.这个 rehash 的过程是很耗时的,特别是 HashMap 很大的时候,会导致程序卡顿,而 2 倍内存的关系还会导致内存瞬间溢出,实际上是 3 倍内存,因为老结构的内存在 rehash 结束之前还不能立即回收.那为什么不能在 HashMap 比较大的时候扩容扩少一点呢,关于这个问题我也没有非常满意的答案,我只知道 hash 的取模操作使用的是按位操作,按位操作需要限制数组的长度必须是 2 的指数.另外就是 Java 堆内存底层用的是 TcMalloc 这类 library,它们在内存管理的分配单位就是以 2 的指数的单位,2 倍内存的递增有助于减少内存碎片,减少内存管理的负担.
本文转自: https://www.toutiao.com/i6504574147786441229/?group_id=6504574147786441229&group_flags=0
来源: http://www.bubuko.com/infodetail-2475198.html