一篇搞懂HashMap，手写HashMap

HashMap核心原理

预备知识

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

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

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

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

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

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放入元素在数组中的索引位置（后面详解）

• | （或运算）： 两个位都为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次方的数

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

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

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

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

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

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

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

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

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

3.泛型类数组

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

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

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);
 }

手写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 +
                '}';
    }
}

测试一下

     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. 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方法中出现链表需要一个一个遍历，效率很低。

到了这里，关于一篇搞懂HashMap，手写HashMap的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！