铁锤的IT奇妙探险 Java Back-End Coder

HashMap原理入门

2020-07-03

数据结构
   

HashMap以其优秀的增删改性能，成为最常用的实现类之一，本文将对JDK8的HashMap源码进行讲解。

HashMap

HashMap源码解析

属性和构造方法

// HashMap 初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// HashMap 最大长度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824

// 默认的加载因子 (扩容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 当链表长度大于此值且容量大于 64 时
static final int TREEIFY_THRESHOLD = 8;

// 转换链表的临界值，当元素小于此值时，会将红黑树结构转换成链表结构
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树容量
static final int MIN_TREEIFY_CAPACITY = 64;
  1. 加载因子也叫扩容因子或负载因子，用来判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。
  2. 加载因子较大的时候，扩容发生频率低，占用空间下，但发生hash冲突的概率会提升，加载因子较小时，扩容会比较频繁，因此会占用更多的空间，此时发生hash冲突的可能性较小，因为0.75是平衡两者得出的结果。
  3. 链表长度达到8时便会转化为红黑树结构，而阈值小于6时，红黑树才会转换为链表结构，这是为了避免频繁的结构转换带来的消耗
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
 
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取该map的实际长度
        int s = m.size();
        if (s > 0) {
            //判断table是否初始化，如果没有初始化
            if (table == null) { // 
                /**求出需要的容量，因为实际使用的长度=容量*0.75得来的，+1是因为小数相除，基本都不会是整数，容量大小不能为小数的，后面转换为int，多余的小数就要被丢掉，所以+1**/
                float ft = ((float)s / loadFactor) + 1.0F;
                //判断该容量大小是否超出上限。
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                /**对临界值进行初始化，tableSizeFor(t)这个方法会返回大于t值的，且离其最近的2次幂**/
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //如果table已经初始化，则进行扩容操作，resize()就是扩容。
            else if (s > threshold)
                resize();
            //遍历，把map中的数据转到hashMap中。
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

该构造函数，传入一个Map，然后把该Map转为hashMap，entrySet方法会返回一个Set<Map.Entry<K, V»，泛型为Map的内部类Entry，Map中的每一个key-value就是一个Entry实例。其余的几个构造函数都是以初始容量或加载因子为参数。

查询

public V get(Object key) {
    Node<K,V> e;
    // 对 key 进行哈希操作
    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;
    // 非空判断
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != 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) {
            // 如果第一节点是树结构，则使用 getTreeNode 直接获取相应的数据
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 非树结构，循环节点判断
                // hash 相等并且 key 相同，则返回此节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

通过hashCode和key来确定我们要找的节点，然后再调用节点的value属性并返回。

新增

public V put(K key, V value) {
    // 对 key 进行哈希操作
    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;
    // 哈希表为空则创建表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根据 key 的哈希值计算出要插入的数组索引 i
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果 table[i] 等于 null，则直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果 key 已经存在了，直接覆盖 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 key 不存在，判断是否为红黑树
        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) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //  key 已经存在直接覆盖 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;
        }
    }
    //这一步操作足以说明HashMap是线程不安全的
    ++modCount;
    // 超过最大容量，扩容，从尾部插入新节点
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
  1. JDK8之前新节点的插入采用的是头插法，JDK8之后改成了尾插法
  2. 采用头插法会造成死链，当两个线程同时出发扩容时，在移动节点时会导致一个链表的两个节点互相引用，从而生成环链表
  3. 扩容方法resize():1.8之前扩容会重新计算每个元素的哈希值，1.8后通过高位运算来确定元素是否需要移动
  4. 扩容后新的下标位置=原下标位置+原数组长度

删除

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

final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
//matchValue表示是否删除key，movable表示删除后是否移动节点

核心思路：判断哈希数组是否为空，获取待删除节点的下标，先判断是链表结构还是红黑树，遍历搜索该节点，找到后判断matchValue，再判断是链表还是红黑树，然后删除，返回节点。

参考博客

HashMap线程不安全

  • 原因:++modCount操作
  • 举例：多个线程同时put，且put的key相同，发生碰撞，最终只会保留一个数据
  • 可见性不能得到保证

Similar Posts

上一篇 带你解析ThreadPoolExecutor最底层

下一篇 设计模式之工厂模式

Comments

Content