源码解析-深刻理解Hash HashTable HashMap原理及数据hash碰撞问题

た入场券 2022-04-11 12:18 270阅读 0赞

### HashMap ###

*  前言
 *  Hash
 *  HashTable
 *   *  开地址法
     *   *  线性探测法
         *  平方探测法
         *  双重散列探测法
     *  拉链法
     *  哈希表优势
 *  HashMap
 *   *  变量介绍
     *  初始容量和负载因子
     *  红黑树和链表转化
     *  HashMap内部数据结构
     *  构造方法
     *  HashMap内部哈希算法
     *  存储-put
     *  获取-get
     *  快速存取实现原理及保证key的唯一性
     *  HashMap容量为什么总是2的n次方
     *  为什么要通过&(与运算)计算下标值

# 前言 #

Map接口应该是在开发中每天都可能会接触的了，它给我们快速存取数据提供了一种解决途径，尤其是它的一个子类HashMap；为什么这么说呢？我们知道除了Map这种数据结构存取数据外，我们可能还会用到其它的数据结构来做这件事，比如数组和链表；但是它们俩并不完美，数组是一种寻址方便，插入删除不容易的数据结构；链表是寻址困难，插入删除容易的数据结构

而HashMap能综合两种数据结构的特点，其实在Java中几乎所有的数据结构都会用数组或链表，或者两者结合来实现的；HashMap也不例外，因为它的底层实现是一个数组，不过数组的每一项在遇到数据碰撞的时候会扩展成一条链表（jdk1.8后有所不同）

# Hash #

可以看到HashMap比Map多了Hash这四个字母，音译为哈希，中文意思是散列，这么命名是因为HashMap内部是通过哈希算法来计算key-value的存储位置

这里提到了哈希这个概念，那到底是什么意思呢？在刚学Java的时候被这个东西搞得云里雾里的，很烦；其实Hash就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法（Hash算法），变换成固定长度的输出，该输出就是散列值（Hash值）。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

像Java里的hashCode() 方法就是一个Hash的过程

说到这里你是不是想到什么？没错，就是MD5加密，它的全称是Message-Digest Algorithm 5，即信息-摘要算法 5，它是哈希算法的一种实现；还有其它实现比如MD4和SHA-1；

这三种是应用于加密的Hash算法，当然还有用于查找的Hash函数，比如：加法Hash，位运算Hash，乘法Hash（String的hasCode就是这种方式），除法Hash，查表Hash，混合Hash等

# HashTable #

哈希的应用之一就是哈希表，也叫散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法，有寻址容易，插入删除也容易的特点

哈希表是根据关键码值而直接进行访问的数据结构，它的本质是一个数组，数组中每一个元素称为一个桶，桶中存放的是键值对；它的工作原理是：

*  根据给定的key通过哈希函数计算出哈希值
 *  将哈希值进行位运算后对数组长度取余，结果作为数组的下标
 *  最后将键值对存放在该下标的桶中

int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;

但是这里会有一个常说的碰撞问题（或者说冲突），因为两个不同或多个不同的key是有可能得到相同的下标值的，即映射到了同一个桶上；这有点像我们生活中使用新华字典的情况，比如新和薪两个字的拼音完全相同，这时候你通过xin查找页数索引的值是一样的，这就是碰撞了；解决这种冲突常见的两种方式有open hashing，即拉链法；另一种是closed hashing，即开地址法(opened addressing)

## 开地址法 ##

它的原理就是通过探测法寻找哈希表空闲地址然后插入，这就跟你买电影票一样，你想买的位置被别人买去了，那你就只能去买剩下的位置了

**举例**：比如在长度为11的哈希表中，下标为5,6,7的位置处已存放了三个关键字60，17，29，哈希函数是h(k) = k （哈希函数实现有很多种），下标值index(k) = h(k) mod 11；现在有一个关键字38需要存放，通过计算可以得到下标是5，显然这是冲突了，因为下标5的位置已经有关键字了

这时候就需要用探测法去寻找空闲地址，几种常用的探测序列法：线性探测法、平方探测法、随机探测法、伪随机探测法、双重散列探测法

### 线性探测法 ###

这时候通过线性探测法去计算新的下标值，涉及到的公司是 f(i) = i，index(k,i)= ( h( k ) + f (i) ) % 11，每次i从0开始尝试：

*  i=0时，下标是5，不符合
 *  i=1时，下标是6，不符合
 *  i=2时，下标是7，不符合
 *  i=3时，下标是8，该位置元素是空，符合，探测结束

这种方法有一个很严重的问题就是很容易造成数据扎堆现象，这样会把哈希表变成线性表，影响性能，违背了散列函数的初衷

### 平方探测法 ###

这里面的 f(i) = i²，继续从0开始尝试：

*  i=0时，下标是5，不符合
 *  i=1时，下标是6，不符合
 *  i=2时，下标是9，该位置元素是空，符合，探测结束

### 双重散列探测法 ###

计算公式是index(k,i) = ( h(k) + i \* h1(k) ) ％ 11

该方法使用了两个散列函数 h(k) 和 h1(k)，这就是双重散列的由来。定义 h1(k) 的方法较多，但无论采用什么方法定义，都必须使 h1(k) 的值和 m 互素；该方法是开地址法里最好方法之一

## 拉链法 ##

它的原理是每当发送数据冲突的时候，将这些数据链接在同一个单链表的数据结构中，这就像电影院里某个坐标处它不是一个座位，而是一个包间，里面有很多位置坐；HashMap包括HashSet都是采用的拉链法来解决哈希冲突的，如图：

![在这里插入图片描述][E6_8B_89_E9_93_BE_E5_93_88_E5_B8_8C_E8_A1_A8.jpg]

可以看出，左边是一个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素

## 哈希表优势 ##

我们平常使用数组或者链表存储数据的时候，一旦存储的数据量非常大的时候，这时候想查找某个元素是否存在就会变得很困难，因为它们总是需要循环进行比较

举例：现在有一个数组int\[\] t = \{4,5,9,13\}，现在判断元素13是否存在于这个数组中，那就需要循环遍历

int[] t = {4,5,9,13}
    for(int i=0; i<t.length; i++){
    	if(t[i] == 13){
    		System.out.println("find 13");
               	 return;
    	}
    }

这样就需要遍历4次才能找到，时间复杂度是O(n)；链表同理

现在使用哈希表来存放，假定哈希函数是

h(key) = key % 3;

要想判断13是否存在于哈希表中，我们只需要计算13的哈希值h(13) = 13 % 3 = 1（存的时候也是根据哈希值存的）；然后就判断哈希表的下标为1的位置元素是否等于13就行了；这里我们只需要查找一次，时间复杂度是O(1)，时间主要消耗在hash上

如果受到了哈希冲突攻击（基于哈希冲突的拒绝服务攻击），导致所有hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(1+n)，性能会急剧下降  
![在这里插入图片描述][799055-20161226145358554-108974646.png]

一般来说影响数据碰撞量的因素有三个：

*  哈希函数是否均匀
 *  处理冲突的方法
 *  哈希表的加载因子

# HashMap #

Map是一个key-value映射的接口，其中key不允许重复，value可以是相同的值；HashMap实现了该接口，是线程不安全的实现，在内部以Entry的形式保存key和value；同时HashMap继承自AbstractMap，它是一个抽象类，实现了Map接口，且对其中的方法提供了实现，减少其它实现Map接口类的工作

**本文基于jdk1.8**

## 变量介绍 ##

该类提供了四个构造方法，在讲解构造方法前先介绍下内部的一些变量

*  int DEFAULT\_INITIAL\_CAPACITY = 1 << 4： 内部哈希表初始容量，值为16，值必须是2的幂次方
 *  int MAXIMUM\_CAPACITY = 1 << 30：哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题
 *  float DEFAULT\_LOAD\_FACTOR = 0.75f：默认的负载因子，因此初始情况下，当键值对的数量大于 16 \* 0.75 = 12 时，就会触发扩容
 *  int TREEIFY\_THRESHOLD = 8：这个值表示当某个桶中，链表长度大于 8 时，将链表转化成红黑树；如果哈希函数不合理，导致过多的数据碰撞，即使扩容也无法减少箱子中链表的长度，因此将链表转换成红黑树
 *  int UNTREEIFY\_THRESHOLD = 6：当哈希表在扩容时，如果桶中的链表长度小于 6，则会由树重新退化为链表
 *  int MIN\_TREEIFY\_CAPACITY = 64：即哈希表中的桶数量要大于64才会考虑将链表转换成树，也是避免在小容量的时候进行不必要的转换
 *  Node<K,V>\[\] table：存放元素的数组，容量总是2的幂次方
 *  Set<Map.Entry<K,V>> entrySet：存放具体元素的集合
 *  int size：HashMap中键值对的数量
 *  int modCount：扩容或者结构更改的计数器
 *  int threshold：HashMap进行扩容的阈值，当实际大小超过该值就会进行扩容
 *  float loadFactor：实际负载因子

## 初始容量和负载因子 ##

这是两个影响哈希表性能的重要参数

初始容量为什么是16而不是12或者10等更小的值，是因为越小出现数据碰撞的几率会越大，不符合均匀分布的原则，同时也是考虑到空间使用效率没有取更大的值（下方会给出具体原因）

负载因子是哈希表在进行扩容前能达到多满的程度，它用来衡量哈希表的 使用 程度

*  负载因子越大：意味着哈希表被装填的越满，越容易导致冲突，性能也就越低；对于一个使用拉链法的链表（比如HashMap）此时查找一个元素的时间复杂度是O(1+n)，n是链表长度，虽然空间利用充分，但是查询效率就变低
 *  负载因子越小：意味着哈希表中的数据越松散，需要开辟更多的空间，虽然查询效率高了，但是造成空间浪费；并且哈希表进行扩容的频率会变高，重哈希过程中所有元素的位置可能变化，影响性能

所以系统给出0.75是一个空间和时间上的综合考虑，如果没有特殊需求自己不用修改

## 红黑树和链表转化 ##

学概率论的应该知道一个公式：泊松分布  
![在这里插入图片描述][1470319630.png]

在理想的随机hashCode下，容器中节点的分布遵循泊松分布，我们计算下（当负载因子为0.75时，λ=0.5）

其中的 k! 在数学中是阶乘的意思 比如 5! = 5 \* 4 \* 3 \* 2 \* 1；e是一个自然常数，值是2.71828…；p表示事件k发生的概率

* k=0:    0.60653066
     * k=1:    0.30326533
     * k=2:    0.07581633
     * k=3:    0.01263606
     * k=4:    0.00157952
     * k=5:    0.00015795
     * k=6:    0.00001316
     * k=7:    0.00000094
     * k=8:    0.00000006

这就是为什么TREEIFY\_THRESHOLD 值定为8，因为在正常情况下出现这种现象的几率小到忽略不计。一旦出现，几乎可以认为是哈希函数设计有问题导致的，总是出现相同的hash值，也就是说正常情况下红黑树和链表的转换很难发生

--------------------

## HashMap内部数据结构 ##

在jdk1.8之前，HashMap底层采用**数组+链表**实现，即使用拉链法处理数据碰撞，即对key进行hash后的索引如果相同，就放在一个链表中，如图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwOTkzNTk1_size_16_color_FFFFFF_t_70]

虽然这能很好的解决数据碰撞的问题，但是随着链表中的元素越来越多，数据查找的时间复杂度为O(1+N)，查询效率将会变低，显然这违背了HashMap的设计初衷；所以从jdk1.8开始，HashMap底层采用**数组+链表/红黑树**实现，当同一个桶中的键值对或者说链表中的节点过多时，超过8个后链表转换为红黑树，如图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwOTkzNTk1_size_16_color_FFFFFF_t_70 1]

可以看出来数组中的每个桶中可能存放的是链表也可能是红黑树

其中的Node<K,V>是HashMap的内部类，实现了Map.Entry<K,V>；它本质上是一个链表，内部维护了下一个节点

//单向链表，因为只维护了下一个节点
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;//hash值
            final K key;
            V value;
            Node<K,V> next;//下一个节点，很重要，hash值相同的键值对就是通过这个next进行关联的
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    	//判断两个node是否相等，如果两个node的k和v都相等即返回true
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

其中的TreeNode是红黑树的实现，

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
            TreeNode<K,V> parent;  // 父节点
            TreeNode<K,V> left;//左节点
            TreeNode<K,V> right;//右节点
            TreeNode<K,V> prev;    // 上一个同级节点
            boolean red;
            TreeNode(int hash, K key, V val, Node<K,V> next) {
                super(hash, key, val, next);
            }
            ......
    }

从上面可以看到HashMap的基本结构是一个Node<k,v>\[\]，在上面变量介绍一节中有介绍，这样我们大概能清楚HashMap的实现原理了：内部维护了每一个元素都是链表的数组，其中元素是Node，它本质上是一个单向链表；当添加一个键值对（key-value）时，先计算key的hash值，进而确定要插入到数组中的索引，然后添加到数组中；如果该索引处已经存放了一个元素A，那就将其添加到A的后面；这两个元素虽然都处于数组的同一个位置，但是它们两形成了链表；当链表太长，就将链表转换成红黑树，提高查询效率

--------------------

## 构造方法 ##

*  HashMap()
    
        public HashMap() {
                this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
            }
    
    这是我们用的比较频繁的一个构造方法了，没有特殊的写法，所有变量均是默认值
 *  HashMap(int initialCapacity)
    
        public HashMap(int initialCapacity) {
                this(initialCapacity, DEFAULT_LOAD_FACTOR);
            }
    
    该构造方法传入一个指定容量，然后调用另外一个重载的构造方法
 *  HashMap(int initialCapacity, float loadFactor)
    
        public HashMap(int initialCapacity, float loadFactor) {
                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);
            }
    
    该构造方法指定一个容量值和一个负载因子；从方法内部逻辑可以看出容量值小于0将会抛出异常，大于最大容量值就重置为最大值；负载因子 如果小于等于0或者是个非法数字也将会抛出异常；最后一句代码的意思是计算HashMap下次扩容时的阈值，也就是说HashMap并不会等被填满时才会进行扩容，而是达到这个阈值时就开始提前扩容
    
    其中tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值
    
        static final int tableSizeFor(int cap) {
            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;
        }
    
    其中>>>是无符号右移运算符，具体运算方式可参考博主的[从源码解析-Android数据队列之双端队列ArrayDeque][-Android_ArrayDeque]
 *  HashMap(Map<? extends K, ? extends V> m)
    
        public HashMap(Map<? extends K, ? extends V> m) {
                this.loadFactor = DEFAULT_LOAD_FACTOR;
                // 将m中的所有键值对添加到HashMap
                putMapEntries(m, false);
            }
    
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
                int s = m.size();
                if (s > 0) {
                    if (table == null) { // pre-size
                    	//数组没有初始化 重新计算阈值
                        float ft = ((float)s / loadFactor) + 1.0F;
                        int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                                 (int)ft : MAXIMUM_CAPACITY);
                        if (t > threshold)
                            threshold = tableSizeFor(t);
                    }
                    else if (s > threshold)
                       //已经初始化 如果大小大于阈值 需要扩容
                        resize();
                    //将m中所有键值对添加到本HashMap中
                    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                        K key = e.getKey();
                        V value = e.getValue();
                        putVal(hash(key), key, value, false, evict);
                    }
                }
            }
    
    该构造方法将会构造一个与指定 Map 具有相同映射的 HashMap

## HashMap内部哈希算法 ##

HashMap内部获取每个key的哈希值是通过内部的hash方法实现的

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

*  先判断key是否为null，如果是返回0
 *  先通过key的hashCode()方法获取hash值，该方法每个类对象都拥有
 *  将hash值无符号右移16位，然后与hash值进行异或运算得到最终的hash值

这里hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现，由于hashMap内部数组长度总是 2 的幂次方，通过右移可以使低位的数据尽量的不同，从而使hash值分布尽量均匀

## 存储-put ##

接下来看下HashMap是如何保存键值对的  
HashMap对外提供一个put方法，接收key和value

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }

这里没有具体实现，只是调用内部hash方法得到key的hash值，然后调用putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; 
            Node<K,V> p; 
            int n, i;
            
            //第一步
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
     
     		//第二步
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                //第三步
                if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                	//第四步
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                	//第五步
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            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))))
                            break;
                        p = e;
                    }
                }
                //第六步
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //第七步
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

putVal方法是存储的核心，我这里把它分为七段进行分析

*  第一步  
    如果table为null或者length为0，就进行扩容，并获取长度n = tab.length
 *  第二步  
    先通过i = (n - 1) & hash 计算key在数组中的索引，其中n是数组的长度，hash是key的哈希值， (n - 1) & hash 相当于hash%n，不用后者是因为&（与运算）比%（取余，HashTable使用%计算下标）的效率高，这是HashMap在速度上的一个优化  
    获取数组中指定索引处的链表中第一个结点Node，如果该结点为null，说明该桶中没有元素，那就直接新建结点，然后转向第七步  
    如果不为null，说明这个桶里已经有元素了，并将这个结点赋值给变量p，然后转向else分支
 *  第三步  
    这一步需要判断好几个条件
    
     *  p.hash == hash：第二步获取的结点中的key的hash值与参数key的hash值是否相等
     *  (k = p.key) == key： 通过 == 判断结点p的key和参数key是否相等
     *  (key != null && key.equals(k))：通过equals方法判断两个key是否相等  
        如果三个条件判断返回true，即表示结点p的key和参数key相等（这个相等是通过hash值，== ，及equals相结合判断的），就将结点p赋值给结点e，然后进入第六步；如果返回false，进入第四步
 *  第四步  
    这一步判断取出来的p是不是TreeNode类型，即是不是红黑树；如果是红黑树，就直接插入键值对并将返回结果赋值给e（TreeNode间接继承Node）；否则进入第五步
 *  第五步  
    在一个死循环中不断的从结点p中取出下一个结点，对这个结点有两个判断：  
    第一个：直到最后一个结点取出来，然后通过参数new出一个新结点并链接到结点p的下一个结点中，接下来判断binCount >= TREEIFY\_THRESHOLD - 1，即链表中结点数量如果大于等于8，将链表转为红黑树，最后跳出循环  
    第二个：这一步有三个判断条件，意思就是判断当前结点的key与参数key是否相等，如果相等，说明你put了一个相同key的键值对，那就退出循环
 *  第六步  
    这里判断结点e是否为null，e的值由前面三步进行赋值；如果不为null，说明在链表或者树中找到了一个结点，其key与参数key相同，那就将参数value替换结点中原value，最后返回原value值结束该方法
 *  第七步  
    走到这一步了说明是new了一个新的结点并插入到数组指定索引（i = (n - 1) & hash）的链表中  
    这里会将结构更改计数器+1，如果数组大小超过了扩容阈值就进行扩容  
    最后通过afterNodeInsertion进行回调

## 获取-get ##

存储实现看完了，接下来看看如何获取值

public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

这里先通过getNode方法获取结点，如果结点为null，就返回null；否则返回结点的value

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; 
            Node<K,V> first, e; 
            int n; 
            K k;
            //第一步
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                //第二步
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                //第三步
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

相较于存储而言，取值就简单多了

*  第一步：数组是否为null，数组长度是否大于0，根据参数计算出的下标并获取的链表中第一个结点first是否为null
 *  第二步：根据老三套判断结点first的key和参数key是否相等，相等就返回结点first
 *  第三步：走到这里说明链表中第一个结点不符合，那就继续往下寻找下一个结点
    
     *  如果下一个结点e不为null继续
     *  如果结点e是树，那就通过getTreeNode返回该结点
     *  最后就是一个死循环，不断的寻找该链表中的下一个结点，并判断key是否相等，如果相等就返回结点e，并结束该循环

## 快速存取实现原理及保证key的唯一性 ##

看完以上操作后，你可看明白了HashMap是如何实现快速存取及保证key的唯一性的吗？

HashMap内部采用哈希表来管理所有元素，元素可能是一个链表，也可能是一个红黑树；每个元素通过hash算法决定自己在哈希表中的存储位置，这样判断某个结点的位置的时间复杂度是O(1+n)，n是链表长度（n<8），以此达到快速存取的目的

HashMap通过key的哈希值，==，equals方法三种方式确定唯一key，具体逻辑是只要两个key的哈希值相等且 == 和equals之间有一个符合，那就说明两个key是相同的

## HashMap容量为什么总是2的n次方 ##

阅读HashMap的源码可以知道其保存数据的底层数组长度永远是2的n次方，为什么要这样规定呢？

要知道HashMap内部数据结构是一个数组+链表+树，要实现的效果就是快速存取值，那就要求数组中的每个桶中尽量只放一个键值对，这样效率是最高的，不管查询还是存储都不需要循环遍历链表了，时间复杂度永远是O(1)

这样就要求在存值的时候键值对能存放的越均匀越好，也就是减少数据碰撞发生的概率，HashMap内部机制是使用hash方法对key的哈希值重新计算，以防止质量低下的hashCode()函数实现；使用&（与运算）使得node对象的插入位置尽量分布均匀

其实这两点都是基于容量是2的n次方的，前者在 【HashMap内部哈希算法】这一节说过，后者这节来解释下

*  我们先看下当数组长度为16，且哈希值hash从0取到15，计算下标方法 index=(n-1)&hash
    
    <table> 
     <thead> 
      <tr> 
       <th>hash</th> 
       <th>length-1</th> 
       <th>index</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>0</td> 
       <td>15</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>1</td> 
       <td>15</td> 
       <td>1</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>15</td> 
       <td>2</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>15</td> 
       <td>3</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>15</td> 
       <td>4</td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td>15</td> 
       <td>5</td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td>15</td> 
       <td>6</td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td>15</td> 
       <td>7</td> 
      </tr> 
      <tr> 
       <td>8</td> 
       <td>15</td> 
       <td>8</td> 
      </tr> 
      <tr> 
       <td>9</td> 
       <td>15</td> 
       <td>9</td> 
      </tr> 
      <tr> 
       <td>10</td> 
       <td>15</td> 
       <td>10</td> 
      </tr> 
      <tr> 
       <td>11</td> 
       <td>15</td> 
       <td>11</td> 
      </tr> 
      <tr> 
       <td>12</td> 
       <td>15</td> 
       <td>12</td> 
      </tr> 
      <tr> 
       <td>13</td> 
       <td>15</td> 
       <td>13</td> 
      </tr> 
      <tr> 
       <td>14</td> 
       <td>15</td> 
       <td>14</td> 
      </tr> 
      <tr> 
       <td>15</td> 
       <td>15</td> 
       <td>15</td> 
      </tr> 
     </tbody> 
    </table>
    
    从这个表可以看出不会出现数据碰撞的情况
 *  当数组长度为15时，且哈希值hash从0取到15，计算下标方法 index=(n-1)&hash
    
    <table> 
     <thead> 
      <tr> 
       <th>hash</th> 
       <th>length-1</th> 
       <th>index</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>0</td> 
       <td>14</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>1</td> 
       <td>14</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>14</td> 
       <td>2</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>14</td> 
       <td>2</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>14</td> 
       <td>4</td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td>14</td> 
       <td>4</td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td>14</td> 
       <td>6</td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td>14</td> 
       <td>6</td> 
      </tr> 
      <tr> 
       <td>8</td> 
       <td>14</td> 
       <td>8</td> 
      </tr> 
      <tr> 
       <td>9</td> 
       <td>14</td> 
       <td>8</td> 
      </tr> 
      <tr> 
       <td>10</td> 
       <td>14</td> 
       <td>10</td> 
      </tr> 
      <tr> 
       <td>11</td> 
       <td>14</td> 
       <td>10</td> 
      </tr> 
      <tr> 
       <td>12</td> 
       <td>14</td> 
       <td>12</td> 
      </tr> 
      <tr> 
       <td>13</td> 
       <td>14</td> 
       <td>12</td> 
      </tr> 
      <tr> 
       <td>14</td> 
       <td>14</td> 
       <td>14</td> 
      </tr> 
      <tr> 
       <td>15</td> 
       <td>14</td> 
       <td>14</td> 
      </tr> 
     </tbody> 
    </table>
    
    可以看到事实就是这么残酷，数据碰撞发生的很频繁，而且有的位置永远没有数据，造成空间浪费，存取效率变低
 *  当数组长度为33时，且哈希值hash从0取到15，计算下标方法 index=(n-1)&hash
    
    <table> 
     <thead> 
      <tr> 
       <th>hash</th> 
       <th>length-1</th> 
       <th>index</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>0</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>1</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>8</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>9</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>10</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>11</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>12</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>13</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>14</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>15</td> 
       <td>32</td> 
       <td>0</td> 
      </tr> 
     </tbody> 
    </table>
    
    你没看错，这里更加惨不忍睹，哈希表退化成链表，所有键值对全部存放在同一个桶里

当数组长度是其它值的时候，大家可以去试试，数据碰撞发生的很频繁，只有长度为2的n次方时，且哈希函数合理的情况下才能尽量避免数据碰撞的发生

其实它的计算原理是：当容量为2的n次方时，在进行(n-1)&hash运算时，其n-1的值的二进制的每一位都是1，比如16-1的二进制是1111，64-1的二进制是111111；那么与hash进行与运算时，最后得到的结果就是hash值自己了，这样肯定就不会得到重复的下标值了，除非hash值重复

## 为什么要通过&(与运算)计算下标值 ##

可能有的人疑问了，既然(n-1)&hash永远等于hash自己，那还进行这个运算干嘛，直接取hash做下标得了；但是你要注意一个情况，hash值是有可能大于数组长度的，这时候你怎么存呢？所以就要进行与运算，在高位取0

比如容量是16，hash值是20，那么(n-1)&hash等于

0 1 1 1 1
    1 0 1 0 0

最终结果就是100=4，这样就能避免数组越界的问题

还有一个原因就是上面提到的&(与运算)比%运算速度快，两者等值不等效

[E6_8B_89_E9_93_BE_E5_93_88_E5_B8_8C_E8_A1_A8.jpg]: /images/20220411/7e69f333ad67490da5e1447c05d8eff5.png
[799055-20161226145358554-108974646.png]: /images/20220411/ac1a41479f294c0ab16dfbe501750457.png
[1470319630.png]: https://o8ouygf5v.qnssl.com/1470319630.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwOTkzNTk1_size_16_color_FFFFFF_t_70]: /images/20220411/448e5a25ab3b4cffaf89a193ba65549b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwOTkzNTk1_size_16_color_FFFFFF_t_70 1]: /images/20220411/d817bdd8a186423eafc89abefb3480ba.png
[-Android_ArrayDeque]: https://blog.csdn.net/qq_30993595/article/details/80799444