[数据结构与算法] HashMap源码图解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> HashMap源码图解 -> 正文阅读

[数据结构与算法]HashMap源码图解

文章目录

基础入门

1、数组与链表的优劣

数组的内存是连续的，每一块的内存空间是一样大的，所以索引速度是很快的(有索引下标)，但是扩容与插入删除繁琐

链表内存不连续，每一个结点保存下一个结点的引用地址，所以相比于数组顺序存储插入删除容易，索引比较繁琐

2、散列表：整合数组与链表的优势

散列表：数组加链表，数组中保存的数据是链表，整合了数组的快速索引与链表的动态扩容(增删)

核心理论: Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出

这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值

Hash的特点：

从hash值不可以反向推导出原始的数据
输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
hash算法的冲突概率要小
hashCode并不是完全可靠，有时候不同的对象他们生成的hashcode也会一样(生成hash值得公式可能存在的问题)

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间
根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况(hash冲突)

HashMap原理讲解

1、HashMap继承体系

2、HashMNode数据结构分析

interface Entry<K,V> {	//Map
    K getKey();
    V getValue();
    V setValue(V value);
}


static class Node<K,V> implements Map.Entry<K,V> {		//HashMap
    final int hash;		  //结点的hash值
    final K key;	     //结点的key
    V value;		    //结点的value
    Node<K,V> next;	    //hash碰撞时链起来

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

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

3、底层存储结构介绍

底层维护一个Node数组，存储结构为：数组 + 链表 + 红黑树

当没有发生冲突的时候是数组，当发生hash冲突的时候冲突的桶位形成链表，当链表长度达到8后并且hash表中所有元素达到64个链表就会进行树化

JDK8为什么引入红黑树？

红黑树：黑色自平衡二叉查找树，为了解决可能的过度链化的问题(过度链化的时候查找效率基本退化为logn)，提高查找效率

4、put数据原理分析

5、HashMap扩容原理

当hash表存放的数据达到了接近表容量的情况下查找效率就会变得很差，为了解决这个问题，就需要扩容提升桶位、减少链表长度以提高查找效率，是以空间换时间的做法

HashMap源码分析

1、核心属性解析

//默认的数组大小16，构建的时候不给传大小时的默认值
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//数组最大长度 2的三十次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认负载因子大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//链表树化阈值
static final int TREEIFY_THRESHOLD = 8;

//树降级为链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

//数组的长度最少为64后，达到树化阈值的链表才可以升级为树
static final int MIN_TREEIFY_CAPACITY = 64;




//维护的hash表，表现为Node数组
transient Node<K,V>[] table;
//懂得都懂
transient Set<Map.Entry<K,V>> entrySet;
//当前hash表中元素个数
transient int size;
//当前hash表结构修改次数（增删结点算，修改结点value不算）
transient int modCount;
//扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容
int threshold;
//负载因子，默认0.75，可以去计算出threshold：threshold = capacity * loadFactor 	capacity：表数组长度
final float loadFactor;

2、构造方法解析

public HashMap(int initialCapacity, float loadFactor) {
    //数组大小小于0不合法抛异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //如果数组大小超过了最大长度（2的三十次方）则设置为最大长度
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    //负载因子不能小于0且不能为非数
    //（NaN 实际上就是 Not a Number的简称。0.0f/0.0f的值就是NaN，从数学角度说，0/0就是一种未确定）
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //数组的长度必须是2的次方数，tableSizeFor()返回大于等于initialCapacity的最小2的次方数
    this.threshold = tableSizeFor(initialCapacity);
}		

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}





//美妙的算法
static final int tableSizeFor(int cap) {
    int n = cap - 1;	//防止传进来的为2的次方数
    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;
}

3、put方法解析

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    } 
	//hash扰动函数
    //key是null则hash值为0
	//h与h的无符号右移16位作位最终hash码
	//作用：让key的hash的高16位也参与运算，即当数组的长度很短时，只有低位数的hashcode值能参与运算。而让高16位参与运算可以		更好的均匀散列，减少碰撞，进一步降低hash冲突的几率。并且使得高16位和低16位的信息都被保留了
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }


	//onlyIfAbsent：仅仅在表中没有该key的时候才插入，有的话就不插了，即不会修改，putIfAbsent插入方法会传入true
	//如果是替换则返回老的value值，否则返回值为null
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {

        /**
         	tab:hashmap散列表的引用
         	p:当前散列表的元素
         	n:散列表数组的长度
         	i:路由寻址结果的下标
        **/
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        
        //若当前散列表还未创建则创建
        //是延迟初始化逻辑,第一次调用putVal时才会初始化hashMap对象中的最耗费内存的散列表
        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 {
            //e:不为null的话，找到了一个与当前要插入的key-value一致的元素
            Node<K,V> e; K k;
            //表示桶位中的第一个元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //桶位中该元素不与你当前元素一致且已经树化了后的put处理
            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)
                            //树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果找到了一个相同的元素则跳出循环，在下方会进行插入
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //如果未找到则继续循环
                    p = e;
                }
            }
            //发生碰撞的情况下找到了一个要被替换结点则进行修改并将旧值返回（表不计入表结构修改）
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        //表结构修改次数加1表，替换Node元素的value不计数
        ++modCount;
        //若插入后元素数量大于了扩容阈值则触发扩容
        if (++size > threshold)
            resize();
        //模板方法
        afterNodeInsertion(evict);
        return null;
    }

hash扰动的作用与例子：

因为当table长度还是不是很长的时候比如16

存放在数组的下标位置计算公式为：hashcode & （length - 1） 即 hashcode & 1111

如果不做hash扰动的话，两个key的hash后四位相同的结点就会发生冲突，但是做了hash扰动会让高16位与低16位异或，而在此情况下(表长16)两个低4位相同的hashcode与高16位异或后的结果相同的概论就很低了，所以冲突就解决了

总体流程图如下：

4、resize方法解析

为什么要扩容？

为了解决hash冲突，防止过度链化影响查询效率，扩容会缓解该问题，如下图所示：

    final Node<K,V>[] resize() {
        //引用扩容前的hash表
        Node<K,V>[] oldTab = table;
        //扩容前hash表的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //触发本次扩容的阈值
        int oldThr = threshold;
        //newCap:扩容之后的大小	newThr:扩容之后新的扩容阈值
        int newCap, newThr = 0;

-------------------------------------------------------------------------------------------------------------------
        
        //条件如果成立说明 hashMap中的散列表已经初始化过了，是一次正常扩容
        if (oldCap > 0) {
            //扩不了啦 开摆！
            //扩容之前的table数组大小已经达到最大阈值后，则不扩容，且设置扩容条件为 int最大值（此后再也不会resize）
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //新容量newCap翻倍，newCap小于最大值限制且扩容之前数组长度≥16
            //这种请况下下一次阈值为当前阈值翻倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; 
        }
        //oldCap为0但是oldThr＞0 说明hashmap的散列表是null
        //HashMap(initialCapacity, loadFactor)
        //HashMap(intinitialCapacity, loadFactor)
        //HashMap(map)
        //以上三个构造方法会确定通过tableSizeFor方法计算出的oldThr的值（2的次方数）
        else if (oldThr > 0) 
            newCap = oldThr;
        //无参构造的第一次扩容  newCap=16 newThr=12
        else {       
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        
        //只有第一次初始化扩容时通过三个无参构造的HashMap与容量为16之前的扩容才会来到这个if
        //newThr为零时，通过newCap和loadFactor计算出一个newThr  基本就是newCap*0.75
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //将newThr赋值给扩容阈值
        threshold = newThr;
        
        
        
//以上代码就做了两件事     1.计算本次扩容之后需要创建多大的数组newCap    2.计算下一次再次出发扩容时的条件newThr
-------------------------------------------------------------------------------------------------------------------
        
        @SuppressWarnings({"rawtypes","unchecked"})
    	//根据newCap创建出新的更长更大的数组newTab
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        
        //若旧表里有数据则循环向新表里拷贝
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;	//e用于保存当前结点
                if ((e = oldTab[j]) != null) {
                    //将表中结点置空以便GC回收旧表内存
                    oldTab[j] = null;
                    //如果只有一个结点则直接hash到新表
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果已经树化则进行树化拷贝处理
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //链化拷贝
                    else { 
                        //低位链表:存放在扩容之后的数组的下标位置，与当前数组的下标位置一致
                        Node<K,V> loHead = null, loTail = null;
                        //高位链表:存放在扩容之后的数组的下标位置为当前数组下标位置＋扩容之前数组的长度
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;		//next用于将e的下一个元素保存
                        //循环尾插创建出高低位链表
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        
                        //低位链表赋值到新数组
                        if (loTail != null) {
                            //清除可能的指向高位链的引用
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //高位链表赋值到新数组
                        if (hiTail != null) {
                            //清除可能的指向低位链的引用
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                        
                    }
                }
            }
        }
        return newTab;
    }

在扩充HashMap的之后，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成 原索引+oldCap，这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了

扩容第一大步：计算oldCap,oldThr,newCap,newThr流程图

扩容整体流程图

6、get与remove方法解析

get非常简单，就是查找如果第一个结点不是就树式或者链式查询

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

	
    final Node<K,V> getNode(int hash, Object key) {
        //tab:散列表的引用	first：桶位中的头结点 	e:临时node结点 
        //n:table数组长度 
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //表不为空 && 表长＞0 && 当前元素的应在位置头有数据（一个 | 多个 | 树）
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //第一个就是要取的数据，芜湖
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //很遗憾第一个不是，这时候已经链化或者树化
            if ((e = first.next) != null) {
                //如果已经树化，则树式查询，找不到则返回null
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //如果已经链化，则链式查询，找不到则返回null
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

remove也非常简单，就是找到了嗯删

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

   //matchValue为true的时候则value也必须匹配才可以进行删除
   final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
       //tab:散列表引用	p:表中node结点	n:表长	index:寻址结果
        Node<K,V>[] tab; Node<K,V> p; int n, index;
       
        //表不为空 && 表长＞0 && 当前元素的应在位置头有数据（一个 | 多个 | 树）
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            //node:查找到的结果	e:next结点
            Node<K,V> node = null, e; K k; V v;
            
            //查找逻辑 
           	//第一种情况:第一个就是
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //第一个不是且其后还有结点，可能树化也可能链化
            else if ((e = p.next) != null) {
                //树化处理，红黑树查找操作 
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    //链化处理
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            } 
            
            //删除逻辑
            //如果照到了要删除的结点并且根据matchValue判断到底删不删value不一样的结点
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //第一种情况:如果要删除的结点是树上的，则走树的删除逻辑
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //第二种情况:桶位第一个结点即为查找结果（上述第一种情况），则进行删除
                else if (node == p)
                    tab[index] = node.next;
                //第二种情况:链式删除
                else
                    p.next = node.next;
                //表结构修改次数加一
                ++modCount;
                //表大小减一
                --size;
                //删除后的后置处理操作，空方法，模板方法
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }