HashMap 解析

发表于 | 分类于 | 阅读次数

HashMap 概述

HaspMap 是 基于哈希表的Map接口实现，提供了所有的Map操作并且允许key和value为null。（HashMap大致等同于HashTable,除了HashMap不是同步的和允许为null）HashMap不保证Map中的排序顺序；尤其是不能保证排序在一段时间内保持不变。

HashMap的这个实现为基本操作提供了恒定的性能（get和put）,假设哈希函数在buckets之间正确地分散元素。对集合视图的迭代需要的时间与HashMap实例的“容量”（buckets的数量）加上其大小（键值映射的数量）成正比。因此，如果迭代性能很重要，不要将初始容量设置得太高（或者负载因子太低）。

buckets 其实就是 transient Node<K,V>[] table;这个。其中Node 保存的数据区 final int hash; 通过key计算出的hash值 final K key; key V value; value Node<K,V> next;

HashMap的有两个影响其性能的参数:初始容量(initialCapacity)和负载因数(loadFactor)。容量就是buckets的数量,初始容量就是哈希表创建时的容量。负载因子:当哈希表容量达到(负载因子*容量) 就会自动增加容量.如果哈希表中条目的数量超过了负载因子和当前容量的乘积,哈希表被rehash(即内部的数据结构将被重建)所以哈希表大约有两倍的容量。

通常来说，默认的负载因子(.75)在时间和空间成本之间提供了一个很好的折中。负载因子越高会减少空间开销，但会增加查找成本（反映在大部分HashMap类的操作中，包括get和put）在设定其初始容量时，应考虑Map中预期的条目数量及其装载因子，以尽量减少rehash的次数。如果初始容量大于最大容量除以负载因子，则不会rehash操作。

HashMap 实现

1
2
3
4

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

HashMap 构造方法

HashMap 有4个构造方法

  • HashMap(int initialCapacity, float loadFactor) 用指定的初始容量和负载因子构造一个空的HashMap
1
2
3
4
5
6
7
8
9
10

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);
}
  • HashMap(int initialCapacity) 用指定的初始容量创建一个空的HashMap
1
2
3

 public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
  • HashMap() 使用默认初始容量（16）和默认加载因子（0.75）创建一个空的HashMap。
1
2
3

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
  • HashMap(Map<? extends K, ? extends V> m) 使用与指定的Map相同的映射构造一个新的HashMap。
1
2
3
4

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

HashMap 的 get(key)和 put(K,V)

  • HashMap 的put(K,V) 方法
1
2
3

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

然后我们看看putVal方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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)//先判断键值对数组(Node<K,V>[] tab) table[i]是否为空或为null，否则执行resize()进行扩容。
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//根据键值key计算hash值得到插入的数组索引i，如果table[i]==null,直接新建节点添加
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))//判断table[i]的首个元素是否和key是否一样（即通过hashCode和equals()）,如果相同则覆盖value
            e = p;
        else if (p instanceof TreeNode)//判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对；
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        //遍历table[i]
            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，大于8的话把链表转换为红黑树，在红黑树中执行插入操作
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))//进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可
                    break;
                p = e;
                }
            }
        if (e != null) { // 覆盖value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容
        resize();
    afterNodeInsertion(evict);//这个方法在LinkedHashMap中实现
    return null;
}
  • HashMap的 get(Object K) 方法
1
2
3
4

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

然后我们继续看看getNode(hash(key), key))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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) {//判断key是否存在
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))//先判断hash 是否一样然后继续判断key 是不是一样，如果一样则返回 节点
            return first;
        if ((e = first.next) != null) {//继续查找下一个
            if (first instanceof TreeNode)////判断table[i] 是否为treeNode，如果是则从treeNode 中查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {//遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))// 先判断hash 是否一样然后继续判断key 是不是一样，如果一样则返回 节点
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

暂时分析到这，以后继续补充。