HashMap底层实现原理

开发者 · 2024-10-8 18:59:48

java1.7 从前HashMap底层由数组+链表情势实现。
1.1 插入数据时起首盘算数据key的hash值，根据hash找到对应的数组槽位。
1.2 找到槽位后，判定当前数组槽位是否为null，null则直接作为链表表头插入，否则判定当前须要插入的key是否已经在当前槽位的链表中存在，存在则直接更换新值，不存在则插入到头结点。

// hash值盘算static final int hash(Object key){ int h; // h = key.hashCode() 取hashCode值 // h ^ (h >>> 16) 高位运算 return key == null ? 0 : (h = key.haskCode()) ^ (h >>> 16);} // 盘算槽位 (n-1) & hash

java1.8 引入和红黑树，底层由数组+链表+红黑树实现。
2.1 java1.8中插入元素时，会判定当前槽位对应的链表长度，如果长度大于即是8，会将链表转换为红黑树。当红黑树节点<=6 则会重新转换为链表。
2.2 java1.8 在链表插入元素时，接纳的尾部插入法，即将新节点插入到链表尾部。
2.3 为什么引入红黑树：jdk1.8从前由于链表的查询服从非常低，当hash辩论严峻时，链表过长，严峻影响查询性能。散列列表最理想的查询服从为O(1)，但是链表过长时，会导致查询退化为O(n)。为相识决这个题目所以jdk8中的HashMap添加了红黑树来办理这个题目，当链表长度>=8的时间链表就会酿成红黑树，红黑树实在就是一颗特别的二叉排序树，匀称时间复杂度为O(log2(n))。

HashMap底层实现原理

所属分类: 问答交流

新帖推荐: 30日

推荐作品