Photo by Pixabay from Pexels

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.html

每个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

1
2
3

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

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

1 2	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对比查看这里

`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的余数：

1	index = hash % length;

又有在Length为2^n^时：

hash % 2^n^ = hash & ( 2^n^ - 1)

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

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

1	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^n^
右移	`>>`	相当于除以2^n^
无符号右移	`>>>`