HashMap的简要分析

HashMap底层数据结构

HashMap底层的数据结构式哈希表,也叫做散列表,就是一个数组,每个数组中的元素是一个单向链表(jdk8之后满足一定条件后会由单向链表变成红黑树),哈希表有点像书架,一个书架上有很多层,每层可以放书籍。哈希表中的数组具有较高的随机访问效率,数组中的链表具有较高的插入删除效率,所有说哈希表是集数组和链表的优点于一身。

下面代码创建了一个HashMap对象,向里面添加了一些元素

HashMap<Integer, String> map = new HashMap<>();
map.put(1009, "parker");
map.put(1025, "paul");
map.put(1010, "james");
map.put(1026, "nash");
map.put(1042, "jordan");
map.put(1043, "kobe");

根据上面代码画出存储结构图(注:下图只是为了方便理解,实际存储情况是要取决于hash值的计算)

Hash碰撞

当使用HashMap的put方法添加数据的时候,会根据key计算该数据要存放的数组下标,对于两个不同数据中的key,计算出的下标可能是相同的,这个叫做hash碰撞。在HashMap中使用了链表算法的方案解决的该问题,即两个数据有相同hash值的时候会放到一个链表中。

HashMap的put流程

比如执行下面代码:

map.put(1001,"monkey1024");

调用key1001的hashCode()获取hash值,根据hash值计算下标i,访问哈希表中下标是i的元素table[i],此时会出现下面几种情况

  1. table[i]为null,此时会创建一个新的节点对象Node,其内存地址放入到table[i]中。Node中存储了hash值,key值,value值,next下一个节点的内存地址值。
  2. table[i]不为null,且table[i]中链表的长度小于8,此时会遍历table[i]中单向链表的每个节点对象,倘若某个节点的key与1001 equals相等,则用monkey1024替换掉该节点中之前的value值。
  3. table[i]不为null,且table[i]中链表的长度小于8,此时会遍历table[i]中单向链表的每个节点对象,倘若查找到最后的节点n时,也没有找到key与1001 equals相等的节点,此时创建一个新的节点,放到n的后面
  4. 将节点对象Node放入到链表中之后,如果table[i]中链表的长度大于等于8,且table[i]长度小于64,此时会对table进行扩容,扩容到原来长度的2倍,然后再重新计算Node在table中的位置,这里扩容的目的是为了减少hash碰撞的几率从而提高运行效率。
  5. 将节点对象Node放入到链表中之后,如果table[i]中链表的长度大于等于8,且table[i]长度大于等于64,此时会将该链表中的数据转成红黑树。

 

为什么链表长度大于8的时候才会转换为红黑树?

红黑树占有的空间是链表的2倍,根据泊松(poisson)分布推算出8是最合适的,说白了就是经过了空间和时间的权衡。当一个数组中的节点数小于6的时候,会将红黑树转换为链表。对应源码中的UNTREEIFY_THRESHOLD

HashMap中默认初始长度

在HashMap中默认的数组长度DEFAULT_INITIAL_CAPACITY是16,我们可以自己手动设置数组长度,不过必须是2的n次方。对应的源码

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

为什么集合初始化的长度是2的n次幂

主要是为了让哈希表散列的更加均匀,减少hash碰撞。我们调用put方法向HashMap中存放数据的时候,需要根据key计算hash值,然后再根据hash值确定数组的下标。该算法可以通过取余数进行运算:hash % length,但是该算法不如位运算符效率高,所以hashmap使用了(length – 1) & hash的方式进行计算下标。而要确保两个算法相等的前提就是length必须是2的n次方。2的n次幂对应的2进制是1后面n个0,再减1的话就是n个1。此时进行&按位与操作可以让哈希表散列的更加均匀。

位与运算规则:有0则0

下面通过代码演示散列均匀,这里定义的length是2的4次幂,此时计算出的下标值是不同的

int length = 16;//长度
int hash1 = 2;//第一个hash值
int hash2 = 3;//第二个hash值

//打印的结果是计算之后的数组下标,这里是不同的
System.out.println(hash1 & (length - 1));//2
System.out.println(hash2 & (length - 1));//3

这里修改length是17,并不是2的n次幂,计算出的下标值是相同的,出现了hash碰撞

int length = 17;//长度
int hash1 = 2;//第一个hash值
int hash2 = 3;//第二个hash值

//打印的结果是计算之后的数组下标,这里是相同的
System.out.println(hash1 & (length - 1));//0
System.out.println(hash2 & (length - 1));//0

创建HashMap对象长度不是2的n次幂的情况

我们再创建HashMap对象的时候可以指定长度,长度需要在该范围内(0, 1<<30],哈希表中数组长度最大值是1<<30。倘若传入的长度并不是2的n次幂时,HashMap会通过tableSizeFor方法找到离比我们传入长度最近且较大的2的n次幂的值,比如传入14,那么会赋值长度为16,传入17,会赋值长度为32。

tableSizeFor源码

static final int tableSizeFor(int cap) {
    int n = cap - 1;//这里减1的目的是排除我们赋值正好是2的n次方的情况
    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;
}

位或运算:有1则1

这里假设传入长度14,我们来分析下上面方法是如何执行的,首先14减一变成了13,13对应的2进制是1101。

经过n |= n >>> 1;运算之后,n的值是15,二进制值是1111

1101 
0110    1101 >>> 1结果是0110
1111    上面经过位或运算之后,结果是1111,十进制是15

经过n |= n >>> 2;

1111
0011    1101 >>> 2 结果是0111
1111    上面经过位或运算之后,结果是1111,十进制15

后面的这些运算,n的值都是15

 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;

最后再执行下面语句的时候,就会计算出返回值是16了

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

HashMap长度什么时候进行扩容

在HashMap中有一个负载因子(DEFAULT_LOAD_FACTOR)默认值是0.75f,当哈希表的长度超过length * loadFactor时就会扩容,16 * 0.75=12,即当哈希表中的数组长度超过12的时候就会扩容。负载因子表示哈希表中的稀疏程度,过大的话,导致查询效率降低,太小的话会导致数据存的分散,浪费内存。0.75是经过大量的计算得出的一个值,所以不建议我们修改。当使用HashMap的时候,可以根据如下公式对要放入的数据进行一个预估:

初始容量=数据数量/负载因子 + 1

然后将计算出来的初始容量传入到HashMap的构造方法中,这样可以减少扩容的操作。