Java Map 和 Set（一）：剖析 HashMap

1. `Map` 接口的概念是

Map 有键和值的概念
- Map 表示的是映射关系。一个键 key 映射到一个值 value，Map 根据键存储和访问值
- 键不能重复，即一个键只会存储一份，给同一个键重复设值会覆盖原来的值
- 使用 Map 可以方便地处理需要根据键访问对象的场景
数组、ArrayList、LinkedList 可以视为一种特殊的 Map ：键为索引，值为对象

2. `Map` 接口的定义是

Java 7 中 Map 接口的定义代码如下

public interface Map<K, V> { //K 和 V 是类型参数，分别表示键（Key）和值（Value）的类型
    V put(K key, V value); //保存键值对，如果原来有 key，覆盖，返回原来的值
    V get(Object key); //根据键获取值，没找到，返回 null
    V remove(Object key); //根据键删除键值对，返回 key 原来的值，如果不存在，返回 null

    int size(); //查看 Map 中键值对的个数
    boolean isEmpty(); //是否为空

    boolean containKey(Object key); //查看是否包含某个键
    boolean containValue(Object value); //查看是否包含某个值
    
    void putAll(Map<? extends K, ? extends V> m); //保存 m 中所有的键值对到当前 Map
    void clear(); //清空 Map 中所有键值对

    Set<K> keySet(); //获取 Map 中键的集合
    Collection<V> values(); //获取 Map 中所有的值集合
    Set<Map.Entry<K, V>> entrySet(); //获取 Map 中所有的键值对

    interface Entry<K, V> { //嵌套接口，表示一条键值对
        K getKey(); //获取键值对的键
        V getValue(); //获取键值对的值
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }

    boolean equals(Object o);
    int hashCode();
}

Java 8 增加了一些默认方法，如：getOrDefault()、forEach()、replaceAll()、putIfAbsent()、replace()、computeIfAbsent()、merge() 等
Java 9 增加了多个重载的 of() 方法，可以方便地根据一个或多个键值对构建不变的 Map

3. `Set` 接口的概念

Set 接口表示的是数学中的集合概念，即没有重复元素的集合
- Java 7 中 Set 接口的定义为：public interface Set<E> extends Collection<E> {}
- Set 扩展了 Collection，但没有定义任何新的方法。不过，它要求所有实现者都必须确保 Set 的语义约束，即不能有重复元素
Java 9 增加了多个重载的 of() 方法，可以根据一个或多个元素生成不变的 Set

4. `Map` 中的键除了不能重复之外还有什么特点

Map 中的键没有重复的，所以 keySet() 返回了一个 Set
keySet()、values()、entrySet() 有一个共同的特点：它们返回的都是视图，不是复制的值，所以基于视图返回值的修改会直接修改 Map 自身。比如，map.keySet().clear() 会删除所有键值对

5. 随机产生 1000 个 0 ~ 3 的数，统计每个数的次数

//使用 HashMap 统计随机数
public static class CountRandom {
    Random rnd  = new Random();
    Map<Integer, Integer> countMap = new HashMap<> ();

    for(int i = 0; i < 1000; i++) {
        int num = rnd.nextInt(4);
        Integer count = countMap.get(num);
        if(count == null) {
            countMap.put(num, 1);
        } else {
            countMap.put(num, count + 1);
        }
    }

    for(Map.Entry<Integer, Integr> kv : countMap.entrySet()) {
        System.out.println(kv.getKey() + ", " + kv.getValue());
    }
}

6. `HashMap` 存储结构示意图

7. `HashMap` 实现原理之内部组成

HashMap 内部有如下几个主要的实例变量

transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE; //哈希表或哈希桶
transient int size; //表示实际键值对的个数
int threshold; //阈值
final float loadFactor; //负载因子

size 表示实际的键值对个数
table 是一个 Entry 类型的数组，称为哈希表或哈希桶
- 其中的每个元素指向一个单向链表，链表中的每个节点表示一个键值对
- table 的初始值是一个空表，具体定义为：static final Entry<?, ?>[] EMPTY_TABLE = {}
- 当添加键值对后，table 就不是空表了，它会随着键值对的添加进行扩展，扩展的策略类似于 ArrayList
- 添加第一个元素时，默认分配的大小为 16（ArrayList 默认是 10），设计成 16 的好处主要是可以使用按位与代替取模来提升 hash 的效率
- 不过，并不是 size 大于 16 时再进行扩展，下次什么时候扩展与 threshold 有关
threshold 表示阈值
- 当键值对个数 size 大于等于 threshold 时考虑进行扩展
- 一般而言，threshold 等于 table.length 乘以 loadFactor
loadFactor 是负载因子
- 表示整体上 table 被占用的程度
- 是一个浮点数，默认为 0.75，可以通过构造方法进行修改
- 默认值是 0.75 是因为：通过源码里的 javadoc 注释可以看到，元素在哈希表中分布的桶频率服从参数为 0.5 的泊松分布（Poisson Distribution）

Entry 是一个内部类，它的实例变量和构造方法如下

static class Entry<K, V> implements Map.Entry<K, V> {
    final K key; //键
    V value; //值
    Entry<K, V> next; //指向下一个 Entry 节点
    int hash; //key 的 hash 值，直接存储 hash 值是为了在比较的时候加快计算

    Entry(int h, K k, V v, Entry<K, V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

参考：HashMap 中傻傻分不清楚的那些概念

8. `HashMap` 实现原理之默认构造方法

默认构造方法代码为
1
2
3
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
- DEFAULT_INITIAL_CAPACITY 为 16：设计成 16 的好处主要是可以使用按位与代替取模来提升 hash 的效率
- DEFAULT_LOAD_FACTOR 为 0.75：通过源码里的 javadoc 注释可以看到，元素在哈希表中分布的桶频率服从参数为 0.5 的泊松分布
- 默认构造方法调用的构造方法主要代码为
  1
  2
  3
  4
  public HashMap(int initialCapacity, float loadFactor) {
  this.loadFactor = loadFactor;
  threshold = initialCapacity;
  }
主要就是设置 loadFactor 和 threshold 的值

9. `HashMap` 实现原理之保存键值对方法 `put(K key, V value)`

put(K key, V value) 方法代码

public V put(K key, V value) {
    if(table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    if(key == null) {
        return putForNullKey(value);
    }

    int hash = hash(key);
    int i = indexFor(hash, table, 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;
}

如果是第一次保存，首先调用 inflateTable() 方法给 table 分配实际的空间

inflateTable() 方法的主要代码为

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];
}

默认情况下，capacity 的值为 16（设计成 16 的好处主要是可以使用按位与代替取模来提升 hash 的效率）， threshold 会变为 12，table 会分配一个长度为 16 的 Entry 数组
1. 接下来，检查 key 是否为 null，如果是，调用 putForNullKey() 单独处理，我们暂时忽略这种情况。
2. 在 key 不为 null 的情况下，下一步调用 hash() 方法计算 key 的 hash 值
3. hash() 方法的代码为
  1
  2
  3
  4
  5
  6
  final int hash(Object k) {
  int h = 0;
  h ^= k.hashCode();
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>>4);
  }
基于 key 自身的 hashCode() 方法的返回值又进行了一些位运算，目的是为了随机和均匀
1. 有了 hash 值之后，调用 indexFor() 方法，计算该将这个键值对放到 table 的哪个位置
2. indexFor() 方法代码为
  1
  2
  3
  static int indexFor(int h, int length) {
  return h & (length - 1);
  }
HashMap 中，length 为 2 的幂次方，h & (leng-1) 等同于求模运算 h % length
1. 找到了保存位置 i，table[i] 指向一个单向链表
2. 接下来，就是在这个链表中逐个查找是否已经有这个键了，遍历代码为：for(Entry<K, V> e = table[i]; e ! = null; e = e.next)
3. 而比较的时候，是先比较 hash 值，hash 相同的时候，再使用 equals() 方法进行比较，代码为：if(e.hash == hash && ((k = e.key) == key || key.equals(k)))

为什么要先比较 hash 呢？因为 hash 是整数，比较的性能一般要比 equals() 高很多，hash 不同，就没有必要调用 equals() 方法了，这样整体上可以提高性能

如果能找到，直接修改 Entry 中的 value 即可
modCount++ 的含义与 ArrayList 和 LinkedList 中的一样，为纪录修改次数，方便在迭代中检测结构性变化

如果没找到，则调用 addEntry() 方法在给定的位置添加一条，代码为

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

如果空间是够的，不需要 resize()，则调用 createEntry() 方法添加。createEntry() 方法代码为

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 对象，插入单向链表的头部，并增加 size

如果空间不够，即 size 已经要超过阈值 threshold 了，并且对应的 table 位置已经插入过对象了，具体检查代码为：if((size >= threshold) && (null != table[bucketIndex]))

则调用 resize() 方法对 table 进行扩展，扩展策略是乘 2，resize() 方法的主要代码为

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

分配一个容量为原来两倍的 Entry 数组，调用 transfer() 方法将原来的键值对移植过来，然后更新内部的 table 变量，以及 threshold 的值

transfer() 方法代码为

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

参数 rehash 一般为 false。这段代码遍历原来的每个键值对，计算新位置，并保存到新位置
HashMap 支持 key 为 null，key 为 null 的时候，放在 table[0]

简单总结下，保存键值对的基本步骤为
1. 计算键的哈希值
2. 根据哈希值得到保存位置
3. 插到对应位置的链表头部或更新已有值
4. 根据需要扩展 table 大小
参考：彻底理解 HashMap 的元素插入原理
查找方法 get(Object key)、删除方法 remove(Object key) 逻辑相对简单，就不分析了

10. `HashMap` 实现原理总结

基本原理：HashMap 内部有一个哈希表（哈希桶），即 Entry 类型的数组 table 。每个元素 table[i] 指向一个单向链表，根据键存取值，首先用键算出 hash 值，然后取模得到数组中的索引位置 bucketIndex，然后操作 table[bucketIndex] 指向的单向链表
需要注意的是，存取的时候依据键的 hash 值，只在对应的链表中操作，不会访问别的链表。在对应链表操作时也是先比较 hash 值，如果相同再用 equals() 方法比较。这就要求，相同的对象其 hashCode() 返回值必须相同，如果键是自定义的类，就特别需要注意这一点。这也是 hashCode() 和 equals() 方法的一个关键约束
需要说明的是，Java 8 对 HashMap 的实现做了优化
1. 在哈希冲突比较严重的情况下，即大量元素映射到同一个链表的情况下（具体是至少 8 个元素，且总的键值对个数至少是 64）
2. Java 8 会将该链表转换为一个平衡的排序二叉树（红黑树），以提高查询的效率
3. 红黑树
  - 维基百科：红黑树
  - 漫画：什么是红黑树

11. `HashMap` 的特点总结

原理：HashMap 实现了 Map 接口，可以方便地按照键存取值
- HashMap 内部使用数组链表（哈希表/哈希桶）和哈希的方式进行实现
- 根据键保存和获取值的效率都很高，为 O(1)，每个单向链表往往只有一个或少数几个节点，根据 hash 值就可以直接快速定位
- HashMap 中的键值对没有顺序，因为 hash 值是相对随机和均匀的
场景：如果经常需要根据键存取值，而且不要求顺序，那么 HashMap 就是理想的选择
- 如果要保持添加的顺序，可以使用 HashMap 的一个子类 LinkedHashMap
- Map 还有一个重要的实现类 TreeMap，它可以排序
线程安全性：HashMap 是线程不安全的
- Java 中还有一个类 Hashtable，它是 Java 最早实现的容器类之一。实现了 Map 接口，实现原理与 HashMap 类似，但没有特别的优化，它内部通过 synchronized 实现了线程安全
- 在 HashMap 中，键和值都可以为 null，而在 Hashtable 中不可以
- 在不需要并发安全的场景中，推荐使用 HashMap；在高并发的场景中，推荐使用 ConcurrentHashMap

1. Map 接口的概念是

2. Map 接口的定义是

3. Set 接口的概念

4. Map 中的键除了不能重复之外还有什么特点

5. 随机产生 1000 个 0 ~ 3 的数，统计每个数的次数

6. HashMap 存储结构示意图

7. HashMap 实现原理之内部组成

8. HashMap 实现原理之默认构造方法

9. HashMap 实现原理之保存键值对方法 put(K key, V value)

10. HashMap 实现原理总结

11. HashMap 的特点总结