游客您好
第三方账号登陆
  • 点击联系客服

    在线时间:8:00-16:00

    客服电话

    020-85534346

    电子邮件

    81058337@qq.com
  • 码云社APP

    随时掌握码云社动态

  • 扫描二维码

    关注砺锋微信公众号

HashMap的实现原理笔记

发布时期:2019-5-24 17:41
阅读:1207 回复:20

序HashMap是Java中常用的Map接口的实现类,因为在日常工作中非常频繁的出现,所以在大部分的Java面试中都会问几个关于HashMap的问题。掌握HashMap的实现原理,已经是Java程序员的基础操作了。Map接口映射(Map)是一 ...

HashMap是Java中常用的Map接口的实现类,因为在日常工作中非常频繁的出现,所以在大部分的Java面试中都会问几个关于HashMap的问题。掌握HashMap的实现原理,已经是Java程序员的基础操作了。

Map接口

映射(Map)是一种用于存放键/值对的数据结构。如果提供了键,就能直接找到相对应的值。HashMap(哈希映射)是Map接口的一个实现类,主要使用哈希来实现键与值的映射。

定义。映射是一种用于存放键/值对的数据结构,主要支持两种操作:插入(put),即将一组新的键值对存入映射中;查找(get),即根据给定的键得到相应的值。

HashMap的底层数据结构

HashMap的底层是用散列表实现的,散列表是一种用数组来存储键值对的数据结构,它使用一个散列函数将键转换成数组的一个索引然后存储值。不过会有不同的键被散列成同个索引的情况出现,这叫做碰撞冲突。HashMap用拉链法来解决这个问题,即散列表数组中的每个元素都指向一条链表,链表中的每个节点都存储了被散列到这个索引的键值对。

HashMap的实现原理笔记

HashMap的散列函数

根据散列表的定义我们知道,想要弄清楚HashMap的实现,我们首先需要知道HashMap的散列函数是怎么实现的,即HashMap是如何将一个键映射到数组的索引的。

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

上面就是HashMap的散列函数源码了,可以看到如果键为null的话它的索引固定为0,即HashMap是支持使用null作为键的。如果键不为null就用Java对象都有的hashCode方法获得一个哈希值,并将这个哈希值的低16位与高16位做异或处理,高16位不变。

这里有个问题就是为什么不直接用键的hashcode,而要将hashcode的低16位与高16位做异或处理?这里是因为有三个前提:

  • int有32位
  • HashMap的数组长度都是2的幂
  • 获取数组索引需要将键的哈希值和数组长度-1做一个与操作(&)得到,即tab[(n - 1) & hash]

首先因为HashMap的数组长度都是2的幂,(n - 1)的高16位都是0,所以只有键的低16位参与索引运算。如果直接用键的hashcode的话,就会有很多碰撞冲突,所以用这种方法使得hashcoede的高16位也参与到索引的运算中来。下面是字符串“1234”在数组长度为16的索引运算过程:

public static void main(String[] args) {
int hashcode = "1234".hashCode();
System.out.println(Integer.toBinaryString(hashcode));
// 输出为 10111 0000100001000010
System.out.println(Integer.toBinaryString(hashcode >>> 16));
// 输出为 10111
System.out.println(Integer.toBinaryString(hashcode ^ (hashcode >>> 16)));
// 输出为 10111 0000100001010101
System.out.println(Integer.toBinaryString(16 - 1));
// 输出为 1111
System.out.println(Integer.toBinaryString((16 - 1) & (hashcode ^ (hashcode >>> 16))));
// 输出为 101
}
HashMap的实现原理笔记

碰撞冲突

虽然HashMap对散列函数做了很多优化,但是碰撞冲突还是不可避免的会出现。为了解决这个问题HashMap使用了拉链法,使用链表来存储碰撞冲突的键值对。并在JDK 8中进行了优化,当链表长度到达某个指定值时HashMap会自动将链表优化为红黑树。频繁碰撞冲突还可能是因为数组长度不够的原因,HashMap还会根据键值对的数量进行自动扩容。

自动扩容

在讲HashMap的自动扩容前,先来看看HashMap有哪些相关的属性:

  • Node[] table; 存放键值对的数组
  • int size; 已存放键值对的数量
  • int threshold; 当键值对的数量等于这个值的时候HashMap将进行扩容,值等于数组长度 * loadFactor
  • final float loadFactor; 负载因子,用于计算threshold的值,默认值为0.75
  • static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 数组长度的默认值16

根据这些属性可以知道,HashMap的自动扩容会根据数组长度和负载因子的积得到一个threshold的值,当键值对的数量等于threshold时就会开始扩容,下面是扩容的源码。大概过程是新建一个长度为旧数组两倍的新数组,并将原有的键值对都重新映射到新数组上。

final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

后记

这次主要是理解了一下HashMap的实现原理,特别重点写了很多关于散列函数的理解,并没有按照源码一行行的去理解。之所以这样是因为写这篇的动力主要来源于面试……而面试则只要讲下原理就可以了,并不需要把源码背下来。之前看HashMap的时候对散列函数都是跳过去的,只知道是用来计算键的hash,不知道里面的原理。其实还有链表转红黑树的地方没有弄清楚,主要是红黑树不怎么理解,基础的重要性体现了出来。

GONGYANQIN(未知职业)-本文作者
这个人很懒,什么也没有留下。
1207 20 2019-5-24 17:41
该文章已有20人参与评论

请发表评论

全部评论

查看全部评论>>

扫一扫关注官方微信号

最前沿的技术信息一手掌握

滚动新闻
CODESEEDING(码云社)一家致力于程序员成长、以内容为核心、以提问为引导的多元化成长社区。我们在线上为技术爱好者提供了一个优质的交流氛围环境,在线下同样和众多高校联合开办了技术沙龙品牌。
020-85534346
关注我们
  • 访问移动H5版
  • 官方微信公众号

码云社 - CODESEEDING 2.0© 2018-2019 码云社. TOOBUG ( 粤ICP备16114193号-3 )