JDK-HashMap解析

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

JDK-HashMap解析

jdk 类介绍

HashMap 是一个继承Map接口并且是使用哈希表的实现。提供了所有的map操作，并且允许null建和null值。除了非同步方式和允许null键值，它大致上可以等同于Hashtable。影响HashMap表现的有两个原因：初始容量和加载因子。

capacity：容量指的是hash表中的总容量。初始容量在第一次创建hashmap的时候就已经创建好了。
load factor: 加载因子，是测量capacity在hash表达到了多满的时候可以自动增长。

当键值对达到了加载因子的量并且超过了当前的capacity，hash表就会重新进行hash（意思是内部数据结构将重建），目的是为了将hash表能够达到差不多两倍的容量。

通常的规则是，默认的加载因子为0.75，它可以在时间和空间上做一个非常好的平衡。如果设置自定义capacity，map里面可能存在多少键值队就需要作为一个考虑因素，以达到最小的rehash操作。如果初始capacity在设置capacity之后还能存下更多的键值对，那么就不会出现rehash操作。

如果事先能大致确认map的容量是多少，那么给map定一个初始化大小是非常可行的，会比让它自己增长更有效率。在hash表中如果出现太多的相同的key拥有相同的hashCode()会降低效率，如果需要改善这种关系，如果键是可以比较的，类可以使用key的比较顺序来进行改善。

HashMap的实现是非线程安全的。在多线程的环境下，必须在外部上进行同步控制。如果外部没有控制，那么需要将map进行包装，也就是使用Collections.synchronizedMap(map)方法，最好是在一开始创建map的时候就进行包装。
map的iterators方法是fail-fast的。在iterator创建之后，如果map的结构被修改了，除了iterator的remove方法，iterator会抛出ConcurrentModificationException异常。所以在多线程环境下进行修改，iterator会快速的返回失败。不过也得注意在非同步环境下，迭代器的fail-fast不能得到保证。迭代器抛出这个异常一个非常好的功能，但是不应该依赖它来写程序，如果出现异常那么就应该说明程序有bug。

jdk的源码里面，介绍的非常详细。真的很详细。

分块介绍

之前说过map是非线程安全的，这节就单纯的聊一下非线程安全下的map。

一个类我们从哪里来看它了？其实我也不知道，那就干脆从我们使用一个对象开始。我们是先创建对象，给对象设置值，然后使用对象的方法。

创建map

通常在创建map的时候我们会使用对象的构造方法，如果有对象有属性，可能还会有带参数的构造方法。所以在创建map之前我们先了解下map有哪些属性？

通过idea我截取了一个图，在jdk8中是

2018-02-06-14-54-11

在jdk7中：
2018-02-06-15-00-27

可以看到，map对象里面有一些属性，根据这些属性的定义我们可以猜到大致的意思。

DEFAULT_INITIAL_CAPCITY = 1<<4：默认容量大小，1左移4位，16。记住默认的大小必须是2的幂。
MAXIMUM_CAPACITY = 1<<30：最大的容量
DEFAULT_LOAD_FACTOR:加载因子，默认0.75
Entry<?,?>[] EMPTY_TABLE： 空表
Entry<K,V>[] table：长度为2的幂方，并且必要的时候可以改变大小，默认为空表。注意到这个字段是transient
size: 实际map中键值对的数量
threshold：下一次表重构的极限值
modCount：hash表结构修改一次就增加一次，包括增加减少键值对，内部数据结构重构。主要用来在迭代器中fail-fast

大致的参数就这些了。

然后我们看到构造方法，如下图：

2018-02-06-15-22-02

1
2
3
4
5
6
7
8
9
10
11
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

如果你看构造函数带有Map的构造方法：

1
2
3
4
5
6
7
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

你会发现，同样的它也在里面调用带两个参数的构造方法，所以我认为，这个带两个参数的构造方法可以算作是基本方法，其实想想这算不算代码复用？如果我们可以在平常的开发中开发出了基础方法，那么是否也可以像这样进行包装使用？

这三个构造方法其实只是包装了一层而已，当然map构造方法进行了一些其它的操作，所以我们需要再看下里面的基础构造方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    threshold = initialCapacity;
    init();
}

这里可以看到，我们的map里面，在使用的时候至少需要进行两个属性设置：initialCapacity初始容量和loadFactor加载因子。

可以看到代码的严谨性：在初始化的时候进行了参数可用性校验，平常我写方法的时候，偶尔会忘记这个，不过最后我会根据sonar扫描一次代码提交。哈哈sonar这点还是可以做到的。

在这个构造方法里面init()是一个空方法。

在map的构造方法里面后面还有两个操作，一个是inflateTable，一个是putAllForCreate。其实可以想到，用map的构造方法是有数据的，不同于其它三个，其它三个都是无数据的。所以我们只需要构建一个map出来就好了。而map的构造方法拥有数据所以在构建map之后我们需要将数据填充到新的map中。一个是扩容的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

/**
 * Inflates the table.
 */
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

之后的设置初始值就不详细说了。

常用方法

常用方法put(key,value)

这个方法是从Map接口中继承过来的，我们大致猜测一下，map如果插入了一个键值对，插入之前我们是不是需要先判断一下容量？是不是还需要有个地方存入这个值？在哪里存这个键值对？：

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
public V put(K key, V value) {
    //对表容量进行判断
     if (table == EMPTY_TABLE) {
         inflateTable(threshold);
     }
     //key的空值处理
     if (key == null)
         return putForNullKey(value);
     //对key进行hash计算
     int hash = hash(key);
     //hash表中的位置i
     int i = indexFor(hash, table.length);
     //在i的位置找到值，
     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         
         Object k;
         //条件1：判断当前key的hash与i位置的hash是否一致
         //条件2：判断key是否是i位置(entry)的key相等的
         //条件3：判断key是否和i位置(entry)的key内容相等
         //条件1&&（条件2||条件3）
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
             //说明找到了hash的key，将新值替换旧值
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
     }

     //map数据结构修改，+1
     modCount++;
     //没有在i的位置找到值，说明这个是新的key，加入到entry
     addEntry(hash, key, value, i);
     return null;
 }

我们再代码中就可以看到之前的问题了，不过代码实现中还做了null值的处理。下面我们一个个来看：

扩容处理：inflateTable(threshold); 这个在上面构造map的时候讲过了。

空值处理：putForNullKey(value);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private V putForNullKey(V value) {
    //从table的0位置开始遍历
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //找到null的key，替换值
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

可以看到，这里的的操作是从0位置开始查找的。也就是从一开始遍历，这种情况下可以想到一个O(n)的时间复杂度。所以，如果是1.7，null键最好不要存在。

在代码中可以看到存键值对的地方是Entry，关于Entry我们现在只需要知道它是一个单链表的数据结构就好了，之后我们专门讲解一下Entry和hash。

讲完1.7。我们看看1.8中的put方法：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
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;
    //判断是否是空表
    if ((tab = table) == null || (n = tab.length) == 0)
        //空表，重构表
        n = (tab = resize()).length;
    //如果原始表中不存在数据，直接新建一个节点，p为表中key的数据节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //原始表中存在数据
        Node<K,V> e; K k;
        //找到了key节点hash的值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果该节点是一个TreeNode
        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) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //增加修改次数
    ++modCount;
    //size+1之后的大小大于极限值
    if (++size > threshold)
        resize();
    //空方法
    afterNodeInsertion(evict);
    return null;
}

jdk1.8中的put方法，实现好像有些优化。加入了TreeNode，之后这块我补上，整体的流程是和1.7一致的。

常用方法get(key)

该方法在1.7中的实现是：

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

public V get(Object key) {
    //判断null，如果是null遍历循环找出值
    if (key == null)
        return getForNullKey();
    //找到存了key的entry
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    //如果是空表，直接返回null
    if (size == 0) {
        return null;
    }

    // 计算hash值
    int hash = (key == null) ? 0 : hash(key);
    //循环遍历找到值，从hash值开始找
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

1.7中还是很好理解的，这里主要是hash值计算，之后我们重点讲解。

在1.8中，get方法：

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

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;
    //表不为空
    //表的内容长度不为0
    //在(n-1)&hash的位置不为null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个位置?为什么判断第一个位置，是和node的数据结构有关系么？是不是加入的时候都是加入第一个位置？
        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;
}

注意到8中总是计算判断第一个node，为什么？之后了解清楚了再来详细解析

常用方法containsKey(Object),containsValue(Object)

containsKey(Object)的源码中我们可以看到也是调用了getEntry方法：

1
2
3
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

containsValue(Object)的源码中我们可以看到，基本类似，也是循环链表，然后获取到值之后比较value：

1
2
3
4
5
6
7
8
9
10
11
public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

常用方法keySet(),values(),entrySet()

这几个方法是指代的键,值遍历，以及键值对遍历。

常用方法size()，内部方法resize()

这里就需要主要注意resize()方法是default的，也就是同一个包下面才可以调用。

size()方法就是为了获取到map里面真实的实例数量，返回的是size属性。

resize()方法在每次达到极限界值的时候会自动调用：

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
void resize(int newCapacity) {
    //获取原始表的容量值
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //原表容量值等于最大值，可以直接返回了。
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 新表
    Entry[] newTable = new Entry[newCapacity];
    //填充新表数据
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //替换旧表内容
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

Entry,hash,hashCode(),size,capacity,threshold

前面我们讲过一些常用的方法，put，get，size等，这些方法其实都是有一定关联的，put前是不是应该先判断容量是否够？不够该怎样，够该怎样。其实就是这样，就像流程图一样，只不过在具体的实现上面我们会有不同的方式。使用不同的数据结构来做优化。

这里我们需要讲一下Entry，hash，hashCode(),size,capacity,threshold他们代表的意义，以及作用。

如果说map是存储键值对，那么键是怎么存？值又是怎么存？两者怎么关联起来了？回过头我们思考这些问题，最好的方式就是看看put方法是怎么运作的：

jdk1.7:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public V put(K key, V value) {
   // 判断空表，然后扩容
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //判断nullkey
    if (key == null)
        return putForNullKey(value);

    // 重点。这里计算了key的hash
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
 /**
 获取hash 值，对于hash结果进行重写，主要是为了防止低质量的hash计算方法，hashmap使用2的幂方长度的hash表，在低位容易遇到同样的hashcode冲突 
 Null 为key的hash是0
 */
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

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

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

实际上它使用的是的是Entry[] table 数组，而Entry是一个链表的形式。 

1
2
3
4
5
6
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}

hashCode方法是一个本地方法，hash算法实在key的hashCode上计算的，这里有两篇文章，感觉很好，我就不敢多说了：
http://www.cnblogs.com/xiongpq/p/6175702.html，http://blog.csdn.net/fjse51/article/details/53811465；

size是指的map实际中存在了多少键值对，也就是实际的实例；

capacity是指这个map的总容量；

threshold是一个极限值，当达到了size达到了极限值的时候就会自动扩容(2的幂次方)，threshold的计算为capacity*load factor。

在jdk8中感觉变化太大了，下次要单独讲讲jdk8。另外还需要讲解一下在多线程下的map该怎么操作。

疑问待解决

1：在put的时候，如果是重复键，再第二次的时候就只是替换了，那么entry链表有什么用？为什么这么设计？

2：hash的计算方式？hashCode计算方式，什么是hashCode？那些位运算是怎么做的？

坚持原创技术分享，您的支持将鼓励我继续创作！