hooyantsing's Blog

P097 深入理解HashMap与Hash算法

字数统计: 206阅读时长: 1 min
2022/03/10

视频源:阿里P8爆肝2个月呕心整理,挑战30天打卡春招上岸!

1. HashMap 的数据结构

  • JDK 1.7 及以前 HashMap 底层是 数组链表
  • JDK 1.8 以后 HashMap 底层是 数组链表 以及 红黑树

image-20220310212600893

JDK 1.8 什么时候链表会转化成红黑树

HashMap在元素比较少的时候,也只会有数组 + 链表的结构。

当链表的长度大于 8,HashMap 可能会做树化(链表转变成红黑树),不过就是需要再满足一个条件,就是数组长度必须大于等于 64 (初始是 16,经过两次扩容后),链表才会转变为红黑树。否则,只会触发数组的扩容。

2. 讲一讲 HashMap 中的 hash 算法

下图是 HashMap 的 put 和 get 方法流程:

image-20220310213121774

CATALOG
  1. 1. 1. HashMap 的数据结构
    1. 1.1. JDK 1.8 什么时候链表会转化成红黑树
  2. 2. 2. 讲一讲 HashMap 中的 hash 算法