HashMap 考点记录

HashMap 面试

一、HashMap基本数据结构

散列性****

1、JDK 1.7

a、链表 + 数组
b、初始化入参：初始值大小 --> 数组大小 内部在初始化时一定会将数组的长度初始化为2的次方
因为在确定某个key对应具体的数组下标时
首先key.haskCode得到哈希值，哈希值%数组大小 = key对应的数组下标。
但是实际上的数组下标时根据 key.hashCode&(数组大小-1）实现的。这里仔细想想这个操作就明白为什么初始化数组的大小一定是要2的次方数。
但是由于在JDK 1.4下面，%操作在某些操作系统下面是运行效率比较低的，但是&操作在任何操作系统上面的效率都是很高的。

但是由于以上方法获取数组下标的方法，除了(数组大小-1）的bit位参数，其他的高位可能没有参与，重复太多可能导致hashmap效率下降，这个时候该想个办法让高位也参与进来：

c、扩容机制。1.7先扩容再添加元素 1.8 先添加元素再扩容
扩容的时候，数组的长度会变成原来的两倍，然后针对原来链表中的每个元素，都会重新计算数组下标。 注意这里计算的数组下标有个规律，新的数组下标和一定是以下两种情况，一种是新老数字下标相等，二是新数组下标=老数组下标 + 新增的数组长度。 JDK1.7并没有利用这个规则，JDK1.8利用了，这个在1.8源码的时候可以具体关注下。不过感觉这个规律似乎没有利用的空间啊，后面具体看下。

d、
JDK1.7 多线程情况下的扩容死循环问题可以关注下

e、key等于null的情况下固定存在数组第一位

f、扩容因子：
threshold（扩容阈值)= (int)Math.min(capacity * laodFactor, MAX)

2、JDK1.8 添加红黑树

a、JDK1.8 某些情况下将链表转化成红黑树，这种情况会有一个对应的阈值，该阈值限制链表上面的元素个数，超过阈值则转化成红黑树。而且还有一个反树化阈值。默认是6，树化阈值默认是8。两个阈值不同是预防频繁的红黑树与链表转换。

b、相对于1.7 哈希算法稍微简化了一点