乐趣区

关于java:阅读源码HashMap回顾

jiezi

本文一是总结后面两种汇合，补充一些脱漏，再者对 HashMap 进行简略介绍。

回顾

因为前两篇 ArrayList 和 LinkedList 都是针对独自的汇合类剖析的，只见树木未见森林，明天剖析 HashMap，能够联合起来看一下 java 中的汇合框架。下图只是一小部分，而且为了不便了解去除了抽象类。

Java 中的汇合（有时也称为容器）是为了存储对象，而且少数时候存储的不止一个对象。

能够简略的将 Java 汇合分为两类：

  • 一类是 Collection，存储的是独立的元素，也就是单个对象。细分之下，常见的有 List，Set，Queue。其中 List 保障依照插入的顺序存储元素。Set 不能有反复元素。Queue 依照队列的规定来存取元素，个别状况下是“先进先出”。
  • 一类是 Map，存储的是“键值对”，通过键来查找值。比方事实中通过姓名查找电话号码，通过身份证号查找集体详细信息等。

    实践上说咱们齐全能够只用 Collection 体系，比方将键值对封装成对象存入 Collection 的实现类，之所以提出 Map，最次要的起因是效率。

HashMap 简介

HashMap 用来存储键值对，也就是一次存储两个元素。在 jdk1.8 中，其实现是基于数组 + 链表 + 红黑树，简略说就是一般状况间接用数组，产生哈希抵触时在抵触地位改为链表，当链表超过肯定长度时，改为红黑树。

能够简略了解为：在数组中寄存链表或者红黑树。

  1. 齐全没有哈希抵触时，数组每个元素是一个容量为 1 的链表。如索引 0 和 1 上的元素。
  2. 产生较小哈希抵触时，数组每个元素是一个蕴含多个元素的链表。如索引 2 上的元素。
  3. 当抵触数量超过 8 时，数组每个元素是一棵红黑树。如索引 6 上的元素。

下图为示意图，相干构造没有严格遵循标准。

类签名

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

如下图

]

实现 Cloneable 和 Serializable 接口，领有克隆和序列化的能力。

HashMap 继承抽象类 AbstractMap 的同时又实现 Map 接口的起因同样见上一篇 LinkedList。

常量

// 序列化版本号
private static final long serialVersionUID = 362498820763181265L;

// 默认初始化容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

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

// 默认负载因子，值为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;


// 以下三个常量应联合看
// 链表转为树的阈值
static final int TREEIFY_THRESHOLD = 8;

// 树转为链表的阈值，小于 6 时树转链表
static final int UNTREEIFY_THRESHOLD = 6;

// 链表转树时的汇合最小容量。只有总容量大于 64，且发生冲突的链表大于 8 才转换为树。static final int MIN_TREEIFY_CAPACITY = 64;

上述变量的关键在于链表转树和树转链表的机会，综合看：

  • 当数组的容量小于 64 是，此时不论抵触数量多少，都不树化，而是抉择扩容。

  • 当数组的容量大于等于 64 时，

    • 抵触数量大于 8，则进行树化。
    • 当红黑树中元素数量小于 6 时，将树转为链表。

变量

// 存储节点的数组，始终为 2 的幂
transient Node<K,V>[] table;

// 批量存入时应用，详见对应构造函数
transient Set<Map.Entry<K,V>> entrySet;

// 理论寄存键值对的个数
transient int size;

// 批改 map 的次数，便于疾速失败
transient int modCount;

// 扩容时的临界值，实质是 capacity * load factor
int threshold;

// 负载因子
final float loadFactor;

数组中存储的节点类型，能够看出，除了 K 和 Value 外，还蕴含了指向下一个节点的援用，正如一开始说的，节点理论是一个单向链表。

static class Node<K,V> implements Map.Entry<K,V> {
    
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
   //... 省略常见办法
}

构造方法

常见的无参结构和一个参数的结构很简略，间接传值，此处省略。看一下两个参数的构造方法。

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;
    // 将给定容量转换为不小于其本身的 2 的幂
    this.threshold = tableSizeFor(initialCapacity);
}

tableSizeFor 办法

上述办法中有一个十分奇妙的办法 tableSizeFor，它将给定的数值转换为不小于本身的最小的 2 的整数幂。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

比方 cap=10，转换为 16；cap=32，则后果还是 32。用了位运算，保障效率。

有一个问题，为啥非要把容量转换为 2 的幂？之前讲到的 ArrayList 为啥就不须要呢？其实关键在于 hash，更精确的说是转换为 2 的幂，肯定水平上减小了哈希抵触。

对于这些运算，画个草图很好了解，关键在于可能想到这个办法很牛啊。解释的话配图太多，这里篇幅限度，将内容放在另一篇文章，HashMap 之 tableSizeFor 办法图解。

增加元素

在下面构造方法中，咱们没有看到初始化数组也就是 Node<K,V>[] table 的状况，这一步骤放在了增加元素 put 时进行。

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

能够看出 put 调用的是 putVal 办法。

putVal 办法

在此之前回顾一下 HashMap 的形成，数组 + 链表 + 红黑树。数组对应地位为空，存入数组，不为空，存入链表，链表超载，转换为红黑树。

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 计算 hash 值得出数组中的地位 i，地位 i 上为空，间接增加。if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 数组对应地位不为空
    else {
        Node<K,V> e; 
        K k;
        // 对应节点 key 上的 key 存在，间接笼罩 value
        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) {p.next = newNode(hash, key, value, null);
                    // 链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((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;
        }
    }
    
    ++modCount;
    // 下次增加前需不需要扩容，若容量已满则提前扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize()办法比较复杂，最好是配合 IDE 工具，debug 一下，比拟容易弄清楚扩容的形式和机会，如果干讲的话反而容易混同。

获取元素

依据键获取对应的值，外部调用 getNode 办法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode 办法


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 && 
            ((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;
}

总结

HashMap 的内容太多，每个内容相干的知识点也很多，篇幅和集体能力限度，很难讲清所有内容，比方最根底的获取 hash 值的办法，其实也很考究的。有机会再针对具体的细节缓缓具体写吧。

退出移动版