郑佳伟 Blog

保温杯里泡枸杞

Java

HashMap详解

郑佳伟

image-20200930090156442

结构上，底层使用数组+单向链表+红黑树的结构，节点数大于8时会转为红黑树，节点数小于6时会转为单向链表。

首先每一个元素都是链表的数组，当添加一个元素（key-value）时， 就首先计算元素 key 的 hash 值，以此确定插入数组的位置，但是可能存在同一 hash 值的元素已经被放到数组的同一位置，这是就添加到同一 hash 值的元素的后面，他们在数组的同一位置形成链表，同一链表上的 Hash 值是相同的，所以说数组存放的是链表，而当链表长度太长时，链表就转换为红黑树。

当链表数组的容量超过初始容量的 0.75 时，再散列将链表数组扩大 2 倍，把原链表数组的元素搬移到新的数组中

直接看源码。

常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 初始容量为2的4次方即16(aka:Also Known As)

static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量为2的30次方

static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子，当数量达到容量的0.75倍则扩容

static final int TREEIFY_THRESHOLD = 8; // 树化阈值8，即节点数大于8时会转为红黑树

static final int UNTREEIFY_THRESHOLD = 6; // 树退化阈值，即节点数小于6时会转为单向链表

static final int MIN_TREEIFY_CAPACITY = 64; // 最小树形化阈值，红黑树最小长度为 64

成员变量

transient Node[] table; // HashMap的哈希桶数组，用于存放表示键值对数据的Node元素。

transient Set> entrySet; // HashMap将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。

transient int size; // HashMap中实际存在的键值对数量

transient int modCount; // HashMap的数据被修改的次数，这个变量用于迭代过程中的Fail-Fast机制，其存在的意义在于保证发生了线程安全问题时，能及时的发现（操作前备份的count和当前modCount不相等）并抛出异常终止操作。

int threshold; // 扩容阈值，当HashMap的size大于threshold时就会执行resize操作自动扩容容量为原来的二倍

final float loadFactor; // 负载因子，默认值为0.75f，计算HashMap的实时装载因子的方法为：size/capacity

构造函数

//指定容量大小和负载因子大小
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; // all other fields defaulted
}

//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

数据结构

数组元素Node<K,V>[]

是HashMap内部的静态类：

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

    // Node构造函数Node
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = 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;
    }

    // 判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
    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;
    }
}

红黑树TreeNode<k,v>

也是HashMap内部的静态类，TreeNode的代码很多，分类来看：

成员变量和构造方法

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

方法

// 返回当前节点的根节点  
final TreeNode<K,V> root() {...}

// 将跟节点移至最前
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {...}

// 使用给定的哈希和键，从根节点p开始查找指定的节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {...}

// 为根节点调用find()方法
final TreeNode<K,V> getTreeNode(int h, Object k) {...}

// 用于不可比较或HashCode相同时进行比较的方法
static int tieBreakOrder(Object a, Object b) {...}

// 构建红黑树
final void treeify(Node<K,V>[] tab) {...}

// 树退化
final Node<K,V> untreeify(HashMap<K,V> map) {...}

// 键值对插入红黑树
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {...}

// 移除树节点
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {...}

// 在HashMap进行扩容时会调用到
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {...}

// 左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {...}

// 右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {...}

// 插入平衡算法（插入后）
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {...}

// 删除平衡算法
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {...}

// 检查不变量
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {...}

HashMap常用方法

Hash值计算

// 将传入的参数key本身的hashCode与h无符号右移16位进行二进制异或运算得出一个新的hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put()方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);// 这里传入了计算后的hash值
}

putVal()方法：

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为空，则使用resize扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根据传入的hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 新建节点
    else {
        // 当table[i]!=null时
        Node<K,V> e; K k;
        // 如果table[i]的首个元素和key相同，则直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果table[i]的首个元素和key相同，则直接覆盖
        else if (p instanceof TreeNode)
          // 如果table[i]的首个元素和key不相同，则先判断table[i]是否为红黑树，若是则直接在树中插入键值对
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
          // 如果table[i]不是红黑树，则判断链表长度是否大于8，大于8将链表转换为红黑树，再执行插入操作
          // 否则进行链表的插入操作
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 若节点数大于等于8
                      // 转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key:key已经存在，将新value替换旧value值具体操作
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) // 判断是否需要扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

  • 获取Node数组table对象和长度，并判断table是否为空：

    • 若table为空，则调用resize()扩容；

    • 若table不为空，判断要插入的key和插入位置的元素是否相同：

    • 若相同，则直接覆盖；

    • 若不同，则先判断是否是红黑树：

      • 若是红黑树，则按红黑树的方式插入；
      • 若不是红黑树，则判断其长度是否大于8，大于8则先转为红黑树，再执行插入，否则进行链表的插入操作

  • 最后判断是否需要扩容。

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;
  // 当table不为null，table长度大于0，指定位置不为null时，才更进一步查询，否则直接返回null。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node 先判断第一个存在的节点的key是否和查询的key相等。
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;// 如果相等，直接返回该节点。
        if ((e = first.next) != null) { // 若first节点和要查询的不一致，且其下一个节点不为null时。
            if (first instanceof TreeNode)
              // 当这个table节点上存储的是红黑树结构时，在根节点first上调用getTreeNode方法，在内部遍历红黑树节点，查看是否有匹配的TreeNode。
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
              // 当这个table节点上存储的是链表结构时，则检索链表来查询结果。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e; // 成功后返回。
            } while ((e = e.next) != null);
        }
    }
    return null;
}
  • 首先table要满足三个条件才能继续深入查询：table不为null，table长度大于0，指定位置不为null。
  • 先判断第一个存在的节点的key是否和查询的key相等。
    • 如果相等，则直接返回该节点。
    • 如果不想等，则判断它的下一个节点是否为null。
    • 当table的这个节点上为红黑树结构时，在根节点first上调用getTreeNode方法，在内部遍历红黑树节点，查看是否有匹配的TreeNode
    • 当这个table节点上存储的是链表结构时，则检索链表来查询结果。

resize()方法（扩容机制）

重新设置table大小，并返回新的HashMap的数据。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 旧table
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的容量
    int oldThr = threshold; // 扩容前的扩容阈值
    int newCap, newThr = 0; // 扩容后的容量，扩容后的扩容阈值

    if (oldCap > 0) { // 若扩容前的容量大于0
        if (oldCap >= MAXIMUM_CAPACITY) { // 若扩容前的容量若超过最大容量，则不再进行扩充
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
      // 若扩容后的容量小于最大容量，且扩容前的长度大于等于默认的初始化长度
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) 
            newThr = oldThr << 1; // double threshold 则扩容为原来的二倍
    }
  // 若扩容前的容量为0，且扩容前的扩容阈值大于0
    else if (oldThr > 0) // initial capacity was placed in threshold
      // 则扩容后的容量设为扩容前的扩容阈值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 若扩容前的容量为0，且扩容前的扩容阈值也为0，则新阀值和新容量使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
      // 如果新阈值为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""})
  //创建新的 Hash 表
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
      //遍历旧的 Hash 表
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 释放旧空间
                if (e.next == null) // 当这个节点只有一个数据时
                    newTab[e.hash & (newCap - 1)] = e; // 将这个数据直接赋给新table中指定的hash位置
                else if (e instanceof TreeNode) // 当这个节点是一个红黑树时，则按红黑树的方式赋给新table
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                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的结构以及核心源码分析

网站 http://bladerunner.plus/
文章已创建 17

相关文章

开始在上面输入您的搜索词，然后按回车进行搜索。按ESC取消。

返回顶部