1、HashMap概述
Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。特别地，
此外，HashMap 是 Map 的一个非同步的实现。
2、设计思想
HashMap采用的是哈希表的数据结构。哈希表是一种以
来存储的数据结构，哈希表的哈希函数通常有 直接定址法、平方取中法、求余法等。
而hashMap的设计者则采取求余法来对其进行元素的均匀分配。
在源码中，有这么一句代码tab[i = (n - 1) & hash],n代表的是数组的长度，hash是指的key的hashCode()值，这句话设计者的意思是想让其相当于hash%n(位运算比%的运算要快，源码中有大量这种位运算)，那么你可能会问了，怎养才能使得这两个相等呢？这就涉及到位运算的知识了。
首先要知道1&1=1,0&0=0,1&0=0,0&1=0
要使得 (n-1)&hash <==> hash%n,就得使得n为2的n次幂，因为2的n次幂的二进值形式为0000000100000xxxx,因为hashmap的数组长度初始化为1<<4,也就是16，那么就以16为例子，二进制为0...010000 ,n - 1也就是 0...01111,那么(n - 1)& hash为
hash : 00101010 00011111 00101010 01110100
&
n - 1: 00000000 00000000 00000000 00001111
---------------------------------------------------------
00000000 00000000 00000000 00000100
(可以看出得到的值是在0-15之间(这就保证了==>hash%n)， 而且决定最终值的是hash的后面4位)
这是hash值的计算方式。
static final int hash(Object key) {
int h;
//将前面的16位和后面的16位进行异或，使扰动之后的index结果尽可能的不同
//这么做也能在保证table的length比较小的时候，也能
//保证到高低位的bit都参与到hash的计算中来，同时也不会有太大的开销
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注意，由于hashCode()可以进行重写(hashCode和equals()这两个方法一定要
一起重写),所以key的hash值有可能重复(另外字符的hashCode()也有可能重复，如一些特殊字符)
那么你又会问了HashMap是如何保证长度是2的n次幂的呢？
这就要看tableSizeFor()了,这个方法保证了数组table的长度是不小于cap的最小2的n次幂
static final int MAXIMUM_CAPACITY = 1 << 30;//超过这个，就变成负数了
//得到不小于cap的最小整次幂(最高位1后面都变成1，然后再加1)
//eg：1 2 4 8 16 32
//cap:5 15 30 传入的cap
//n:8 16 32 得到的n
static final int tableSizeFor(int cap) {
int n = cap - 1;//为了避免cap是2的整次幂，从而导致n变成cap的2倍
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 :
(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
00000000 00000000 00000000 00000100 n
00000000 00000000 00000000 00000010 n>>>1 n|n:00000000 00000000 00000000 00000110
00000000 00000000 00000000 00000001 n>>>2 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>4 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>8 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000000 n>>>16 n|n:00000000 00000000 00000000 00000111
00000000 00000000 00000000 00001000 n+1
2.1初始化和扩容
Q:HashMap是什么时候进行初始化和扩容的，扩容的长度是多少，扩容是怎么进行的。
A:你可能会说，那我判断size>table.length,不就是可以进行扩容了吗？首先table数组并不是等到装满了，再进行扩容的，因为这样子会使得hash的碰撞增多，但是又不能太小就进行扩容，因为这会导致table里面的空元素增多，对table的空间进行浪费,这就使得我们要确定一个阀值对table数组进行扩容，而确定这个阀值的因素，我们就叫做 加载因子 。在hashMap中，加载因子loadFactor默认为0.75f。为什么是这个值，我总结了几点下面几点原因：
1、从区间上来说，0.5太小，会减少hash碰撞，造成空间的浪费,定义为1的话，则会造成hash碰撞增多
2、从数学角度上来说，由于长度是2的整次幂，所以*0.75一般都可以得到一个整数的结果
3、从泊松分布上来说，0.7多可以使得碰撞的元素在8以上的概率极大减小
但是为什么是0.75这个值,其实只是个经验值,和泊松分布并没有什么关系,这是java官方自己说的.
//初始化和扩容
final Node<K,V>[] resize() {
Node<K,V>[] 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){
//对旧的数组长度和旧的预期值进行2倍的扩容
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;//默认的初始化长度 1<<4 16
//初始化预期值
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//对旧的数组进行一个数据迁移
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//如果oldTab[j] 里面有东西(红黑树或者链表)
oldTab[j] = null;//清除旧的格子,对节点进行重新分布
if (e.next == null){//只有一个节点
newTab[e.hash & (newCap - 1)] = e;//用哈希函数重新计算index
}else if (e instanceof TreeNode){
//格子里面装着红黑树，对其进行拆解...
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}else { // preserve order
//格子里面装着多个节点,先初始化4个节点
//分别是头尾高低节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//下一个节点
do {
next = e.next;
//oldCap是2的整次幂 (因此二进制是
//10000....)，以16为例子，结果只可能
//是0或者16
if ((e.hash & oldCap) == 0) {
//代表是在0-16里面
//所以新的数组还在里面，就不用迁移
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}else {
//节点的hash是可以在16之外的
//进行迁移
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
//hash&16判断比较小的数据
//位置不变
loTail.next = null;
newTab[j] = loHead;//loHead存储着hash…&16之后比较小
//节点集合
}
if (hiTail != null) {
//hash&16判断比较小的数据
//位置加上旧的数组长度
hiTail.next = null;
newTab[j + oldCap] = hiHead;//hiHead存储着hash&16之后比较大
//节点集合
}
}
}
}
}
return newTab;
}
从上面可以看出，hashMap在进行扩容的时候，会对长度进行原来2倍的扩充，并且对table[index] 元素上面的链表进行迁移，这里注意，因为table[index]元素里面的单链表，有可能会有高的hash值(超过旧的数组长度为高)和低位的hash值,那么我们就要把低位和高位分别存在一个链表集合中，这时候源码是用(e.hash & oldCap) == 0来区分的高低位置的。以16为例，二进制为0...01000,所以&它的值要么是0，要么是16，并且用loHead和hiHead存储起来。所以，扩容之后的index要么是原来的，要么是加上+旧的长度length
3、Hashmap结构图(红黑树后面再讲解)
图1.png
这图就很好的表现了hashMap的数据结构，当key的hash的值相等的时候，它采取尾接法，形成一条单链表.
4、put过程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
@param evict 如果为false，则表处于创建模式。
如果为true的话，就删除最久没使用的，
这个是用在LinkedHashMap里面的
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断当前的table是否为空，为空的话初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//(n-1)&hash 想当于hash%n 随机分布到0-15
tab[i] = newNode(hash, key, value, null);//当前的table[i]里面没有链表，初始化
else {
//当前table[i]存在节点
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))){
//如果要插入的节点已经存在，且key相等，赋值给e
e = p;
}else if (p instanceof TreeNode){
//如果table[i]里面已经有红黑树，则插入红黑树，并进行旋转的操作
//如果有相同hash和相同key的话，就返回值
//具体请看下一篇博文红黑树，里面有具体的讲解
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
}else {
//单链表，往下查找并插入节点 尾插法
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//找到null的节点，进行插入
p.next = newNode(hash, key, value, null);
//如果这个大于等于8，则把单链表变成红黑树
//这里你可能有个疑问，8-1不是等于7吗？
//那是因为(binCount是从下标0开始的！！！！)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))){
//往下找，找到相同的key节点,则break结束循环
break;
}
p = e;
}
}
if (e != null) { // existing mapping for key
//e不为null，则说明有相同的节点，则修改value的值
V oldValue = e.value;
//由于put操作的时候，onlyIfAbsent传的是false
//则旧的值终会被替换
/**@param onlyIfAbsent 代表着是否保留旧的value
**/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//afterNodeAccess 是一个回调方法，回调相同key的节点
/**@link LinkedHashMap有用到这个**/
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//结构修改的次数加1 迭代器 failfast
//size 加1之后判断是否超出预期的容量值
if (++size > threshold){
//进行扩容
resize();
}
afterNodeInsertion(evict);//也是LinkedHashMap用到的.
//根据Lru算法来删除最久没使用的
//节点
return null;
}
java8 put流程图.png
从put过程可以看出，判断table是否为空，若为空，则执行resize方法初始化table数组，如果table[i = (n-1)&hash]的值为空，则初始化一个链表节点,如果不为null，则判断头节点是否和要put的节点key相等，如果不等，就判断链表是否被红黑树化，需要搜索红黑树查找该key值是否已存在；链表未被树化，且头节点key值与新增key值不同，需要遍历链表查找该key值是否存在。如果不存在，则插入，这里需要注意的是，当链表>=8的时候，则转化成红黑树
上面的判断逻辑中，不管是哪一种，只要key值已存在，则赋值给e，因此在后面判断e是否为null，若不为空，则表示已存在，根据策略决定是否覆盖原值
如果key值不存在，需要将modCount自增1，然后将size自增，判断大小是否超过阈值，是，则通过resize方法double原table数组的容量。
网友评论