HashMap

2022-08-25 22:07:20   29  举报





AI智能生成

仅用来概括性总结，用于面试阐述给面试官或者准备面试的。

Java

数据结构

HashMap

模版推荐

作者其他创作

大纲/内容

底层结构

JDK1.7以及之前由数组加链表实现

JDK1.8以及之后由数组加链表加红黑树实现

源码

默认容量为16且必须是2的幂次方

为什么是2的幂次方？ 因为计算数组下标的时候要用到数组长度

最大容量是2^30

默认负载因子是0.75

阈值=容量*负载因子。添加键值对后， 如果键值对的个数 > 阈值，则进行扩容

树化阈值=8。当桶的链表上元素个数 >= 8 则链表转成红黑树

红黑树是一棵自平衡的二叉查找树， 解决了链表线性查找的性能问题

非树化阈值=6。当桶的链表上元素个数 <= 6 则红黑树转成链表

树化阈值的最小容量=64。 数组的长度 >= 64 && 桶上的链表元素个数 >= 8才会进行树化， 否则进行数组扩容，扩容后的容量是旧的2倍，即旧值左移1位

put元素进去时计算数组下标

首先计算hash() = (key.hashcode) ^ (key.hashcode >>> 16)。 再用(数组长度 - 1) & hash()。 1. hashcode的高16位与低16作异或运算，使得hash出来的值更加普遍 2. hash出来的值通常很大，如果采用%运算，则基本都会落到数组最后面部分的桶上。 数组长度限制为2幂次方后，数组长度-1得到的二进制就是全部二进制位为1， 因此采用&运算只有个操作数为1才是1。 3. &运算比%运算、/运算要快

面试问题

HashMap如何解决冲突的？ 为什么链表转红黑树

1. key的hashcode高16位与低16位作^异或运算， 降低hash冲突的概率，使数据均匀分布

2. 采用链地址法链接具有相同hash值的元素

3. 链表查询性能是O(n)，红黑树是O(logN)。 链表变长查询性能下降，而红黑树是一个二叉查找树。 而且红黑树不是绝对平衡，省去非必要的左旋右旋。

什么时候扩容？

添加键值对后，如果键值对个数  > 阈值(数组容量*负载因子)， ‌则扩容。新容量是旧容量的2倍(旧容量左移1位)

数组某个桶上链表长度 >= 8，且数组长度 < 64时，也会扩容而不是链表转红黑树。

数组长度小于等于64时，直接扩容可以重新分配数据的位置， ‌比树化要好，树结点的大小比普通节点大两倍。‌其实是在时间和空间权衡

数组长度为什么要2的幂次方

计算下标一般采用取余操作。 ‌如果取余操作中除数是2的幂次方，则等价于与除数减1作&运算。 ‌而且&运算速度比%运算速度快

因此采用了数组长度n-1 & hash()计算下标。 ‌当n为2的幂次方，n-1的二进制为全是1，不管hash()的值是多少， ‌算出来的下标都不会数组越界。