哈希表总结

分手后的思念是犯贱 2023-10-02 17:00 41阅读 0赞

**目录**

引言

一，哈希表概念

1.概念

2.初次简单模拟

3.模拟总结

二，哈希冲突（哈希碰撞）

1.概念

2.分析

初步分析：

避免冲突时的哈希函数设计：

常见的哈希函数：

3.解决

1.闭散列

2.开散列

三，模拟实现哈希桶（开散列）

模拟实现的准备工作

1.定义哈希表中的结点

2.构造方法

3.哈希地址的计算方法

1.操作之添加 / 插入

2.操作之获取key的value

3.操作 之 key存在返回key对应的value，key不存在返回默认值

4.操作之删除key

5.操作之是否包含key

6.操作之是否包含value

7.测试代码（模拟实现的全部代码）

四，总结

常见问题：

标准库中的扩容

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

## 引言 ##

>  *  **顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(![\\log\_\{2\}N][log_2_N])，搜索的效率取决于搜索过程中元素的比较次数**
>  *  **哈希表作为一个非比较的方法去查找和删除元素，这是和利用比较的方法最不同的地方，它的好处也正是在于不用比较，大大的降低了时间复杂（O(1)）**

## 一，哈希表概念 ##

### **1.概念** ###

> **不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函  
> 数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素**

### **2.初次简单模拟** ###

**模拟分析向该状态下的表格里插入和查找元素**

假设待插入的元素为红色单元格的数字，表格是要插入的地方（一个数组array）

**一一映射关系（HashFunc）：index = value % array.length**

> 插入元素：
> 
> 1.  计算带插入元素的在表格中的位置index
> 2.  将元素插入到表格中index的位置

> 查找元素：
> 
> 1.  查找这个元素在这个表格中可能存在的位置（有可能不存在）
> 2.  到相应位置去获取元素

### 3.模拟总结 ###

**可以发现在实际运用中，对于数组来说，插入和查找的时间复杂度就是O(1)**

**在上面的简单模拟中：**

1.  **存储元素的表格（或者说是数组）就是哈希表，也称散列表**
2.  **index所表示的就是这个元素的哈希地址**
3.  **映射关系（HashFunc）：index = value % array.length 这是哈希函数或者称为散列函数**

## 二，哈希冲突（哈希碰撞） ##

### 1.概念 ###

>  *  **在上面的模拟过程中，哈希展现了其精妙之处，但是也存在问题，借用上面的模拟，如果现在有一个数字是99，它的哈希地址和9的哈希地址是一模一样的，那么现在强行插入元素，之前的元素就会被替换掉，所以，就不能直接插入，因此，把这种冲突叫做哈希冲突（哈希碰撞）**
>  *  **简而言之就是，不同的元素通过哈希函数计算出来了相同的哈希地址，这些元素称为同义词**

### 2.分析 ###

#### 初步分析： ####

1.  通过了解可以发现，哈希表的容量往往是小于元素个数的，因此，可以说哈希冲突是必然发生的，只能说，我们设计的哈希函数要尽可能的要做到避免冲突
2.  我们可以把不发生哈希冲突理解为这个哈希函数的渐近线，而设计出来的哈希函数就是再精妙，它也是在无线逼近渐进线，而不是可以等于这个渐进线所在的值
3.  避免发生哈希冲突，哈希函数的设计思想

#### 避免冲突时的哈希函数设计： ####

>  *  **哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间**
>  *  **哈希函数计算出来的地址能均匀分布在整个空间中**
>  *  **哈希函数应该比较简单**

#### 常见的哈希函数： ####

> **1. 直接定制法**
> 
>  *  **取关键字的某个线性函数为散列地址：Hash（Key）= A\*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况** 
>  *  **使用场景：适合查找比较小且连续的情况**
> 
> **2. 除留余数法**
> 
>  *  **设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址**
> 
> **3. 平方取中法**
> 
>  *  **假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址**
>  *  **平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况**
> 
> **4. 折叠法**
> 
>  *  **折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址**
>  *  **折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况**
> 
> **5. 随机数法**
> 
>  *  **选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数**
>  *  **通常应用于关键字长度不等时采用此法**
> 
> **6. 数学分析法**
> 
>  *  **设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址**
>  *  **数学分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况**

### 3.解决 ###

#### 1.闭散列 ####

*  **闭散列：当发生哈希冲突时，从发生哈希冲突的位置开始寻找下一个空位置**
 *  **寻找空位置也有两种方法：**

**线性探测**

*  **当发生哈希冲突时，从发生冲突的位置开始依次往后寻找，如果找到了哈希表的末尾，在接着从头开始继续寻找**
 *  ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]
 *   **此时就需要添加两个标记，来对每个位置里是否有元素进行标记，有就是Exist，没有就是Empty，进行查找，当添加完成后，需要将这个位置的标记进行更改**
 *  **查找元素时，需要添加一个Delete的标记，因为存在一种情况（假设现在在上面这个数组当中查找9，我们需要计算相应的哈希地址去寻找，所以，去9号位置找，找到了并删除，第二次要找99，当来到9号位置时，却发现是空的，系统会自动判定，我们的数组当中没有99这个元素，但实际上有，只是因为发生了哈希冲突，我们将99这个元素放到了下一个空位置而已）因此，我们添加一个delete的删除标记，是为了告诉计算机，我们还有发生了哈希冲突的元素，需要对别的位置进行查找**
 *  **那万一存满了呢？实际上是不会放满的，那么放的少了------>空间利用率低，放得多了------>哈希冲突概率高了**
 *  **哈希的负载因子（载荷因子）：哈希表中存放的有效元素个数 / 哈希表的容量 ；负载因子越小，发生哈希冲突的概率越小（在Java中大约是0.75左右）**
 *  **优点：处理冲突的方式简单；缺点：容易产生数据的堆积**

>  **缺点示例：**
> 
>  **哈希函数：****index = value % array.length**
> 
>  **红色数字表示：发生了哈希冲突时，放置的元素**
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td>11</td> 
>    <td>21</td> 
>    <td>22</td> 
>    <td>33</td> 
>    <td>44</td> 
>    <td>55</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>3</td> 
>    <td>4</td> 
>    <td>5</td> 
>    <td>6</td> 
>    <td>7</td> 
>    <td>8</td> 
>    <td>9</td> 
>   </tr> 
>   <tr> 
>    <td></td> 
>    <td>11</td> 
>    <td><strong><span style="color:#fe2c24;">21</span></strong></td> 
>    <td><strong><span style="color:#fe2c24;">22</span></strong></td> 
>    <td><strong><span style="color:#fe2c24;">33</span></strong></td> 
>    <td><strong><span style="color:#fe2c24;">44</span></strong></td> 
>    <td><strong><span style="color:#fe2c24;">55</span></strong></td> 
>    <td></td> 
>    <td></td> 
>    <td></td> 
>   </tr> 
>  </tbody> 
> </table>
> 
>  **可以很直观地观察到，一冲突，后面元素若是此种顺序，堆积的更加严重！！！**

**二次探测：**

>  *  **H(i) = H(0) + i ^ 2 H(0)表示第一此计算出来的哈希地址，i 表示从1 到 9 的数**
>  *  **优点：解决了线性探测的堆积问题；缺点：当表格中的元素不断增多时，需要查找的次数也变得多了**
>  *  **当表的长度为质数且表负载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容**
>  *  **闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷**

#### 2.开散列 ####

*  **开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中**
 *  **简单点说就是数组 + 链表的方式存储**

**待插入的元素：**

**哈希函数：HashFunc(key) = key % capacity capacity为哈希表的容量**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_19_color_FFFFFF_t_70_g_se_x_16][]

## 三，模拟实现哈希桶（开散列） ##

<table> 
 <tbody> 
  <tr> 
   <td><strong>方法</strong></td> 
   <td><strong>解释</strong></td> 
  </tr> 
  <tr> 
   <td><strong>V get(Object key)</strong></td> 
   <td><strong>返回 key 对应的 value</strong></td> 
  </tr> 
  <tr> 
   <td><strong>V getOrDefault(Object key, V defaultValue)</strong></td> 
   <td><strong>返回 key 对应的 value，key 不存在，返回默认值</strong></td> 
  </tr> 
  <tr> 
   <td><strong>V put(K key, V value)</strong></td> 
   <td><strong>设置 key 对应的 value</strong></td> 
  </tr> 
  <tr> 
   <td><strong>V remove(Object key)</strong></td> 
   <td><strong>删除 key 对应的映射关系</strong></td> 
  </tr> 
  <tr> 
   <td><strong>boolean containsKey(Object key)</strong></td> 
   <td><strong>判断是否包含 key</strong></td> 
  </tr> 
  <tr> 
   <td><strong>boolean containsValue(Object value)</strong></td> 
   <td><strong>判断是否包含 value</strong></td> 
  </tr> 
 </tbody> 
</table>

**以上就是我们要实现的方法**

### **模拟实现的准备工作** ###

#### **1.定义哈希表中的结点** ####

#### **2.构造方法** ####

#### **3.哈希地址的计算方法** ####

### 1.操作之添加 / 插入 ###

//操作------>插入/添加
        public Integer put(int key,Integer value){
            //计算key的哈希地址
            int index = hashFunc(key);
            //查找元素是否存在
            ListNode cur = table[index];
            while(cur != null){
                if(cur.key == key){
                    Integer oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
                cur = cur.next;
            }
    
            //没有元素重复
            ListNode newNode = new ListNode(key,value);
            newNode.next = table[index];
            table[index] = newNode;
    
            size++;
            return value;
        }

### 2.操作之获取key的value ###

//操作------> 获取key的value
        public Integer get(int key){
            //计算key的哈希地址
            int index = hashFunc(key);
    
            //查找key
            ListNode cur = table[index];
            while(cur != null){
                if (cur.key == key){
                    return cur.value;
                }
                cur = cur.next;
            }
    
            return null;
        }

### 3.操作 之 key存在返回key对应的value，key不存在返回默认值 ###

//操作 ------> key存在返回key对应的value，key不存在返回默认值
        public Integer getOrDefault(int key,int value){
            if(get(key) != null){
                return get(key);
            }else{
                return value;
            }
        }

### 4.操作之删除key ###

//操作 ------>删除key
        public void remove(int key){
            if (get(key) != null){
                //计算哈希地址
                int index = hashFunc(key);
                ListNode cur = table[index];
                ListNode prev = null;
    
                while(cur != null){
                    if(cur.key == key){
                        if(cur == table[index]){
                            table[index] = cur.next;
                            size--;
                            return;
                        }else{
                            prev.next = cur.next;
                            size--;
                            return;
                        }
                    }else{
                        prev = cur;
                        cur = cur.next;
                    }
                }
            }
        }

### 5.操作之是否包含key ###

//操作 -----> 是否包含key
        public boolean containsKey(int key){
            if(get(key) != null){
                return true;
            }
            return false;
        }

### 6.操作之是否包含value ###

//操作 ------> 是否包含value
        public boolean containsValue(int value){
            for(int index = 0;index < table.length;index++){
                ListNode cur = table[index];
    
                while(cur != null){
                    if(cur.value == value){
                        return true;
                    }
                    cur = cur.next;
                }
            }
            return false;
        }

### 7.测试代码（模拟实现的全部代码） ###

public class TestHashMap {
        public static class ListNode{
            int key;
            Integer value;
            ListNode next;
    
            public ListNode(int key,Integer value){
                this.key = key;
                this.value = value;
            }
        }
    
        ListNode[] table;
        int size;
    
        public TestHashMap(int initCapacity){
            initCapacity = initCapacity <= 0 ? 16 : initCapacity;
            table = new ListNode[initCapacity];
        }
    
        private int hashFunc(int key){
            return key % table.length;
        }
        //操作------>插入/添加
        public Integer put(int key,Integer value){
            //计算key的哈希地址
            int index = hashFunc(key);
            //查找元素是否存在
            ListNode cur = table[index];
            while(cur != null){
                if(cur.key == key){
                    Integer oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
                cur = cur.next;
            }
    
            //没有元素重复
            ListNode newNode = new ListNode(key,value);
            newNode.next = table[index];
            table[index] = newNode;
    
            size++;
            return value;
        }
    
        //操作------> 获取key的value
        public Integer get(int key){
            //计算key的哈希地址
            int index = hashFunc(key);
    
            //查找key
            ListNode cur = table[index];
            while(cur != null){
                if (cur.key == key){
                    return cur.value;
                }
                cur = cur.next;
            }
    
            return null;
        }
    
        //操作 ------> key存在返回key对应的value，key不存在返回默认值
        public Integer getOrDefault(int key,int value){
            if(get(key) != null){
                return get(key);
            }else{
                return value;
            }
        }
    
        //操作 ------>删除key
        public void remove(int key){
            if (get(key) != null){
                //计算哈希地址
                int index = hashFunc(key);
                ListNode cur = table[index];
                ListNode prev = null;
    
                while(cur != null){
                    if(cur.key == key){
                        if(cur == table[index]){
                            table[index] = cur.next;
                            size--;
                            return;
                        }else{
                            prev.next = cur.next;
                            size--;
                            return;
                        }
                    }else{
                        prev = cur;
                        cur = cur.next;
                    }
                }
            }
        }
    
        //操作 -----> 是否包含key
        public boolean containsKey(int key){
            if(get(key) != null){
                return true;
            }
            return false;
        }
        //操作 ------> 是否包含value
        public boolean containsValue(int value){
            for(int index = 0;index < table.length;index++){
                ListNode cur = table[index];
    
                while(cur != null){
                    if(cur.value == value){
                        return true;
                    }
                    cur = cur.next;
                }
            }
            return false;
        }
        public static void main(String[] args) {
            TestHashMap hb = new TestHashMap(10);
            hb.put(1,1);
            hb.put(2,2);
            hb.put(3,3);
            hb.put(6,6);
            hb.put(5,5);
            hb.put(4,4);
            hb.put(10,null);
    
            System.out.println(hb.size);
            System.out.println(hb.get(1));
    
            System.out.println(hb.get(10));
            hb.put(10,10);
            System.out.println(hb.get(10));
            hb.put(10,20);
            System.out.println(hb.get(10));
    
            System.out.println(hb.getOrDefault(20,-1));
            
            hb.remove(6);
            System.out.println(hb.size);
            
            if(hb.containsKey(10)){
                System.out.println("10 在哈希表中");
            }else{
                System.out.println("10 不在哈希表中");
            }
    
            if(hb.containsValue(100)){
                System.out.println("100 在哈希表中");
            }else{
                System.out.println("100 不在哈希表中");
            }
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

## 四，总结 ##

### 常见问题： ###

**1.链表中结点不适宜过多？**

> **答案是肯定的，肯定不能过多，不然会失去哈希桶本身的优势和存在的意义**

**2.大部分元素集合到一个链表当中怎么办？（以上面实现开散列为例子，假设key为 10 20 30 40 50 60 70 80 90）**

> **进行扩容，并对哈希表重新进行开散列，就有可能将元素重新分布**

### 标准库中的扩容 ###

> **1.默认初始容量为16**
> 
>     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
> 
> **2.最大容量为2 ^ 30**
> 
>     /**
>     * The maximum capacity, used if a higher value is implicitly specified
>     * by either of the constructors with arguments.
>     * MUST be a power of two <= 1<<30.
>     */
>     static final int MAXIMUM_CAPACITY = 1 << 30;
> 
> **3.HashMap的默认负载因子是0.75**
> 
>     /**
>     * The load factor used when none specified in constructor.
>     */
>     static final float DEFAULT_LOAD_FACTOR = 0.75f;
> 
> **4.链表和红黑树相互转化**
> 
>  *  **当链表中节点个数超过8时，会将链表转化为红黑树**
>  *  **若红黑树中节点小于6时，红黑树退还为链表**
>  *  **如果哈希桶中某条链表的个数超过8，并且桶的个数超过64时才会将链表转换为红黑树，否则直接扩容**
> 
>     /**
>     * The bin count threshold for using a tree rather than list for a
>     * bin. Bins are converted to trees when adding an element to a
>     * bin with at least this many nodes. The value must be greater
>     * than 2 and should be at least 8 to mesh with assumptions in
>     * tree removal about conversion back to plain bins upon
>     * shrinkage.
>     */
>     // 若链表中节点个数超过8时，会将链表转化为红黑树
>     static final int TREEIFY_THRESHOLD = 8;
>     /**
>     * The bin count threshold for untreeifying a (split) bin during a
>     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
>     * most 6 to mesh with shrinkage detection under removal.
>     */
>     // 若红黑树中节点小于6时，红黑树退还为链表
>     static final int UNTREEIFY_THRESHOLD = 6;
>     /**
>     * The smallest table capacity for which bins may be treeified.
>     * (Otherwise the table is resized if too many nodes in a bin.)
>     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
>     * between resizing and treeification thresholds.
>     */
>     // 如果哈希桶中某条链表的个数超过8，并且桶的个数超过64时才会将链表转换为红黑树，否则直接扩容
>     static final int MIN_TREEIFY_CAPACITY = 64;
> 
> **5.哈希函数**
> 
>     /*
>     1. key如果为空，返回的是0号桶
>     2. key如果不为空，返回该key所对应的哈希码，从该位置可以看出，如果key是自定义类型，必须要重写 
>        Object类的hashCode方法
>     3. 高16bit不变，低16bit和高16bit做了一个异或，主要用于当hashmap 数组比较小的时候所有bit都参与运 
>        算了目的是减少碰撞
>     4. 获取到哈希地址后，计算桶号的方式为：index = (table.length - 1) & hash
>     5. 通过除留余数法方式获取桶号，因为Hash表的大小始终为2的n次幂，因此可以将取模转为位运算操作，提 
>        高效率，这也就是为什么要按照2倍方式扩容的一个原因
>     hash&(table.length-1)     二进制      index        key%(table.length)     index
>          4  & 15             100&1111     100             4  % 16              4
>          13 & 15             1101&1111    1101            13 % 16             13
>          19 & 15             10011&1111   11              19 % 16              3
>     通过上述方式可知，实际上hashcode的很多位是用不上的，因此在HashMap的hash函数中，才使用了移位运算，只取了hashcode的前16位来做映射。2^15=65536 已经是很大的数字了，另一方面&操作比取模效率更高
>     */
>     static final int hash(Object key) {
>            int h;
>            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
>     }
> 
> **6.下一次扩容大小计算**
> 
>     // 每次都是将cap扩展到大于cap最近的2的n次幂
>     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;
>     }
> 
> **int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍**
> 
> **7.构造方法**
> 
>     // 构造方法一：带有初始容量的构造，负载因子使用默认值0.75
>     public HashMap(int initialCapacity) {
>            this(initialCapacity, DEFAULT_LOAD_FACTOR);
>     }
>     // 构造方法二：
>     public HashMap() {
>            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
>     }
>     // 构造方法一：带有初始容量和初始负载因子的构造
>     public HashMap(int initialCapacity, float loadFactor) {
>            // 如果容量小于0，抛出非法参数异常
>            if (initialCapacity < 0)
>                throw new IllegalArgumentException("Illegal initial capacity: " +
>                                                    initialCapacity);
>            // 如果初始容量大于最大值，用2^30代替
>            if (initialCapacity > MAXIMUM_CAPACITY)
>                initialCapacity = MAXIMUM_CAPACITY;
>            // 检测负载因子是否非法，如果负载因子小于0，或者负载因子不是浮点数，抛出非法参数异常
>            if (loadFactor <= 0 || Float.isNaN(loadFactor))
>                throw new IllegalArgumentException("Illegal load factor: " +
>                                                    loadFactor);
>            // 给负载因子和容量赋值，并将容量提升到2的整数次幂
>            // 注意：构造函数中并没有给
>            this.loadFactor = loadFactor;
>            this.threshold = tableSizeFor(initialCapacity);
>     }
>     /*
>     不同于Java7中的构造方法，Java8对于数组table的初始化，并没有直接放在构造器中完成，而是将table数组的构造延迟到了resize中完成
>     */

> **8.LinkedHashMap**
> 
>  *  **LinkedHashMap继承自HashMap，并实现了Map接口**
>  *  **LinkedHashMap底层使用了哈希桶和双向链表两种结构**
>  *  **LinkedHashMap需要重写HashMap中的：afterNodeInsertion/afterNodeAcess/afterNodeRemove等方法**
>  *  **LinkedHashMap使用迭代器访问时，可以保证一个有序的结果，注意此处的有序不是自然有序，而是元素的插入次序。另外，当向哈希表中重复插入某个键的时候，不会影响到原来的有序性。也就是说，假设你插入的键的顺序为1、2、3、4，后来再次插入2，迭代时的顺序还是1、2、3、4，而不会因为后来插入的2变成1、3、4、2**
>  *  **LinkedHashMap可以作为LRU来使用,但是要重写removeEldestEntry方法**

> **9.resize扩容**  
> **在Java8的扩容中，不是简单的将原数组中的每一个元素取出进行重新hash映射，而是做移位检测。所谓移位检测的含义具体是针对HashMap做映射时的&运算所提出的，通过上文对&运算的分析可知，映射的本质即看hash值的某一位是0还是1，当扩容以后，会相比于原数组多出一位做比较，由多出来的这一位是0还是1来决定是否进行移位，而具体的移位距离，也是可知的，及位原数组的大小，我们来看下表的分析，假定原表大小为16**
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td> <p>HashCode(Java8中只使用高16<br> 位）</p> </td> 
>    <td>size=16</td> 
>    <td>size=32</td> 
>    <td>移位<br> 情况</td> 
>   </tr> 
>   <tr> 
>    <td>0101 1010 0011 1101</td> 
>    <td>0101101000111101&amp;1111</td> 
>    <td>0101101000111101&amp;11111</td> 
>    <td>向前<br> 移动<br> 16位</td> 
>   </tr> 
>   <tr> 
>    <td>1011 0111 1000 0101</td> 
>    <td>1011011110000101&amp;1111</td> 
>    <td>1011011110000101&amp;11111</td> 
>    <td>不移<br> 动</td> 
>   </tr> 
>   <tr> 
>    <td>1110 0100 0001 0001</td> 
>    <td>1110010000010001&amp;1111</td> 
>    <td>1110010000010001&amp;1111</td> 
>    <td>向前<br> 移动<br> 16</td> 
>   </tr> 
>  </tbody> 
> </table>

[log_2_N]: https://latex.csdn.net/eq?%5Clog_%7B2%7DN
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ddbf69afcf0540d195674c71defb39a2.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0d031f580e4f49529e787a2113c25f24.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ae7ed8032d4c4f59bae539d6a0d1852f.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16