不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

HashMap 面试题

讲讲Hash算法?

Hash算法就是将任意长度的输入,映射到固定长度的输出。可能会存在Hash冲突,比如10个元素,映射到长度为9的hash表里面,一定有一个元素会冲突,解决方案有拉链法、开放地址法。

好的Hash算法应该考虑哪些内容?

应该考虑,分布要尽量的均匀、尽可能的避免hash冲突、通过结果不能反推回原先的值、一点小的变动也会得到不同的结果、效率要高效,长的文本也很快计算出结果。

HashMap的数据结构?

在Jdk1.8里面,HashMap采用的是数组+链表+红黑树的结构,每个结点是用Node表示,Node里面有key,value,next指针,hashcode值。当Hash冲突的时候采用的是拉链法。
还有TreeNode 表示红黑树结点,TreeNode 继承于HashMap的Node 结点,有parent指针执行父节点,left指针指向左孩子,right指针指向右孩子,同样也有Node结点的next指针。

初始容量?负载因子有什么作用?

HashMap如果不传入容量大小的话,默认是16,如果传入的容量大小不是2的整次幂,会自动调整为比该数大的2次幂。默认的负载因子是0.75,用来计算HashMap扩容的阈值,如果使用的是默认大小的容量的话,达到16 * 0.75=12 就会触发扩容,扩容的话是原始容量左移一位,也就是扩容一倍。
Hash表是采用的是懒加载的机制,不是在初始化的时候创建的。

链表什么时候转换成红黑树?

当Hash冲突的链表长度达到8 而且hashMap的元素大于64 的时候 转换成红黑树,如果 只是链表长度达到8的话,会触发扩容。

哈希码是怎么计算的?

通过key.hashCode()进行高16位跟低16位进行按位异或得到的,充分利用高16位。

为什么要高16位跟低16位异或?

因为桶的下标是通过key的hashcode 跟hashmap的长度-1进行与运算获取到的,而hashmap的长度是2的整次方,所以长度-1 就是低位全位1,高位为0, 比如 16-1=15的二进制 为0000 1111,所以高位0跟任何数据进行与运算结果都是0,只会使用到低16位的1。所以通过hashcode高16位跟低16位进行按位异或,使用到key.hashcode的所有二进制位,充分利用高16位。

put 写数据的具体流程

当put 一个数据的时候,计算key的hash码 然后跟hashmap长度-1相与 获取到桶的下标;有四种状态:该位置为null、该位置有一个Node元素、该位置已经链表化、该位置已经变成红黑树:
如果该位置没有元素,则直接创建Node 结点放入桶内; 如果该位置有数据,还是链表结构,则通过hashcode 和equalsl判断两个对象是否相等,相等则直接覆盖,否则创建一个Node 结点,插入到末尾,插入后判断是否要转换成红黑树; 如果该位置有数据,而且已经是红黑树的结构,如果找到相同的key则覆盖,否则找到红黑树的插入结点,进行插入,并左旋、右旋保证红黑树的性能。

红黑树的写入操作,是怎么找到父节点的?

红黑树属于二叉搜索树,是有序的,也就是对于每个结点,左孩子小于父结点,父节点小于右孩子。 所以通过从根结点开始,往下遍历,找到插入的位置的父结点。然后插入到该结点的左孩子或者右孩子,并进行旋转和染色保证性质。

旋转:左旋——自己变为右孩子的左孩子; 右旋——自己变为左孩子的右孩子

红黑树的原则有哪些呢?

红黑树的性质:

  • 每个节点要么是黑色,要么是红色
  • 不存在连续的红色结点,根结点和叶子结点是黑色。
  • 每个红色结点的两个子结点一定都是黑色
  • 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
  • 新插入的结点是红色的

转换成红黑树为了解决Hash冲突的问题,因为查询链表的时间复杂度是O(n),转换成红黑树后时间复杂度变成O(log(n)).

hashmap 什么情况下会触发扩容?

当HashMap中结点的数量 大于阈值的时候会进行扩容。扩容的时候是扩容成原来的两倍,通过左移一位来完成的。

扩容后是怎么进行迁移的?

Hashmap 在扩容的时候是把旧表的数据迁移到新表,按桶顺序来的,每个桶有四种情况:该桶的位置存储的是null值、存储有一个Node,但还没有转换成链表、存储的是一个链表、存储的是一个红黑树;
如果存储的是null值的话就不需要迁移,如果存储的是一个没有链化的Node,根据新表的大小直接迁移即可;
如果存放的是一个Node链表,则把链表进行拆分,分成高位链和低位链;因为结点的hash码跟hash表的长度减1相与,得到桶的下标,比如 16-1=15的二进制位=0000 1111,所以低位全是1,高位全是0,而扩容后变成32-1=31;相比较只是多了一个高位的1,而且0跟任何数相与都是0,所以只需要判断多出的这高位1,对应的hash码是1,还是0;0的话还是在旧表的位置,1的话在旧表的位置+旧表的容量。
如果存放的是一个红黑树的话,因为红黑树继承于Node 结点,还是保留了next指针,内部还是维护了一个链表,也根据这个链表拆分成高位链和低位链,和链表的情况类似,只是要判断拆分出来的链表的长度是否小于6,小于6则从红黑树退化为链表。


目录