HashMap特点
- 存储键值对的
- 允许null值和null键
- HashMap是非synchronized
创建
HashMap创建有两个重要的参数一个是loadFactory一个是capacity
- loadFactory: 装在因子。默认初始为0.75。
- 是用来衡量HashMap的装满程度。
- capacity :容量
- 表示HashMap的容量大小(桶的数量)
- 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下标，把节点放置到新的数组中。
红黑树
具体参考红黑树数据结构
