首页 > 编程语言 >HashMap源码分析

HashMap源码分析

时间:2024-09-12 13:25:06浏览次数:10  
标签:分析 Node hash HashMap else 链表 源码 key null

HashMap源码分析

image-20240901220247606

在jdk1.8中,HashMap的数据结构如上图所示,是由Node数组+链表/红黑树组成的,每个K-V对保存在一个Node结点中,看一下Node结点的定义,其实就是一个Map.Entry<K,V>的实现类,包括key的hash值,key,value和一个next指针。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

//树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    ...
}

HashMap中定义的几个静态变量:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
    /**
     * HashMap的初始容量为2^4=16,容量表示table[]的长度,也是哈希桶的个数
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * HashMap的最大容量为2^30
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 负载因子,当元素数量大于当前容量的0.75倍时,HashMap进行自动扩容
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 树化阈值,当哈希桶上的链表长度大于等于8时进行扩容或转为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 和树化阈值相反,树节点数量小于6时红黑树转为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 最小树化容量,当前容量大于等于64时,桶中链表才会转换为红黑树,否则只是扩容
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
	...
}

看一下HashMap的put()方法是怎样插入结点的:

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

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[]为空,初始化一个table[]
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据key的hash值定义key在table[]中的下标i,p作为结点指针判断下标i位置是否为空
    //如果为空,直接在该位置创建一个Node结点就好了,否则进入p指向下标为i的结点进入else
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //进入else,说明要插入的k的hash值已存在,如果有相同的key,则替换,否则,插入链表或红黑树
        //判断key是否相同,相同的话用e表示旧结点,后面进行替换
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果p是树节点,则将新结点插入红黑树中,p指向树的根节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //这个else表示将新结点插入链表,此时p指向链表头节点
        else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //尾插法插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果链表长度大于等于8,进行扩容,或者树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果在链表中找到相同的key,则新value替换旧value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //新值替换旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //节点数量大于阈值进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}    

总结一下put的流程:首先,判断插入节点的哈希地址是否存在元素,没有的话直接插入节点。有的话,首先判断插入节点和已有节点的哈希值和key值,如果相同,覆盖掉之间的节点。如果不相同,说明应该将这个节点插入红黑树或者链表。如果是插入链表,当链表长度超过阈值8时,先判断数组长度是否大于等于64时,是的话会将链表转换为红黑树结构,否则只是进行扩容。另外,当HashMap中的元素个数大于阈值时,也要进行扩容。

可以发现,HashMap的扩容时机有两个,一是当元素个数大于阈值时,二是当哈希桶的链表长度大于8,并且数组长度小于64时,接下来看看HashMap的扩容机制。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //左移一位,新容量为旧容量的2^1倍,新容量不能超过最大容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //这里是初始化时的赋值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //在这里计算新的threshold,新容量*负载因子
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //创建新的数组
    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;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //表示hash地址只有一个结点
                if (e.next == null)
                    //计算元素新的下标,直接放入
                    newTab[e.hash & (newCap - 1)] = e;
                //如果旧元素是树结点
                //split会将树分成两个链表,这是因为扩容后重新计算数组下标
                //hash值相同的结点可能会被分配到两个不同的桶中
                //然后对两个链表进行处理,根据元素数量转为链表或红黑树
                //最后放到新数组中
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //这个else表示e后有链表,拆分成两个链表,分别处理,原因同上
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    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的扩容机制:HashMap的扩容时机有两个,一是当元素个数超过一定阈值时,二是当哈希桶的链表长度大于8,并且table[]数组长度小于64时,会触发扩容。新容量会扩充到原来容量的两倍,并根据新的容量创建一个新数组。接下来,遍历旧数组中的元素,根据元素的hash值重新计算元素在新数组中的下标,并放入对应的位置。如果碰到树或者链表,首先进行节点分裂,分裂成两个链表,这是因为原来在同一个哈希桶中的元素在扩容后可能会被分到两个不同的桶中,然后分别处理将元素放到新的数组中,另外,在这个过程中,如果桶中的元素数量超过8,链表会转换为红黑树,如果元素数量小于6,红黑树会退化成链表。

再看一下树化的方法:

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //遍历链表
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        //第一次循环将root设为第一个节点,之后循环走else
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                //确定插入节点的方向,左侧还是右侧
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                //哈希值相同,比较键值
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
				
                TreeNode<K,V> xp = p;
                //p==null表示找到了插入的位置,将新节点x插入p的位置,否则回到上面继续遍历
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //红黑树的平衡调整操作
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //将最新的root节点放到数组的位置
    moveRootToFront(tab, root);
}

为什么HashMap要使用红黑树呢?先看一下红黑树的性质:

  • 每个节点非红即黑
  • 根节点是黑色的
  • 中序遍历由小到大
  • 每个叶子节点都是黑色的空节点
  • 红色节点的子节点一定是黑色的,反之不一定
  • 从任意节点到它的叶子节点的路径中,黑色节点的数量相同

红黑树的这些性质保证了红黑树的近似平衡,跟链表相比,当数据量大时,红黑树查询的时间复杂度更低,跟完全平衡树相比,红黑树节省了很多平衡调整操作。因此,红黑树在各种操作下的性能都是比较好的。

另外,注意到在HashMap中提供了这么三个方法,但是并没有实现,这些方法是提供给LinkedHashMap使用的,LinkedHashMap继承了HashMap,并重写了这三个方法,接下来分析一下LinkedHashMap。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

先看一下LinkedHashMap的数据结构,它是由一个个Entry组成的存储键值对的双向链表。Entry继承了HashMap的Node,有添加了两个前后指针。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

image-20240902170956867

LinkedHashMap插入节点时会插入到链表末尾,因此可以按照插入顺序迭代元素,LinkedHashMap直接使用HashMap的put()方法插入元素,流程是一样的,当调用newNode()方法时,LinkedHashMap进行了重写,通过linkNodeLast()将新元素插入到双向链表的表尾。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

另外,在put()中还调用了afterNodeAccess()和afterNodeInsertion(),看一下LinkedHashMap的实现。

先看afterNodeAccess(),它的作用是将元素移动到链表尾,触发时机是LinkedHashMap调用get()方法或者调用put()方法修改key的value时,根据这个机制可以想到利用LinkedHashMap来实现LRU缓存,将最近使用的元素移到链表末尾,注意需要设置accessOrder为true才能使用这个方法。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

再来看一下afterNodeInsertion()方法,它的作用是移除链表头的元素,触发时机是添加完一个元素之后。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

不过这个方法需要满足removeEldestEntry(first)这个方法为true,它默认返回false,如果我们想利用它实现LRU缓存,可以这样重写,当元素数量超过缓存的容量了,就删除表头的元素,因为表头是最久没有使用的缓存。

protected boolean removeEldestEntry(Map.Entry < K, V > eldest) {
    return size() > capacity;
}

还有一个方法,afterNodeRemoval(),这个也很简单,就是删除元素之后维护一下前后指针。

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

HashMap是线程不安全的,多线程操作HashMap时可能会出现一些线程安全问题,举几个例子:

1、两个线程进行put操作,当同时执行newNode()方法时,会导致第一个线程的元素丢失。

2、一个线程put,一个线程get,当put时恰好需要扩容,扩容过程中会创建一个新数组并赋值,在这个过程中,另一个线程可能get到空值。

若想线程安全的使用HashMap,可以使用ConcurrentHashMap。

在java8之前,ConcurrentHashMap通过分段锁机制来实现线程安全,ConcurrentHashMap采用的是Segment数组加HashEntry数组的结构,每个Segment包含一个HashEntry数组,由于Segment继承了ReentrantLock,它本身就是一个锁。因此只要hash值足够分散,多线程put的时候就会put到不同的Segment中,多个线程不会互相影响,put的时候,当前的Segment会锁住,从而保证线程安全。

在java8之后,ConcurrentHashMap改成和Node数组加链表红黑树的结构,通过对Node数组加锁来实现线程安全。如果添加数据的哈希地址是空的,通过自旋和CAS操作插入,否则对Node结点加锁,然后插入到链表或者红黑树中。

看一下ConcurrentHashMap的put的源码:

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //数组为空,初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //f表示数组待插入位置下标的元素
        //如果是空的,CAS插入新元素
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //如果正在扩容,帮忙一起扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        //如果不是空的,说明要插入链表或红黑树
        else {
            V oldVal = null;
            //对Node节点加锁,也就是对要插入的桶加锁
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    //如果是链表
                    if (fh >= 0) {
                        binCount = 1;
                        //遍历链表,插入元素
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //如果key相同,覆盖旧值
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            //尾插插入新元素
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //新元素插入树中
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                //链表长度大于阈值8,转红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

这段代码中有一个地方,通过if (fh >= 0)来判断是链表,这是因为ConcurrentHashMap和HashMap对树的存储不太一样,ConcurrentHashMap中树的根节点是一个TreeBin类型的节点,不存储元素,TreeBin节点的Hash值是-2,而HashMap中,树的根节点是直接存储元素的。

标签:分析,Node,hash,HashMap,else,链表,源码,key,null
From: https://www.cnblogs.com/Linwei33/p/18409986

相关文章

  • jdk动态代理源码分析
    jdk动态代理源码分析//test.javapublicclasstest{publicstaticvoidmain(String[]args){MyServicemyService=newMyServiceImpl();MyInvocationHandlermyInvocationHandler=newMyInvocationHandler(myService);System.getPropert......
  • ThreadLocal源码分析-
    ThreadLocal源码分析ThreadLocal是解决线程安全问题的一种方法,它通过为每个线程提供一个独立的变量副本避免了变量并发访问的冲突问题。一个ThreadLocal变量只与当前自身线程相关,对其他线程是隔离的。下面这段代码展示了ThreadLocal的使用。publicclasstest{privatesta......
  • SpringBoot源码分析
    Springboot源码分析1、SpringApplication初始化从run()方法进入,可以看到Springboot首先创建了SpringApplication,然后调用SpringApplication的run()方法。publicstaticConfigurableApplicationContextrun(Class<?>[]primarySources,String[]args){return(newSprin......
  • 密码算法设计与分析 - 课程笔记
    基本概念安全威胁安全威胁被动攻击消息内容获取业务流分析主动攻击中断(可用性)篡改(完整性)伪造(真实性)人为威胁被动攻击被动攻击即窃听,是对系统的保密性进行攻击,如搭线窃听、非法拷贝等,以获取他人的信息。被动攻击分类:消息内容获取:直接对消息内容进行窃听,......
  • 收银系统源码、连锁店收银系统源码-收银台高频使用功能
    收银系统成为门店高频使用的软件工具,除了正常扫描商品、商品称重、收银结账、会员管理、处理订单以外,还有哪些功能也是门店日常经常会使用的功能呢?1.单品改价、单品打折门店可以给收银员开通权限,收银员在收银结算时可以给单个商品进行改价或者打折,最低优惠金额和最高优惠金额都是......
  • NLP(文本处理技术)在数据分析中的应用实例
    在Python中,你可以实现多种自然语言处理(NLP)技术。Python拥有丰富的库和框架,使得NLP任务变得更加容易和高效。接下来将列举一些NLP(文本处理技术)具体功能的Python实现。一:文本预处理1:英文版#文本预处理#导入所需的库importrefromtextblobimportTextBlobfromgensim......
  • 农产品交易网站 毕业设计-附源码
    摘 要随着互联网大趋势的到来,社会的方方面面,各行各业都在考虑利用互联网作为媒介将自己的信息更及时有效地推广出去,而其中最好的方式就是建立网络管理系统,并对其进行信息管理。由于现在网络的发达,农产品交易的信息通过网络进行信息管理掀起了热潮,所以针对农产品交易信息管......
  • 微信阅读小程序设计与实现-计算机毕业设计源码+LW文档
    摘 要由于APP软件在开发以及运营上面所需成本较高,而用户手机需要安装各种APP软件,因此占用用户过多的手机存储空间,导致用户手机运行缓慢,体验度比较差,进而导致用户会卸载非必要的APP,倒逼管理者必须改变运营策略。随着微信小程序的出现,解决了用户非独立APP不可访问内容的痛点,所以很......
  • 毕业设计—基于SpringBoot的个人博客系统 (案例分析)
    摘 要随着科学技术的飞速发展,社会的方方面面、各行各业都在努力与现代的先进技术接轨,通过科技手段来提高自身的优势,个人博客系统当然也不能排除在外。个人博客系统是以实际运用为开发背景,运用软件工程开发方法,采用Java技术构建的一个管理系统。整个开发过程首先对软件系统......
  • 最新PHP在线客服系统I聊天源码网页端在线客服系统 带教程
    安装教程1.上传源码压缩包到网站目录并解压2.设置网站运行目录public(防跨站不要勾选)3.设置伪静态,选择thinkphp4.进入网站目录,打开终端 输入启动命令5.宝塔配置开启1238和2346端口后台登录地址:https://域名/admin详细教程查看压缩包中的安装说明.doc文档效果展示......