HashMap 源码分析(一)

一、概述

在Java开发中,HashMap使用的频率还是比较多的,主要通过key-value的形式来存储数据,但是HashMap的原理是怎样的呢?他是如何进行增删改查的呢?所以今天我们就带着这些问题来看源码,主要看它的put,get,remove方法。本文我们使用的JDK版本为1.8。

二、源码分析

在分析源码之前,我们先来看一下HashMap的简单使用:

public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        hashMap.put("key","张三");
        System.out.println(hashMap.get("key"));
}

我们按照这个顺序来继续分析源码,首先来看一下四个构造方法:相关解释已经写在了注释中。


    构造一个空的HashMap,默认的初始容量为:16,默认的加载因子为:0.75。
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

   构造一个空的 指定容量的HashMap,默认的加载因子为:0.75。
    public HashMap(int initialCapacity) {
        //继续调用了第三个调用方法
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    构造一个空的HashMap,指定初始容量,和 加载因子。
    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);
    }

    构造一个与指定Map相同映射的HashMap 可以理解为将Map转为HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }


二、增和改

现在我们带着第一个问题:HashMap是如何插入数据的呢?我们直接来看put方法:

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

可以看到HashMap的put方法又调用了putVal方法,第一个参数中又调用了hash(key),我们先来看看hash(key的作用):这里问题,为什么进行位运算

    static final int hash(Object key) {
        int h;
        //如果key为空,返回0,否则返回key.hashCode的异或运算 位移16位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这里简单举例一个异或运算:比如
h=2987074,在位运算中都是通过二进制进行,
h的二进制:0010 1101 1001 0100 0100 0010
h位移16位之后的二进制:0000 0000 0000 0000 0010 1101
这两个二进制数再进行^(异或)运算,
结果为:0010 1101 1001 0100 0110 1111,转为十进制为:2987119。

看完hash方法之后继续看putVal方法,但是在看putVal方法之前,我们先了解一下HashMap的一个内部类,Node。

在Node类中,存储了hash,key,value,和next,next就是当前node指向的下一个节点,这就是一个链表结构。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> 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;
        }

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

继续来看putVal方法:

    /**
     * @param hash key 的hash
     * @param key 
     * @param value
     * @param onlyIfAbsent 如果为true,则不更改现有值
     * @param evict 如果为false,则表处于创建模式
     * @return valur or null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab;
        Node<K,V> p;
        int n, i;
        //如果table为空,或 长度为0时
        //这里的table为Node<K,V>[] table,是一个数组,Node相当于链表,所以到这里我们可以知道HashMap
        //底层使用的是数组+链表
        if ((tab = table) == null || (n = tab.length) == 0)
            //n = 创建一个新的tab并返回长度
            //这里的n就是tab的长度,即Node<K,V>[]数组长度
            n = (tab = resize()).length;
        //通过数组长度-1 与 hasn进行与运算拿到i即下标,再通过下标取数组中的node,
        //如果为null是,创建一个新的node,赋值给tab[i]
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; 
            K k;
            //如果p中和传入的hash相等,与 key相等时,
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将p即node,赋值给e
                e = p;
            //否则 p是一个树节点,将其插入到树中,并赋值给e
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    //如果p的下一个节点为空,则创建一个node,赋值给p.next,
                    //这里采用的是尾插法,
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果数量大于 TREEIFY_THRESHOLD 即8时,将链表Node,转换为树(红黑树)
                        //到这里 HashMap的结构就成为了数组+链表+红黑树。
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果hash相等,则直接跳出循环,
                    //到这里就表示当前的e(node)和传入的值已经相等了,所以没必要循环了
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果node不为空,保存value为oldValue,
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //如果需要改变现有值,value为空时,将传入的value赋值给node.value
                //这里对应的就是修改key的value
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果当前长度大于默认长度
        //++size 就是每次put后size+1,getSize()就是这个size
        if (++size > threshold)
            //执行扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }


三、查

put方法已经分析完成了,相关的注释我已经写在了上面,大家可以认真看,其实并不太难,接下来我们来看下一个问题,HashMap中是如何通过key获取Value的呢?接下来继续看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) {
        Node<K,V>[] tab;
        Node<K,V> first, e;
        int n;
        K k;
        //如果tab不为null,与 查找到的node不为空时,
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //如果第一个node hash 和key和我们想要的hash key相同,直接返回此node
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果node的next不为空,
            if ((e = first.next) != null) {
                //如果node时TreeNode(树节点)
                if (first instanceof TreeNode)
                    //从树中查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //通过循环 遍历节点的next,如果找到hash和key相同的则返回。
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //没有找到 返回null
        return null;
    }


四、删

到这里,增改查就已经分析完毕,最后来看删除的方法:remove();

    public V remove(Object key) {
        Node<K,V> e;
        //通过removeNode方法查找对应的Node节点返回node.value
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

在removeNode方法中,和getNode原理大致相同,我们来简单看一下:

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab;
        Node<K,V> p;
        int n, index; //n为长度,index为下标
        //如果tab不为空 与 查找到的node不为空时,
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            //如果node中的hash和传入的hash相等,且key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将p赋值给node
                node = p;
            //如果next不为空时,
            else if ((e = p.next) != null) {
                //如果p是树节点
                if (p instanceof TreeNode)
                    //node = 从树节点中查找
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    //否则 遍历table,知道找到要删除的node
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //如果node不为空,与 值相等时
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果node时树节点,就从树节点中删除。
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //更改node的next为要删除的next,就是更改当前node的next引用 为 要删除的next的引用
                //这样就相当于与要删除的节点断开了连接 从而实现了删除
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                //size-1
                --size;
                afterNodeRemoval(node);
                //最后返回删除的node
                return node;
            }
        }
        return null;
    }

到这里HashMap的增删改查的源码我们已经看完了,所对应的为:put(),get(),remove()。在上面的代码中,我都已经写好了注释,根据注释结合代码看还是非常通俗易懂的。

五、总结

通过上面的分析,我们已经基本理解了HashMap增删改查的大致流程了,我们总结如下:

  1. 增(put):

①:通过key的hashcode和hashcode的位移16位进行异或运算得到一个hash值。
②:如果存储节点(Node)的数组为空,则创建一个新的数组。
③:通过数组的长度-1 和 上面得到的hash进行&运算,得到一个node即p;
④:如果p为空,说明该位置没有存储节点,则创建一个node对象,并存入对应的下标中。
⑤:否则,p不为空时,判断Node是否是TreeNode(树节点),如果是则插入到树节点。
⑥:如果不是树节点,则遍历链表,直到链表的next为空时,将此node赋值给next。
⑦:同时判断遍历的次数,如果大于等于TREEIFY_THRESHOLD即8-1时,将链表转换为红黑树。
⑧:如果key hash相同,且需要修改value时,则修改value。
⑨:最后进行收尾工作,++size,如果长度大于threshold,进行扩容。

  1. 改:

其实改的方法是包含在put方法之中的,当传入的key相同时,则根据参数onlyIfAbsent来决定是否更新这个值。

  1. 查(get):

①:判断tab不为空时,算出数组中的index,找到头节点node。
②:如果头节点的key和hash与传入的相同,直接返回此node。
③:如果没找到,继续判断,如果node为红黑树结构,则从红黑树中查找。
④:如果没找到,遍历链表,继续查找key hash和传入相同的node,找到则返回。
⑤:没找到,返回null。

  1. 删(remove):

查和删的原理大致相同,首先都是通过一系列判断查找出对应的node节点,最后通过更改next的指向来达到删除的效果。其中有一个参数:matchValue,如果为true时,则只会在两个value相等的情况下才会删除。

最后上一张HashMap的结构图,以供大家理解。


HashMap.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,922评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,591评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,546评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,467评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,553评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,580评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,588评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,334评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,780评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,925评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,573评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352

推荐阅读更多精彩内容

  • 一、Map概述 首先,在Java集合中,Map是一种以key-value键值对形式保存存储数据的特殊集合类。而Ha...
    LeonardoEzio阅读 699评论 3 18
  • HashMap源码分析——put和get(二) 链接 上一节 :HashMap源码分析——put和get(一) 2...
    施瓦阅读 517评论 0 1
  • 1.HashMap的底层实现图示 如上图所示: HashMap底层是由数组+(链表)=(红黑树)组成,每个存储在H...
    Bamboo_a67a阅读 257评论 0 0
  • 什么是HashMap HashMap是一个用于存储Key-Value键值对的集合,也是Java中使用频率最高的用于...
    言淺阅读 309评论 0 0
  • 一、写在前面 相信读者也看过了不少讲解 HashMap 源码的文章了,笔者认为,一切脱离源码去讲原理的都是泛泛而谈...
    CoderZS阅读 327评论 1 1