Java 笔记之 HashMap 保存数据

JI,XIAOYONG...大约 6 分钟

Photo by **Pixabay open in new window**from Pexelsopen in new window

HashMap使用由Node<K,V>（继承自Map.Entry<K,V>）组成的数组table保存数据。

在table中保存数据时根据key的hashCode计算到一个随机保存位置（但都在table数组的大小范围内），当存储的数据总量超过加载系数loadFactor规定的阈值时则对table进行扩容。

HashMap 有以下全局变量

transient Node<K,V>[] table;//实际保存键值对的数组
transient Set<Map.Entry<K,V>> entrySet;//Holds cached entrySet().用来遍历 HashMap
transient int size;//本 HashMap 实际保存的键值对个数
transient int modCount;//HashMap 修改的次数，每次修改 HashMap 都会叠加，
//用来在遍历的过程中检查 HashMap 是否被改动过来，如果有则抛出异常 ConcurrentModificationException
int threshold;//是否扩容的阈值
final float loadFactor;//加载系数，默认 0.75f

loadFactor：默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下：
如果内存空间很多而又对时间效率要求很高，可以降低负载因子 Load factor 的值；
相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于 1。
https://tech.meituan.com/2016/06/24/java-hashmap.htmlopen in new window

每个Node包含了以下信息：

Node<K,V> implements Map.Entry<K,V>{
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
  }

在执行hashMap.put("k", "v");时，会先计算key的hash值

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  //这里原始 hash 值 (32 位) 的高位和地位进行按位异或（不同为，相同为 0），
  //增加了随机性，避免因为 hashCode 计算得到的 hash 值（低位相同概率高）
  //计算索引时（见下文↓）一直取低位值而可能导致的索引一直的重复问题。
    }

`V put(K key, V value)`

使用HashMap保存数据时：

使用hash(Object key)计算key的hash值

通过hash值计算value应该保存的位置i

i = (table.length - 1) & hash
//由于 table.length 限定为 2 的 n 次方，所以上面的等式相当于给 table.length 取余数
//即 i 永远<=table.length

在此时会判断是否需要扩容 (只有table为空，或者当前存储的数据总数size大于阈值threshold时才会扩容resize())

threshold = capacity * loadFactor
阈值 = 容量 * 负载系数（默认为 0.75）

接下来会插入数据
- 指定位置为空（没有hash 冲突），或已有key相同的值：则直接插入value
- 已经存在值并且数量大于 8：则将链表转化为红黑树（JDK1.8），否则以链表形式保存数据
- 在移除数据时，如果红黑树数量小于 6：则将红黑树转化为链表

在 JDK1.7 中，数据以数组或链表形式保存，JDK1.8 中则新增了红黑树。
发生 hash 冲突时，JDK1.7 采用采用头插法，可能会产生逆序和环形链表；JDK1.8 采用尾插法，直接插入链表或红黑树尾部。
具体 JDK1.7 与 1.8 对比查看这里open in new window

`V get(Object key)`

使用HashMap获取数据时：

计算 key 的hash值
查找对应位置的node
- null：返回null
- node不为空且key一致：返回该node
- node不为空且key不一致：
  如果是链表：遍历链表查找是否存在与key一致的node
  如果是树：遍历树查找是否存在与key一致的node

`V remove(Object key)`

使用HashMap移除数据时：

其大体过程与get(Object key)类似，遍历找到对应的node并删除。

计算索引

一个key对应的索引index是由这个key的hash()值对HashMap的数组长度length的余数：

index = hash % length;

又有**在Length为 2ⁿ**时：

hash % 2ⁿ = hash & ( 2ⁿ - 1)

hash % 2ⁿ = hash - (hash / 2ⁿ) * 2ⁿ
= hash - (hash>>n) * 2ⁿ
= hash & ( 2ⁿ - 1)

而HashMap的长度Length又只能是 2ⁿ，所以：

index = (length - 1) & hash;

保存值

当table为空或者长度超过加载因子DEFAULT_LOAD_FACTOR规定的容量 (默认容量为 16，加载因子为 0.75) 时会自动扩容。
当table[index]为空时，直接新建Node并保存到table[index]中。
当table[index]不为空时：
- 如果是同一个key则覆盖旧的值
- 如果是不同的key则先尝试以链表保存数据
- 如果是不同的key，并且链表长度超过MIN_TREEIFY_CAPACITY规定的长度（默认 64），则将链表转化为红黑树 (JDK1.8 新增)

序列化

在第一节我们可以看到，HashMap的很多变量都被标记为transient，这表示在Serializable序列化时不主动去序列化这些值，那这样岂不是没法反序列化这些数据了？

其实在后面我们可以看到，HashMap在writeObject()方法中主动保存了部分数据（原因是默认的Serializable由于不同 JVM 实现对同一对象如String的HashCode不一定一致，会导致严重的问题——HashMap基于hash值保存数据）：

private void writeObject(java.io.ObjectOutputStream s)
    throws IOException {
    int buckets = capacity();//容量
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    s.writeInt(buckets);
    s.writeInt(size);//保存 size
    internalWriteEntries(s);//保存 table 数据
}

/**
* table 不为空则返回 table 长度
* 否则 threshold 不为空则返回 threshold
* 否则返回默认的 DEFAULT_INITIAL_CAPACITY
*/
final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
}

并在readObject()恢复了这些值。

位运算

位运算	符号	计算
按位与	&	相同为 1，不同为 0
按位或	\|	有 1 则 1
按位异或	^	相同为 0，不同位 1
按位取反	~
左移	<<	相当于乘以 2ⁿ
右移	`>>`	相当于除以 2ⁿ
无符号右移	`>>>`