HashMap源码剖析

最新推荐文章于 2022-03-19 18:43:12 发布
最新推荐文章于 2022-03-19 18:43:12 发布
阅读量265 收藏 1
点赞数 1
分类专栏： Java 文章标签： HashMap源码
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_40438165/article/details/114303924
版权

\quad 红黑树底层实现是数组+链表+红黑树。大体逻辑是：

  • 创建一个长度为2的幂大小的数组table，里面存放Node节点
  • 当一个键值对插入散列表时，首先计算当前键值对Key的hash值，根据寻址算法(index=(table.length-1)&hash(key))，这样每一个键Key都能映射到[0,table.length-1]的区间中去
  • 当多个键值对的Key对应的hash值相同时，会在其对应的位置形成链表或者红黑树，当相同hash值Key数目达到8个时，会从链表树化为红黑树；反之当其数目减少到6个时，会从红黑树退化为链表
  • 数组table长度过小而插入数据过多时，会产生大量hash冲突，例如当table长度为16，散列表中数据量达到1600个时，table中至少有一个位置对应的链表或者红黑树大小大于等于100。因此需要根据插入数据量动态扩容
  • 当数据量=table.length*负载因子(默认0.75)时会引发扩容操作，table长度变为原来的两倍，原table中数据经过重新寻址一一放入新的table

一、源码中各个属性和默认值

1、散列表初始容量，即初始数组长度，默认为16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

2、散列表最大容量，即table数组最大长度，为 2 30 2^{30} 230

static final int MAXIMUM_CAPACITY = 1 << 30;

3、负载因子：当元素个数>table长度*复杂因子时，table会扩容为之前的两倍

static final float DEFAULT_LOAD_FACTOR = 0.75f;

4、树化阈值：当树元素个数大于等于8个时由链转为红黑树

static final int TREEIFY_THRESHOLD = 8;

5、链化阈值：当树元素个数小于等于6个时会从红黑树转为链表

static final int UNTREEIFY_THRESHOLD = 6;

6、最小树化阈值：当所有元素个数达到64且当前链表长度达到8才会树化

static final int MIN_TREEIFY_CAPACITY = 64;

7、table表：采用懒加载机制，第一次使用put时才会初始化，长度始终为2的幂，当元素个数*负载因子大于当前table长度时引发扩容

transient Node<K,V>[] table;

8、当前散列表中元素个数

transient int size;

9、modCount：结构改变的次数，每次put和remove和clear等操作都会使得该参数+1，如果modCount改变的不符合预期，那么就会抛出异常，在一些非多线程安全的情况下，通过这个modCount参数 检测是否有出现混乱的情况，会自动抛出异常。

transient int modCount;

10、threshold：表示当HashMap的size大于threshold时会执行resize操作。threshold=capacity*loadFactor

int threshold;

11、loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity

final float loadFactor;

二、构造函数

\quad 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);
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

\quad 如果传入初始容量，那么使用第一个构造函数，考虑到用户传入的初始容量不一定是2的整数次幂，因此使用静态方法tableSizeFor进行处理，该函数返回大于等于当前传入值的最小的2的整数次幂的数值，例如传入9则返回16。

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

三、put操作

\quad 往散列表中加入键值对，会有如下处理：

  • 计算该键值对key的hash值，根据hash值使用寻址算法找到对应table中的地址，寻址算法：(table.length-1)&hash(key)
  • 如果当前地址无元素，直接插入即可
  • 如果当前位置有元素，且是链，则依次遍历该链，如果在该链中发现与当前插入key相同的其他节点，则更新该节点值并返回；如果没有，则在该链后面加入要插入元素，如果插入该元素后链长度达到8，则进行树化，使用treeifyBin函数将链表转变为红黑树
  • 如果当前位置有元素，且已经是红黑树，则将该值插入红黑树中，具体插入逻辑在后续红黑树讲
  • 如果成功添加了元素，表明散列表结构被修改，size++，modCount++，达到扩容阈值时还需要使用resize函数对table进行扩容
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    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;
        if ((tab = table) == null || (n = tab.length) == 0)  // 延迟初始化，第一次调用时才初始化
            n = (tab = resize()).length;
        // 路由寻址: (n-1)&hash
        // 第一种情况：当前位置无元素，直接放进即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {  // 第二种情况：当前位置有数据，可能是链表也可能是红黑树
            // e：node临时元素
            // k：临时变量存key
            Node<K,V> e; K k;
            // 当前位置元素与要插入的元素的key完全一样，表示后面需要进行替换操作，此时e不为null
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 当前位置元素已经是红黑树的节点
            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) {  // 如果没有元素与当前插入的key相等，则在链表末尾加入该数据
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);  // 链表长度大于等于8，树化
                        break;
                    }
                    if (e.hash == hash &&  // 找到与当前插入key相等的节点
                            ((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;
            }
        }
        // 散列表被修改次数++，替换不算，替换操作已提前return
        ++modCount;
        if (++size > threshold)  // 散列表大小+1，若大于扩容阈值则扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

四、resize操作
\quad 当执行put等需要往散列表中添加元素的操作时，使得散列表中元素个数增加，当元素个数达到当前散列表的阈值，即table.length*load_factor时，会引发table扩容为原来的两倍，流程如下：

  • 1、计算扩容后新的table的长度newCap和新的扩容阈值
  • 2、新开一个newTable，大小为newCap
  • 3、遍历老的table，对于其每一个位置(也可以称为每一个桶)，遍历每个桶对应的所有元素，按照如下规则放入新的table中
    • a)如果该桶只有一个元素，则将该元素key的hash值通过寻址算法找到对应newTable中地址后放入
    • b)如果该桶对应链表结构，则新建低位链表和高位链表作为临时变量，遍历原链表，如果原链表的hash值有高位不为0的情况，则放入高位链表，否则放入低位链表。低位链表扩容后位置与扩容前位置一样，高位链表扩容后位置=扩容前位置+扩容前table长度
    • c)如果该桶对应红黑树，则调用split函数进行节点的重新放置，与红黑树相关的操作在后续统一讲解
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;  // 扩容前的哈希表
    // 扩容前table长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容前的扩容阈值，也就是触发本次扩容的阈值
    int oldThr = threshold;
    // 扩容之后的table长度和新的扩容阈值
    int newCap, newThr = 0;
    // 条件如果成立说明散列表之前已经初始化过
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {  // 不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY) // 扩容前数组长度大于等于16，阈值才翻倍
            newThr = oldThr << 1; // double threshold
    }
    // 散列表之前没有初始化过，但在构造函数中指明了初始容量，此时新的容量=初始容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 没有指明初始容量，用默认值，大小为16，扩容阈值为16*0.75=12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {  // 新的更新阈值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;  // 在全局变量更新扩容阈值

    // 上面代码即计算了新的扩容的table长度和新的扩瞳阈值，接下来才是正儿八经的扩容操作
    @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) {
            // 依次遍历oldtable中各个头节点
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)  // 当前节点只有头节点，直接把这个点放入新的table中去
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)  // 当前头节点对应一棵树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order 当前头节点对应链表
                    // 低位链表和高位链表，低位链表扩容后位置与扩容前位置一样
                    // 高位链表扩容后位置=扩容前位置+扩容前table长度
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 根据高位是否位0拆分位低位和高位
                        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;
}

五、get操作

\quad 使用get操作可以取出散列表中对应key的值，get操作很简单，分为以下几步：

  • 计算key的hash值，通过寻址算法找到对应table的下标，如果table下标对应的节点为null，直接返回null表示无此元素
  • 令改下标对应的节点为头节点，如果该节点的key与输入的key一致，则返回该节点的值
  • 否则分两种情况：
    • 当前节点是树节点，则使用getTreeNode函数去红黑树里面查找即可，与二叉搜索树查找流程一样
    • 当前节点是链表节点，去依次遍历链表即可
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(key)) == null ? null : e.value;
    }

    /**
     * Implements Map.get and related methods.
     *
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(Object key) {
        // first，桶位中头元素
        Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & (hash = hash(key))]) != null) {
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)  // 去树里找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {  // 链表中去找
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

六、remove操作

\quad remove函数与get函数流程一样，不同之处在于找到键为key的元素后进行了删除该节点的操作。相信在链表中删除节点很容易，但在红黑树中就会复杂一些。

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

    /**
     * Implements Map.remove and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        // index：寻址结果
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            // node：表示查找到的结果
            // e：当前node的下一个元素
            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);
                }
            }
            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;
    }

七、其他操作

1、clear：清除散列表中所有元素

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

2、containsKey：判断是否存在某个键，其底层也是调用的getNode

public boolean containsKey(Object key) {
    return getNode(key) != null;
}

3、containsValue：判断是否存在某个值，这个只能依次遍历散列表中所有节点的值来判断了，时间复杂度为 O ( n ) O(n) O(n)

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (Node<K,V> e : tab) {
            for (; e != null; e = e.next) {
                if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

4、size和isEmpty

public int size() {
    return size;
}
public boolean isEmpty() {
    return size == 0;
}

5、keySet和values

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

6、replace：替换键位key的节点，将其复制为传入的value

public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}
HashMap源码解析
拯救地球好累
08-01 353
本来我是准备要先看HashSet的源码，但是发现HashSet内部的实现全是由HashMap实现的，所以我觉得看完HashMap再看HashSet会更容易理解一点。 我们先来看看官方给出的HashMap的解释： 哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable ...
HashMap源码剖析共10页.pdf.zip
10-29
《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构，它属于集合框架的一部分，提供了键值对（Key-Value）的存储方式。HashMap在内部使用了一个数组和链表来实现，实现了快速的查找、插入和删除...
HashMap源码分析
和大黄的博客
02-24 8621
1、hashmap的数据结构 要知道hashmap是什么，首先要搞清楚它的数据结构，在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）。 上图中，X轴方向为HashMap的数组容器，Y轴方向，为每个相应位置的单向链表。每一个元素都是一个包含如图所示四个属性，k
Java集合框架之三：HashMap源码解析
weixin_30915275的博客
02-24 122
版权声明：本文为博主原创文章，转载请注明出处，欢迎交流学习！ HashMap在我们的工作中应用的非常广泛，在工作面试中也经常会被问到，对于这样一个重要的集合模型我们有必要弄清楚它的使用方法和它底层的实现原理。HashMap是通过key-value键值对的方式来存储数据的，通过put、get方法实现键值对的快速存取，这是HashMap最基本的用法。HashMap底层是通过数组和链...
通俗易懂Hashmap源码解析
xadasss的博客
05-14 6737
Hashmap源码解析 一、Hashmap数据结构 哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。 比如上图中，一共有13个桶0-12，当哈希值是01时，就会被放到1桶中，如果是14，对13取模之后也是1，所以也会被放到1桶中。由于1桶有两个数据，就会形成一个链表。 这里需要注意的是，如果链表大小超
Java集合面试题详解-从数据结构到HashMap源码剖析
最新发布
02-06
随后，文中详细分析了Java常用集合类ArrayList、LinkedList、HashMap的工作原理及时空复杂度；并对面试题进行了详细的解析和演示。真实面试还原模块则生动模拟面试过程，以帮助求职者熟悉面试问答环节，提高实战能力...
JavaHashSet和HashMap源码剖析编程开发技术
11-22
本篇技术文档将深入剖析这两类数据结构的源码，帮助开发者理解其内部实现原理，提升在实际开发中的应用能力。 HashSet类是基于HashMap实现的，它不包含重复元素，并且不保证集合中元素的顺序。在HashSet中，元素的...
深入理解Java之HashMap源码剖析
08-31
深入理解Java中的HashMap源码，有助于我们更好地掌握这个常用数据结构的工作原理。HashMap是Java集合框架的重要组成部分，它实现了Map接口，提供了一种快速查找、插入和删除元素的方式。本文将详细解析HashMap的内部...
数据结构之HashMap 源码解析
Taylar_where的博客
05-04 1438
参考博文：https://fangjian0423.github.io/2016/03/29/jdk_hashmap/ 参考文章:http://wiki.jikexueyuan.com/project/java-enhancement/java-twentythree.html 1. HashMap实现了Map 接口，继承 AbstractMap。其中 Map 接口定义了键映射到值的规...
【Java】HashSet底层机制及源码分析
dengmsjava的博客
03-19 1029
（1）HashSer底层是HashMap，HashMap底层是数组+链表+红黑树； （2）添加一个元素时，先得到hash值（会转成索引值），找到存储数据表table，判断这个索引位置是否已经存放元素，如果没有存放，则直接加入；如果有，则调用equals比较，如果相同，就放弃添加，如果不相同，则添加到链表最后； （3）在JDk 8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table的大小≥MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）。
hashmap源码剖析
04-25
好的，我可以为您讲解一下HashMap的源码剖析。 HashMap是一个基于哈希表实现的Map接口的实现类，它使用一个数组来保存数据，每个数据项被映射到数组的索引位置上。HashMap的主要实现思路是利用哈希函数将键映射到...
评论 1
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值