一篇搞懂HashMap，手写HashMap_手写 hashmap

HashMap核心原理

预备知识

1. 算法复杂度：大 O 表示法

• 大O表示法是一种特殊的表示法，指出了算法的速度有多快。
• O(n)：表示该算法需要计算n次，比如常见的for循环：

//n是正整数，这个for循环需要循环n次，算法复杂度就是O(n)
for(int i=0;i<n;i++){
  ...
}
1
2
3
4

• O(1)：无论多少元素参与运算，复杂度始终是计算一次，这个就是典型的最优解。例如查找数组元素：

//获取数组中某个元素，直接找到数组下标就可以获取，不需要循环，这个算法复杂度就是O(1)
int[] a ={1,2,3,4,5};
a[0];
1
2
3

2. 位运算

• 二进制的位运算包括（&、|、^、~、>>、<<、>>>），这种运算速度很快。
• 1 btye（字节）=8 bit（位），一个8bit就可以表示一个二进制，例如 0000 0010
• &（与运算）： 两个位都为1时，结果才为1。例如：

//3&5的二进制： 
0000 0011 & 0000 0101 = 0000 0001 ，因此 3&5 的值得1。
//与运算常用用途：清零，如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。
//HashMap源码中putval方法用到了与运算(计算数组索引：(n - 1) & hash , n是2的倍数的正整数），例如16，hash是计算hash值，计算后获得是一个正整数，这个公式最后计算结果等同求余数，例如（16-1）& 506434430 = 14，意思就是获得余数14，这个余数就是hashmap放入元素在数组中的索引位置（后面详解）

1
2
3
4
5

• | （或运算）： 两个位都为0时，结果才为0

3|5即 0000 0011| 0000 0101 = 0000 0111，因此，3|5的值得7。　
//或运算常用来对一个数据的某些位设置为1
//HashMap中tableSizeFor(int cap)方法用到了或运算，目的是找到最接近用户指定集合大小cap的2的n次方的整数，例如cap=99时候，该方法计算出128是最接近99且是2的n次方的数
1
2
3

• ^（异或运算）：两个位相同为0，相异为1

运算规则:0^0=0  0^1=1  1^0=1  1^1=0
//常常用于翻转指定位
1
2

• <<（左移）： 各二进位全部左移若干位，高位丢弃，低位补0

1<<2  结果4，相当于1×2^2
1

可以约等同这个公式：
$$1<<n=1\times 2^n$$

• >>（右移）： 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

100>>2  结果25，相当于100÷2^2
1

可以约等同这个公式：
$$100>>n=100÷2^n$$

• >>>（无符号右移）：就是右移，但是结果始终为非负数。

3.泛型类数组

• 把泛型类作为元素的一个数组

//声明一个泛型类
public class A<K,V>(){}
//声明一个泛型类作为元素的数组，其底层是一个数组，其中的元素是一个泛型类
A<K,V>[] a;
1
2
3
4

HashMap产生背景

• HashMap是集数组和链表的优点而成的一个集合，数组的优点是查询快，时间复杂度是O(1)，缺点是插入数据特别是中间和头部插入效率低，链表恰恰相反，HashMap的目标是集合两者优点，插入和查询的时间复杂度是O(1)，这个是HashMap的目标，很多手写HashMap最终实现了但是没有达到O(1)，这样就是失去了他的优势。

HashMap核心原理

HashMap图形结构

• HashMap可以理解成一个项链结构，本身是一个数组，当出现hash冲突时该位置变成链表，当链表个数大于8时变成红黑树（JDK8才有红黑树）。
  

• HashMap的目标是插入和查询的时间复杂度是O(1)，这种项链结构的设计都是服务于这个目标。

• HashMap中声明了一个Node<K,V>[ ]作为整个骨架（有力气的宝宝可以看看源码¹），每个数组中放入的都是一个Node<K,V>，就是单节点的链表，当出现hash冲突时就挂在一起形成多节点链表，判断是否是单节点是看这个Node的next是否是Null。当链表长度大于8变红黑树，这个是因为链表大度太大会导致查询变慢，而红黑树具有较高的查询速度。HashMap如果出现链表和红黑树时间复杂度会大于O(1)。

• 源码中对8这个解释是：根据泊松分布公式，出现8个hash冲突的几率非常低，所以一旦出现8个以上hash冲突多半是误操作或者漏洞攻击，之前就有利用HashMap这种链表结构攻击，导致服务器崩溃，所以这个变红黑树其实是补漏洞。正常操作很难出现红黑树。

hash冲突

• HashMap插入原理：Java中Object有个方法hashCode()，意思就是每个类都可以被算成hash值，这个是native方法，是JVM中用C++实现的，这个方法的主要作用就是把任何类变成一个整数。变成整数有什么用处？变成整数后通过计算，可以获取数组中的索引位置，然后按照这个索引去放置元素，例如算出索引是4，那就放入Node<K,V>[4]里面去，这种插入是分散的，所以不会因为插入元素导致索引重排，插入时间复杂度是O(1)，同时获取元素也是通过计算hash获取索引，所以查询时间复杂度是O(1)。
• hash冲突：这种计算成整数的方法，会导致不同对象计算出的整数是相同的，这个就是hash冲突。
• HashMap解决办法：变链表，大于8变红黑树。
• hashCode() 和 hash()：hash()是HashMap对hashCode后还做了进一步计算，进一步计算的目的是让hash更加散列，最终计算出来的索引重复尽可能小。

//任意对象都可以算成整数
"1".hashCode();
//HashMap中获取到hashCode后还做了进一步计算，这个进一步计算后的hash值是计算索引的依据。
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
1
2
3
4
5
6
7

手写HashMap主要流程

• 原版流程
  
• 简易版流程：
  
• 手写的简易版是单一类，没有继承抽象类，没有实现接口，去掉红黑树，初始化时默认放入16长度，去掉复杂的控制参数。

手写前的重要参数和概念

• 容量capacity：就是数组的大小，例如 int a = new int[10]，容量就是10。
• 数组元素个数size：数组中非null的元素个数。
• 阈值threshold ：用于判断是否扩容，因为底层是数组，数组声明大小后长度不能改变，HashMap是通过声明一个新数组，把所有元素移过去。所以扩容非常消耗性能，如果可以预估数据量可以声明HashMap的时候声明数组大小，例如HashMap<String, String> hashMap = new HashMap<>(1000);无论你申请多大容量，HashMap中的tableSizeFor(int cap)方法会计算一个最接近2的n次方的值进行扩容，始终保持2的倍数扩容。为什么是2的倍数，目的是减少hash碰撞，因为2的倍速在公式(n - 1) & hash(key)运算后可以获得更少重复的索引值，减少变链表机会，链表让作者讨厌啊。
• 负载因子DEFAULT_LOAD_FACTOR：阈值=容量×负载因子。为什么要设计负载因子，目的还是减少形成链表的机会。因为一旦使用完了所有空间，必然增加链表产生机会，而且如果本身有链表，那元素个数size不是和数组位置一一对应的，这个时候可能元素个数早就超过容量了，所以要在装满之前就要扩容。默认负载因子0.75是一个适中值，反正作者就这么写。

手写简易版

手写MyHashMap类

package com.cn.iv;

/**
 * 简易HashMap
 * 简易示范：不继承接口
 */
public class MyHashMap<K, V> {
    /*数组骨架：每个节点都是node的一个数组,容量capactiy就是table.length*/
    Node<K, V>[] table;
    /*初始数组大小*/
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 1*2的4次方=16
    /*真实元素长度*/
    int size = 0;
    /*负载因子*/
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /*阈值：用于判断是否扩容，计算方法：capacity * load factor*/
    int threshold;

    /**
     * 初始化：原版是put后才开始初始化，这里便于代码简单
     * 初始化默认16大小的数组容器
     * 容器中装载Node<K,V></>
     */
    public MyHashMap() {
        table = new Node[DEFAULT_INITIAL_CAPACITY];
        threshold= (int) (DEFAULT_LOAD_FACTOR*table.length);//记录阈值
    }

    /**
     * 返回真实元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * PUT：插入值
     */
    public void put(K k, V v) {
        /*根据hash算法找到数组索引，这个时候出现3种情况，该位置无节点，有节点且值重复，有节点不重复变链表*/
        int index = index(table.length, k);//获取索引
        Node<K, V> node=table[index];//原位置节点
        /*1，无节点：直接放入值*/
        if (node==null){
            table[index] = new Node<>(hash(k), k, v, null);//直接赋值
            ++size;
        }
        /*有节点*/
        if (node!=null){
            /*2，有节点且值重复：覆盖*/
            if (node.getV()==v){
                table[index] =new Node<>(hash(k), k, v, null);//直接赋值
            }else{/*3，有节点不重复变链表：头插法挂入链表【未实现红黑树】*/
                table[index] =new Node<>(hash(k), k, v, node);
                ++size;
            }

        }
        System.out.println(size+"，"+threshold);
        /*判断扩容：先插入值再判断扩容，因为完整容量是有多余空间的*/
        if (size>threshold){
            resize();
        }
    }

    /**
     * GET：获取值
     * 按照key来获取对应的value值
     */
    public V get(K k){
        /*有值：单一节点直接返回，链表遍历获取*/
        int index= index(table.length, k);//获取索引
        Node<K, V> node = table[index];
        if (node!=null){
            if (node.getNext()==null){//单一节点
                return node.getV();
            }else {//链表
                Node<K, V> next = node.next;
                while (null != next) {//链表最后一个的next是null，跳出循环
                    if (next.getK() == k) {//链表是hash和索引相同，但key不同
                        return next.getV();
                    }
                    next = next.next;
                }
            }
        }
        /*无值*/
        return null;
    }

    /**
     * 扩容
     * 判断是否扩容，是在put方法中
     * 每次扩容都是2的N次幂，就是原有容量*2
     * @return
     */
    final Node<K, V>[] resize() {
        /*声明旧容量，（不考虑容量为0，因为初始化就给了16长度，不考虑超过最大容量1<<30）*/
        Node[] tableOld=table;//原容器
        Node[] tableNew;//扩容后新容器
        /*扩容成2倍，遍历原有数组，使用hash放入新数组，扩容是for循环+while循环，性能消耗大*/
        tableNew = new Node[tableOld.length<<1];//新数组是原数组2倍
        for (int i=0;i<tableOld.length;i++){
            if (tableOld[i]!=null){
               tableNew[index(tableNew.length, tableOld[i].getHash())]=tableOld[i];//重新hash到新数组
                /*红黑树未考虑，如果是链表，链表中的hash,k,v,next都未变，只是首个表头索引变了*/
            }
        }
        /*扩容后更新容器，更新阈值*/
        return null;
    }

    /**
     * 计算hash值
     *
     * @param key
     * @return
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 计算索引值
     *
     * @param n hashmap容量，就是table.length
     * @param key 需要计算的key
     * @return
     */
    static int index(int n, Object key) {
        return (n - 1) & hash(key);
    }


/**
 * 类：HashMap中元素
 * 每个元素都是一个链表节点，如果有Hash碰撞就挂在链表下
 *
 * @param <K>
 * @param <V>
 */
class Node<K, V> {
    /*计算后的hash值，用于找到节点放在数组哪个位置和获取节点*/
    int hash;
    /*key*/
    K k;
    /*value*/
    V v;
    /*链表下一个节点，如果没有就是null*/
    Node<K, V> next;

    public Node(int hash, K k, V v, Node<K, V> next) {
        this.hash = hash;
        this.k = k;
        this.v = v;
        this.next = next;
    }

    public Node<K, V> getNext() {
        return next;
    }

    public int getHash() {
        return hash;
    }

    public K getK() {
        return k;
    }

    public V getV() {
        return v;
    }

    @Override
    public String toString() {
        return "Node{" +
                "hash=" + hash +
                ", k=" + k +
                ", v=" + v +
                ", next=" + next +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

测试一下

     public static void main(String[] args) {
        MyHashMap<Integer, Integer> myHashMap = new MyHashMap<Integer, Integer>();
        myHashMap.put(1,100);
        myHashMap.put(1,100);
        myHashMap.put(2,200);
        myHashMap.put(3,300);
        System.out.println(myHashMap.size());
        System.out.println(myHashMap.get(1));
    }
1
2
3
4
5
6
7
8
9

总结

1. HashMap底层就是数组，为了实现插入时间复杂度O（1），使用了hash算法去计算数组索引位置，散列的放入数组，因为这个设计导致hash冲突于是又发明了挂链表，又因为挂链表太长被漏洞攻击，于是补漏洞发明当长度8变红黑树。4个作者一个一个修修补补成了现在的HashMap。
2. HashMap有很多位运算，一个方面是速度快，另一方面就是像各种办法减少链表的产生。
3. HashMap因为有链表和红黑树，所以插入和查询不是绝对O(1)。
4. 扩容是HashMap的最需要注意的地方，扩容时时间复杂度瞬间上升，所以预估数据给一个初始大小，不要频繁扩容。
5. ArrayList同样是自动扩容，也可以指定初始化大小，和HashMap区别是未要求2的n次方。所以HashMap中要求扩容是2的倍数，就是为了减少hash冲突，减少索引出现重复，最终是最大程度遏制链表产生。在get方法中出现链表需要一个一个遍历，效率很低。

---

1. 源码位置：jdk1.8->rt.jar->java->util->HashMap ↩︎