HashMap集合

1.HashMap集合简介

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突**(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)**而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。！！！（这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。）

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。

2.HashMap集合底层的数据结构

2.1数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构：就是存储数据的一种方式。ArrayList LinkedList

在JDK1.8 之前 HashMap 由数组+链表数据结构组成的。

在JDK1.8 之后 HashMap 由数组+链表 +红黑树数据结构组成的。

2.2HashMap底层的数据结构存储数据的过程

存储过程如下所示：

使用的代码：

public class Demo01 {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("刘德华", 53);
        map.put("柳岩", 35);
        map.put("张学友", 55);
        map.put("郭富城", 52);
        map.put("黎明", 51);
        map.put("林青霞", 55);
        map.put("刘德华", 50);
    }
}

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。如下图所示。

但是这样的话问题来了，传统hashMap的缺点，1.8为什么引入红黑树？这样结构的话不是更麻烦了吗，为何阈值大于8换成红黑树？

JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

上述我们大概阐述了HashMap底层存储数据的方式。为了方便大家更好的理解，我们结合一个存储流程图来进一步说明一下：(jdk8存储过程)

说明：

1.size表示 HashMap中K-V的实时数量，注意这个不等于数组的长度。

2.threshold( 临界值) =capacity(容量) * loadFactor( 加载因子 )。这个值是当前已占用数组长度的最大值。size超过这个临界值就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍。

3.HashMap继承关系

HashMap继承关系如下图所示：

说明：

Cloneable 空接口，表示可以克隆。创建并返回HashMap对象的一个副本。
Serializable 序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。
AbstractMap 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

补充：通过上述继承关系我们发现一个很奇怪的现象，就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构。

据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

4.HashMap集合类的成员

4.1成员变量

1.序列化版本号

private static final long serialVersionUID = 362498820763181265L;

2.集合的初始化容量( 必须是二的n次幂 )

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

HashMap构造方法还可以指定集合的初始化容量大小：

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

根据上述讲解我们已经知道，当向HashMap中添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。 HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法。

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算(

在计算机中，求余运算（也称为模运算）通常比位移运算效率低，这主要是因为求余运算涉及到更多的计算和处理步骤。求

余运算需要进行除法操作，而除法操作通常比位移操作更复杂和耗时。除法操作涉及到一系列的除法、乘法和减法等算术运算，而位移运算只是简单地将二进制数的位向左或向右移动。

除法操作的复杂性导致了它的执行时间较长。在硬件层面上，除法运算通常需要更多的计算单元和时钟周期来完成，相对于位移运算来说，它需要更多的资源和时间。

另外，现代计算机架构中的指令集通常会对位移运算进行特殊优化，将其作为一种基本的操作进行支持，并提供专门的指令来执行位移操作。相比之下，求余运算不像位移运算那样常见，往往没有得到类似的特殊优化。

综上所述，尽管位移运算相对于求余运算在某些情况下可能更高效，但这并不意味着求余运算在所有情况下都低效。在实际编程中，我们应该根据具体的需求和情况选择合适的运算方式。

所以源码中做了优化,使用 hash&(length-1)，而实际上hash%length等于hash&(length-1)的前提是length是2的n次幂。

为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；

举例：

说明：按位与运算：相同的二进制数位上，都是1的时候，结果为1，否则为零。

例如长度为8时候，3&(8-1)=3  2&(8-1)=2 ，不同位置上，不碰撞；
例如长度length为8时候，8是2的3次幂。二进制是：1000
length-1 二进制运算：
  1000
-    1
---------------------
     111
如下所示：
hash&(length-1)
3   &(8    - 1)=3  
  00000011  3 hash
&   00000111  7 length-1
---------------------
  00000011-----》3 数组下标
hash&(length-1)
2 &  (8 -    1) = 2  
  00000010  2 hash
&   00000111  7 length-1
---------------------
  00000010-----》2  数组下标
说明：上述计算结果是不同位置上，不碰撞；

例如长度为9时候，3&(9-1)=0  2&(9-1)=0 ，都在0上，碰撞了；
例如长度length为9时候，9不是2的n次幂。二进制是：00001001
length-1 二进制运算：
  1001
-    1
---------------------
    1000
如下所示：
hash&(length-1)
3   &(9    - 1)=0  
  00000011  3 hash
&   00001000  8 length-1 
---------------------
  00000000-----》0  数组下标
hash&(length-1)
2 &  (9 -    1) = 2  
  00000010 2 hash
&   00001000 8 length-1 
---------------------
  00000000-----》0  数组下标
说明：上述计算结果都在0上，碰撞了；

注意：当然如果不考虑效率直接求余即可（就不需要要求长度必须是2的n次方了)

小结：

1.由上面可以看出，当我们根据key的hash确定其在数组的位置时，如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。

2.另一方面，一般我们可能会想通过 % 求余来确定位置，这样也可以，只不过性能不如 & 运算。而且当n是2的幂次方时：hash & (length - 1) == hash % length

3.因此，HashMap 容量为2次幂的原因，就是为了数据的的均匀分布，减少hash冲突，毕竟hash冲突越大，代表数组中一个链的长度越大，这样的话会降低hashmap的性能

4.如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字。

源代码如下：

//创建HashMap集合的对象，指定数组长度是10，不是2的幂
HashMap hashMap = new HashMap(10);
public HashMap(int initialCapacity) {//initialCapacity=10
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10
     if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}
  /**
   * Returns a power of two size for the given target capacity.
  */
    static final int tableSizeFor(int cap) {//int cap = 10
        int n = cap - 1;
        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)、首先，为什么要对cap做减1操作。int n = cap - 1;

这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。

下面看看这几个无符号右移操作：

2）、如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是 1（最后有个n+1的操作）。

这里只讨论n不等于0的情况。

注意：|（按位或运算）：运算规则：相同的二进制数位上，都是0的时候，结果为0，否则为1。

第一次右移：

int n = cap - 1;//cap=10  n=9
n |= n >>> 1;
  00000000 00000000 00000000 00001001 //9
| 
  00000000 00000000 00000000 00000100 //9右移之后变为4
-------------------------------------------------
  00000000 00000000 00000000 00001101 //按位异或之后是13

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如：

00000000 00000000 00000000 00001101

第二次右移 ：

 n |= n >>> 2;//n通过第一次右移变为了：n=13
  00000000 00000000 00000000 00001101  // 13
|
    00000000 00000000 00000000 00000011  //13右移之后变为3
-------------------------------------------------
  00000000 00000000 00000000 00001111 //按位异或之后是15

注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为00000000 00000000 00000000 00001101 ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如：

00000000 00000000 00000000 00001111 //按位异或之后是15

第三次右移 :

n |= n >>> 4;//n通过第一、二次右移变为了：n=15
  00000000 00000000 00000000 00001111  // 15
|
    00000000 00000000 00000000 00000000  //15右移之后变为0
-------------------------------------------------
  00000000 00000000 00000000 00001111 //按位异或之后是15

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中正常会有8个连续的1。如00001111 1111xxxxxx 。

以此类推

注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1（但是这已经是负数了。在执行tableSizeFor之前，对initialCapacity做了判断，如果大于MAXIMUM_CAPACITY(2 ^ 30)，则取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2 ^ 30)，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于MAXIMUM_CAPACITY。30个1，加1之后得2 ^ 30）。

请看下面的一个完整例子：

注意，得到的这个capacity却被赋值给了threshold。

this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10

3.默认的负载因子，默认值是0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

4.集合最大容量

//集合最大容量的上限是：2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;

5.当链表的值超过8则有可能会转红黑树(1.8新增)

 //当桶(bucket)上的结点数大于这个值时会转成红黑树
 static final int TREEIFY_THRESHOLD = 8;

如果面试也能这样说HashMap，那么就不会有那么多遗憾！（中）:https://developer.aliyun.com/article/1413689

如果面试也能这样说HashMap，那么就不会有那么多遗憾！（上）

HashMap集合

1.HashMap集合简介

2.HashMap集合底层的数据结构

2.1数据结构概念

2.2HashMap底层的数据结构存储数据的过程

3.HashMap继承关系

4.HashMap集合类的成员

4.1成员变量

热门文章

最新文章

相关课程

相关电子书