HashMap的数据结构

千锋教育

在Java中,保存数据有两种比较简单的数据结构:数组和链表。

  • 数组的特点是:寻址容易,插入和删除困难;
  • 链表的特点是:寻址困难,但插入和删除容易;


所以我们将数组和链表结合在一起,发挥两者各自的优势,就可以使用俩种方式:链地址法和开放地址法可以解决哈希冲突:



链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;


开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。


但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化