Posted science21 minutes read (About 3090 words)0 visits

Map

本篇文章记录学习$java$​集合中$Map$接口的内容。

$Map$接口

  • $Map$与$Collection$并列存在，存储具有映射关系的数据：key-value;
  • $Map$中的$key$用$set$​来存放，不允许包含同样的值。同一个$Map$对象实现的类，必须重写$equals()$和$hashCode()$方法。
  • $Map$中常使用$String$作为键。
  • 常用实现类有$HashMap、LinkedHashMap、HashTable、Properties$，子接口$SortedMap$，其实现类$TreeMap$。

$HashMap$

源码中的重要常量

1
2
3
4
5
6
7
8
9
10
11
12
//默认初始化容量为16，必须是2的n次幂
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;
//链表转化成红黑树时数组的最小长度，这是为了避免数组扩容和树化的冲突
static final int MIN_TREEIFY_CAPACITY = 64;

$jdk7$

HashMap的内部存储是数组加链表的结合。当实例化一个HashMap对象时，会创建一个长度为Capacity的Entry数组，在这个数组中存放元素的位置称之为桶($bucket$​)，每个$bucket$​有自己的索引，可以根据索引找到其在数组中的位置。

关于put

首先调用key所在类的hashCode()和hash方法计算key的哈希值，$jdk7$为了防止因$hash$碰撞引发的问题，在计算$hash$过程中引入随机种子，以增强$hash$的随机性，使得键值对均匀分布在桶数组中。

$hash$方法

1
2
3
4
5
6
7
8
9
10
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // 通过多次位运算，提高算法散列性
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

然后根据得到的$h$值和$table$的长度计算出在$table$​中的下标i=h&(length-1).

如果该位置上为空，则$key-value$​添加成功。

若不为空，意味着此位置存在一个或多个数据(以链表形式存在)，需要比较$key$和已经存在的数据的哈希值。

  • 如果$key$的哈希值与已经存在的数据的哈希值都不相同，那么$key-value$​添加成功，和原来的数据以链表的方式存储，且使用的是头插法，可能是出于后来的数据被访问到的可能性更大的出发点。

  • 如果$key$的哈希值和已经存在的某一个数据$key1$的哈希值相同，继续调用$key$所在类的$equals()$方法比较是否相等。若不相等，则添加成功。如果相等，则用新的$value$更新原来的$value$​。

$hashMap$​​的扩容

当数组中元素数量达到扩容阈值$threshold$时，需要对原数组进行扩容，这便是$resize()$。数组的大小会扩展为$16*2=32$，即扩大一倍，并且需要重新计算每个元素在数组中的位置，这是一个很消耗时间的操作。

$resize()$方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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];
    //将原table中的元素转移到新table中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    //重新计算扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

$transfer()$方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//转移元素
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;
        }
    }
}

可以看到重新计算元素在数组中的位置仍需要调用$hash()$函数，这一点在$jdk1.8$​有所改进。

为什么不直接复制到新数组中？因为数组下标计算公式为hash(key)&(length-1),当数组长度变化，数组所在位置也应该变化。

头插法的弊端

使用头插，当数组扩容，链表上的元素顺序会倒置，在多线程环境下可能形成环。

在多线程的环境下有可能会使链表形成环状，在$getEntry()$​​​​方法查找元素时导致死循环。

$jdk8$

在$jdk8$中$hashMap$​的内部存储结构是数组+链表+红黑树的结合。$jdk8$中的数组是$Node$类型的，这与$jdk7$​不同。当初始化一个$hashMap$时，会初始化initialCapacity和loadFactor，在$put$​第一对映射关系时，会创建一个长度为initialCapacity的$Node$数组，这个长度是容量Capacity,在数组中存放元素的位置称之为桶(bucket),每个bucket有自己的索引，可根据索引查找到bucket中的元素。

为什么初始化数组长度为$16$​​

当$put$一个新数据时会计算位于$table$​​数组中的下标index = hash(key)&(length-1)，此处求下标使用按位与操作，如果$length-1$中某一位为$0$，那么该位按位与&必然为$0$，导致数组上有些位置永远访问不到，造成空间的浪费，也增加了$hash$​冲突的可能性。而如果是$2$的$n$次幂形式，减一后低位全为$1$​，保证计算后的$index$既可以是奇数也可以是偶数，且只要传进来的$key$足够分散均匀，那么$index$就会减少重复，这样就减少了$hash$​碰撞。

为什么选$16$这个数？因为分配的太小很容易导致$Map$​扩容影响性能，初始化分配太大又会浪费资源。

加载因子$0.75$​​

是时间和空间的权衡。如果小于$0.75$如$0.5$，那么数组达到一半就会扩容，空间利用率大大降低。如果大于$0.75$如$0.8$，则会增大$hash$​​冲突的概率，影响查询效率。在源码注释中有更深层次解释，大概意思是当加载因子是$0.75$的情况下，桶中$Node$结点的分布服从参数为$0.5$的泊松分布，当一个桶中出现$8$个元素的概率，已经小于千万分之一了。

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
/** Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million
 */
$put()$​​方法
1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

当$table$为空时调用$resize()$扩容。根据当前$key$的哈希值找到在数组中的下标，并判断当前位置是否存在元素，若没有，则把$key、value$包装成$Node$节点，直接添加到此位置。若已有元素，分三种情况。

  • 当前位置元素的$hash$值等于传过来的$hash$值，且它们的$key$​也相等，就覆盖。
  • 如果当前已经是红黑树结果，就加入到红黑树中。
  • 已存在元素，且是普通链表结构，则采用尾插法，把新节点加入到链表尾部。在插入过程中，若链表长度达到$8$，则转化为红黑树。
$hashMap$​​的扩容和$hash$​​方法

当数组元素个数超过initialCapacity*loadFactor时，就会进行数组扩容，将数组容量扩大一倍。

$hash$方法

1
2
3
4
5
static final int hash(Object key) {
    int h;
    // >>>无符号右移，只保留高16位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

将$hashCode()$的值进行高$16$位值和低$16$值的异或运算，尽量保留高$16$位的特征，降低哈希碰撞的概率。如果不进行高低位异或运算，直接用低$16$​位和n-1相与求数组下标，那么高位不同，低位相似度较高的两个$hashCode$值得到的数组下标可能相同，高位的特征被丢失了，这样哈希碰撞的概率大大增加。而异或运算，使$0$和$1$的比例达到$1:1$的平衡状态，使结果的随机性更大。

在$resize()$​​扩大数组长度为两倍后，重新计算原数组的位置时，如果原来的$hash$值在高$1$位为$0$，那么在新数组的位置不变，如果为$1$​，则在新数组中的位置为原来的位置加上原来数组的长度。

这样在扩充时不需要像$jdk1.7$那样重新计算$hash$,只需要看看原来的$hash$新增的那个$bit$是$1$还是$0$即可，省去了重新计算$hash$的时间，这是优化的地方。

且$jdk1.7$中$rehash$时，旧链表迁移到新链表时，如果在新表的数组索引位置相同，则链表元素会倒置，可能形成环，而$jdk1.8$中使用尾插法不会使元素倒置倒置，在$resize()$​​中有所体现。

$hashMap$​​的树化

在$put$数据到$hashMap$中时，如果是放到同一个位置上链表里，当链表长度达到$8$​​，会进行树化。会什么是$8$，在$jdk1.8$的源码注释中有深层次的解释，涉及泊松分布等概率知识，和上文加载因子$0.75$一致。

1
2
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

但是，当数组长度小于$64$，会先进行扩容。如果数组长度达到了64，就转变为红黑树结构，结点类型由$Node$变成$TreeNode$类型。当元素被移除时，下次$resize()$方法判断树的结点个数低于$6$个，会将红黑树再转变为链表。

带参构造器

当希望指定初始数组的大小时，调用了带有数组大小参数的构造器，但并不会真正创建那个长度的数组。由上文所讲，数组长度必须为$2$的$n$次幂形式。实际上会使用到$tableSizeFor()$函数，返回大于当前传入值最小的一个$2$的$n$次幂的值。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns a power of two size for the given target capacity.
 */
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;
}
$hashMap$​​是线程安全的吗？

不是，即使在扩容时不会引起死循环，但$put()$和$get()$方法都没有加同步锁，在多线程的情况下，无法保证上一秒$put$的值，下一秒$get$的仍是原值。

$Node$节点里的$hashCode$方法。

1
2
3
public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

$LinkedHashMap$

  • 是$hashMap$的子类，在$hashMap$的存储结构基础上，使用了一对双向链表来记录添加元素的顺序。
  • 和$LinkedHashSet$类似，可以维护$map$的迭代顺序与插入顺序一致。

内部类$Entry$

1
2
3
4
5
6
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

$TreeMap$

  • 存储$key-value$对时，会根据$key$进行排序。
  • 使用自然排序，所有的$key$必须是同一个类的对象，并且实现$Comparable$接口
  • 使用定制排序，创建$TreeMap$时需要传入一个$Comparator$对象，负责对$key$排序。
  • 判断两个$key$相等的标准：通过$compareTo()$方法或者$compare()$方法返回$0$。

$HashTable$

  • 是一个古老的$Map$实现类，实现原理和$hashMap$相同，但是方法直接加上$synchronized$，是线程安全的。
  • $hashTable$不允许将$null$作为$key$或者$value$，而$hashMap$允许。
  • 效率比$hashMap$​低，一般不使用。在多线程环境下会使用$ConcurrentHashMap$。

Map

https://twilight218.github.io/2021/11/24/Map/

Author

叶润繁

Posted on

2021-11-24

Licensed under

#

Categories

Tags

Git1
JDBC1
JavaWeb4
Linux1
MySQL5
Redis1
Spring1
acm5
experience1
java基础4
java集合3
位运算1
图论2
搜索1
树状数组1
线段树1
计算机网络5
设计模式1
题解2
×