HashMap 源码分析

这一篇文章是关于ConcurrentHashMap 源码分析 ConcurrentHashMap 源码分析

HashMap简介

JDK1.8 之前 HashMap 由 数组+链表 组成的, 数组是 HashMap 的主体, 链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。

JDK1.8 之后 HashMap 的组成多了红黑树, 在满足下面两个条件之后, 会执行链表转红黑树操作, 以此来加快搜索速度。

• 链表长度大于阈值(默认为 8)
• HashMap 数组长度超过 64

HashMap底层数据结构分析

JDK1.8 之前

JDK1.8之前数据结构图

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值, 然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度), 如果当前位置存在元素的话, 就判断该元素与要存入的元素的 hash 值以及 key 是否相同, 如果相同的话, 直接覆盖, 不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化, 但是原理不变。

static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // >>>:无符号右移, 忽略符号位, 空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 , JDK 1.7 的 hash 方法的性能会稍差一点点, 因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组, 数组中每一格就是一个链表。若遇到哈希冲突, 则将冲突的值加到链表中即可。

JDK1.8 之后

HashMap类

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,  Cloneable,  Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始桶容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 桶最大值
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的负载因子(0.75)
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // table 真正存放数据的数组, 总是2的幂次倍
    transient Node<k, v>[] table;
    // 存放具体元素的集
    transient Set<map.entry<k, v>> entrySet;
    // 存放元素的个数, 注意这个不等于数组的长度
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 临界值 当实际大小(容量*填充因子)超过临界值时, 会进行扩容, 可在初始化时显式指定
    int threshold;
    // 负载因子, 可在初始化时显式指定
    final float loadFactor;
}

• loadFactor 加载因子

  loadFactor 加载因子是控制数组存放数据的疏密程度, loadFactor 越趋近于 1, 那么 数组中存放的数据(entry)也就越多, 也就越密, 也就是会让链表的长度增加, loadFactor 越小, 也就是趋近于 0, 数组中存放的数据(entry)也就越少, 也就越稀疏。

  loadFactor 太大导致查找元素效率低, 太小导致数组的利用率低, 存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

  给定的默认容量为 16, 负载因子为 0.75。Map 在使用过程中不断的往里面存放数据, 当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容, 而扩容这个过程涉及到 rehash、复制数据等操作, 所以非常消耗性能。

• threshold

  threshold = capacity \* loadFactor, 当 Size>=threshold**的时候, 那么就要考虑对数组的扩增了, 也就是说, 这个的意思就是 **衡量数组是否需要扩增的一个标准。

HashMap 源码分析

构造方法

HashMap 中有四个构造方法, 它们分别如下：

// 默认构造函数。
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
    }

    // 包含另一个“Map”的构造函数
    public HashMap(Map<? extends K,  ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m,  false);//下面会分析到这个方法
    }

    // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity,  DEFAULT_LOAD_FACTOR);
    }

    // 指定“容量大小”和“加载因子”的构造函数
    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);
    }

putMapEntries 方法：

final void putMapEntries(Map<? extends K,  ? extends V> m,  boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化, s为m的实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值, 则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化, 并且m元素个数大于阈值, 进行扩容处理
        else if (s > threshold)
            resize();
        // 将m中的所有元素添加至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);
        }
    }
}

put方法

HashMap 只提供了 put 用于添加元素, putVal 方法只是给 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尚未初始化, 则此处进行初始化数组, 并赋值初始容量, 重新计算阈值
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中, 桶为空, 新生成结点放入桶中(此时, 这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
         // 通过hash找到下标, 如果hash值指定的位置数据为空, 则直接将数据存放进去
        tab[i] = newNode(hash,  key,  value,  null);
    else {
        //如果通过hash找到的位置有数据, 发生碰撞
        Node<K, V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等, key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e, 用e来记录
                e = p;
        // hash值不相等, 即key不相等；为红黑树结点
        else if (p instanceof TreeNode)
            // 如果此时桶中数据类型为 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);

                    // 结点数量达到阈值(默认为 8 ), 执行 treeifyBin 方法
                    // 这个方法会根据 HashMap 数组来决定是否转换为红黑树。
                    // 只有当数组长度大于或者等于 64 的情况下, 才会执行转换红黑树操作, 以减少搜索时间。否则, 就是只是对数组扩容。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab,  hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等, 跳出循环
                    break;
                // 用于遍历桶中的链表, 与前面的e = p.next组合, 可以遍历链表
                p = e;
            }
        }
        // 经过上面的循环后, 如果e不为空, 则说明上面插入的值已经存在于当前的hashMap中, 那么更新指定位置的键值对
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) {
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 如果此时hashMap size大于阈值, 则进行扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

从代码看, put方法分为三种情况：

• table尚未初始化, 对数据进行初始化

• table已经初始化, 且通过hash算法找到下标所在的位置数据为空, 直接将数据存放到指定位置

• table已经初始化, 且通过hash算法找到下标所在的位置数据不为空, 发生hash冲突(碰撞), 发生碰撞后, 会执行以下操作：

  • 判断插入的key如果等于当前位置的key的话, 将 e 指向该键值对
  • 如果此时桶中数据类型为 treeNode, 使用红黑树进行插入
  • 如果是链表, 则进行循环判断, 如果链表中包含该节点, 跳出循环, 如果链表中不包含该节点, 则把该节点插入到链表末尾, 同时, 如果链表长度超过树化阈值(TREEIFY_THRESHOLD)且table容量超过最小树化容量(MIN_TREEIFY_CAPACITY), 则进行链表转红黑树(由于table容量越小, 越容易发生hash冲突, 因此在table容量<MIN_TREEIFY_CAPACITY 的时候, 如果链表长度>TREEIFY_THRESHOLD, 会优先选择扩容, 否则会进行链表转红黑树操作)

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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 根据hash算法找到对应位置的第一个数据, 如果是指定的key, 则直接返回
        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;
}

get方法相对于put来说, 逻辑实在是简单太多了

• 根据hash值查找到指定位置的数据
• 校验指定位置第一个节点的数据是key是否为传入的key, 如果是直接返回第一个节点, 否则继续查找第二个节点
• 如果数据是TreeNode(红黑树结构), 直接通过红黑树查找节点数据并返回
• 如果是链表结构, 循环查找所有节点, 返回数据
• 如果没有找到符合要求的节点, 返回 null

在这个方法里面, 需要注意的有两个地方：hash(key)和hash的取模运算 (n - 1) & hash

resize 方法

resize()进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

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倍
        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 {
        // signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap 常用遍历

// 第一种
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
    Map.Entry<String, Integer> next = entryIterator.next();
    System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}

// 第二种
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    String key = iterator.next();
    System.out.println("key=" + key + " value=" + map.get(key));
}

建议使用第一种 EntrySet 进行遍历。第一种可以把 key value 同时取出，第二种还得需要通过 key 取一次 value，效率较低