HashMap源码解析

HashMap特点

1. 存储键值对的
2. 允许null值和null键
3. HashMap是非synchronized

创建

HashMap创建有两个重要的参数一个是loadFactory一个是capacity

1. loadFactory: 装在因子。默认初始为0.75。
   • 是用来衡量HashMap的装满程度。
2. capacity :容量
   • 表示HashMap的容量大小(桶的数量)
3. threshold: 阈值 (容量*装载因子)
   • 当当前桶的数量大于threshold的时候，需要扩容
   • 扩容大小为当前的一倍

内部结构

HashMap内部是由 数组+链表(红黑树)实现的。HashMap内部维护了一个HashMap.Node[]数组 用来存储列表的头节点Node。默认大小是16。

Put

• 根据key 利用key的hashCode计算出 key在数组中对应的下标index
• 如果碰撞了，以链表的形式存在buckets后；
• 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)默认是8，就把链表转换成红黑树；
• 如果节点已经存在就替换old value(保证key的唯一性)
• 如果bucket满了(超过load factor*current capacity)，就要resize。

Get

• 根据key 利用key的hashCode计算出 key在数组中对应的下标index
• 如果有冲突，则通过key.equals(k)去查找对应的entry
• 若为树，则在树中通过key.equals(k)查找，O(logn)；
• 若为链表，则在链表中通过key.equals(k)查找，O(n)。

Hash函数的实现

在get和put操作的时候都是对key先进行hashCode,在对hash值进行计算，得出对应的下标值，过程如下:

[图片上传失败...(image-626f1c-1539854723840)]

在对hashCode()计算hash时具体实现是这样的：

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

可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或。

Resise实现

当put的时候，发现当前的buckt大小大于threshold 阈值的时候，需要进行扩容。在resise的过程简单的说就是将数组扩容为原来的两倍，重新计算index下标，把节点放置到新的数组中。

红黑树

具体参考红黑树数据结构

参考

• HashMap工作原理及实现