一、什么是HashMap?

HashMap用于存储Key-Value键值对(Entry)集合,基于哈希表的Map接口实现,也是一个”链表散列”的数据结构,即数组与链表的结合体。其底层就是一个数组结构,当entry的next指向不为null时,数组里面又是链表,在JDK8及后续版本中,当链表长度超过阈值(8)时,链表将转换为红黑树。

二、HashMap的默认初始长度是多少?为什么这么规定?

HashMap中默认数组长度是16(每一个元素初始值都是NULL),并且每次自动扩展或是手动初始化时,长度必须是2的幂。之所以选择16,是为了服务于从Key映射到index的hash算法。index = HashCode(Key)&(Length - 1)

三、put()方法原理

在调用put()方法时,首先使用hashCode()方法计算出元素key的hash值,以此确定插入数组中的索引位置。如果索引处为空,则直接插入对应的数组中,否则,判断是否是红黑树,若为红黑树则插入,否则遍历链表插入,如果链表长度超过8,则将链表转换为红黑树,转成功之后再插入。

四、get()方法原理

首先会把输入的key通过hashCode()方法做一次Hash映射,得到对应的索引。接着判断key是不是唯一,如果key唯一,则直接返回。如果不唯一(hash碰撞),则使用equals进行key值的判断,最后返回数据。

五、什么是hash碰撞?如何解决?

1. 是什么

hashMap在进行put操作的时候会根据key的hashCode()方法去获取hash值,再根据这个hash值去找哈希桶的位置,当出现key的hashcode值相同时,即为hash碰撞。

2. 怎么办

  • 开放地址法:
    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。
    它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。有几种常用的探查序列的方法,即线性探查、二次探查、伪随机探测

  • 再散列/再哈希法:
    当发生冲突时,将再次散列,直至不发生冲突位置;缺点:计算时间增加。

  • 链地址法/拉链法[HashMap采用方法]:
    将产生冲突的值以链表的形式连起来。就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)

3. 方式比较

1. 拉链法的优点:
与开放定址法相比,拉链法有如下几个优点:

  • 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  • 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
  • 开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
  • 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

2. 拉链法的缺点:
指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

六、HashMap线程不安全会导致什么问题?

(1)在jdk1.7中,在多线程环境下,并发插入元素扩容的时候可能会造成环形链让下一次读操作出现死循环。
(2)在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。(在jdk1.8中对HashMap进行了优化,在发生hash碰撞,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程的情况下仍然不安全。)

七、涨姿势

1. 为什么Java8之后链表数据超过8以后就改成红黑树存储?

  • 查询效率得到提升,从原来的O(n)到O(logn)
  • 更为安全(拒接服务攻击)。比如某些人通过查找到你的hash碰撞值,来让你的HashMap不断产生碰撞,那么相同key位置的链表就会不断增长,当你需要对这个HashMap的相应位置进行查询的时候,就会去循环遍历这个超级大的链表,导致性能及其低下。

2. 拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,链表长度低于6,就把红黑树转回链表,因为根本不需要引入红黑树,引入反而会慢。




参考资料:
什么是HashMap
高并发下的HashMap
HashMap线程不安全的体现
解决哈希冲突的三种方法(拉链法、开放地址法、再散列法)