1.Map接口
Map 用于保存具有映射关系的数据：key-value（双列元素）
public interface Map<K,V> {}
- Map 中的 key 和 value 可以是任何引用类型的数据，最后会存储到 Map
Node 对象，实现了 Map$Entry 接口，所以也可以说一对 k-v 就是一个 Entry
- Map 中的 key 不允许重复，添加相同元素的 key 会将原来这个 key 对应的 value替换掉
- Map 中的 value 允许重复
- Map 中的 key 可以为 null，但只能有一个；value 也可以为 null，可以有多个
- key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
- 如果自定义对象作为 Map 的键，那么必须覆写 hashCode 和 equals。
Set<Map.Entry<K, V>> entrySet();//获取 Map 中存储的元素集合
Set<K> keySet(); // 获取Map中key的集合
Collection<V> values(); // 获取Map中value的集合
// Entry 接口定义了 getKey() 和 getValue() 方法
interface Entry<K,V> {
K getKey();
V getValue();
}
接口方法
| 方法声明 | 方法描述 |
|---|---|
| intsize(); | 返回 Map 中 k-v 的个数 |
| booleanisEmpty(); | 返回 Map 是否为空 |
| booleancontainsKey(Object key); | 返回 Map 中是否包含 key |
| booleancontainsValue (Object value); | 返回 Map 中是否包含 value |
| V get(Object key); | 返回 Map key 对应的 Value值 |
| Vput(K key, V value); | 向 Map 中添加 key-value 并返回 value |
| V remove(Object key); | 删除 Map 中 key 对应的键值对 |
| void clear(); | 从此 Map 中删除所有映射（可选操作） |
| Set keySet(); | 获取 Map 中 k 的集合 |
| Collection values(); | 获取 Map 中 v 的集合 |
| Set |
获取 Map k-v 键值对集合 |
遍历
Map map = new HashMap(); // put 元素略
//keySet() 获取 key 集合遍历
Set keySet = map.keySet();
// 增强 for
for (Object key : keySet) {
System.out.println(key + "-" + map.get(key))
}
// 迭代器
Iterator iterator = map.keySet().iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}
//values() 获取 value 集合遍历
Collection values = map.values();
// 增强 for
for (Object value : values) {
System.out.println(value);
}
// 迭代器
Iterator iterator = map.values().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
//entrySet() 获取 entry 集合遍历
Set entrySet = map.entrySet();
// 增强 for
for (Object entry : entrySet) {
// 将 entry 转成 Map$Entry 类型
Map.Entry ele = (Map.Entry) entry;
System.out.println(ele.getKey() + "-" + ele.getValue());
System.out.println(ele); // key=value
}
// 迭代器
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
System.out.println(entry.getKey() + "-" + entry.getValue());
System.out.println(entry); // key=value
}
哈希表
哈希表是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
哈希表为解决冲突可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
链地址法简单来说是数组加链表的结合。
建立一个哈希表需要解决两个主要问题：
- 构造一个合适的哈希函数,均匀性 H（key）的值均匀分布在哈希表中
- 冲突的处理（冲突是在哈希表中不同的关键字值对应到同一个存储位置的现象）
链式哈希表
链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”，我们将所有的元素通过散列的方式放到具体的不同的桶中。
插入元素时，首先将其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属于哪个“桶”，然后在相应的链表头插入元素。查找或删除元素时，用同们的方式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。因为每个“桶”都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如果表变得太大，它的性能将会降低。
应用场景
缓存技术（比如redis、memcached）的核心是在内存中维护一张巨大的哈希表，还有HashMap、ConcurrentHashMap等应用。
2.HashMap
- key和value都允许null存在
- HashMap底层数据结构：数组+(链表、红黑树)，jdk8之前是用数组+链表方式实现，jdk8引进了红黑树
- HashMap内部实现数组是Node
- 创建 HashMap 对象时，数组 table 默认为 null，加载因子 loadfactor 默认为 0.75
- 添加元素首先默认将数组扩容到16，阈值 threshold 为数组长度与加载因子的积 12；其次计算出key的hash值i，判断table[i]是否为空，为空就直接插入，不为空判断当前位置key和table[i]是否相同；相同value就覆盖，不相同查看table[i]是否红黑树节点，如果是用红黑树直接插入键值对，不是开始遍历链表；如果遇到重复值覆盖，否则直接插入；当 table 某个节点的链表长度达到 TREEIFY_THRESHOLD（默认 8）后，判断 table 的容量是否达到 MIN_TREEIFY_CAPACITY（默认 64）；达到则对当前结点的链表进行树化，否则对 table 扩容，扩容大小为原来的 2 倍，同时阈值更新为当前数组长度乘以加载因子；当树的元素减少到 UNTREEIFY_THRESHOLD = 6 时，会进行转回链表
- HashMap是线程不安全
- Hashmap的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中（1.8以前）；jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中
- HashMap大小为什么是2的幂次方？效率高+空间分布均匀
- HashMap 使用 HashMap(int initialCapacity) 初始化。
存储结构
HashMap是使用哈希表来存储的。
Node是HashMap的一个内部类，实现了Map.Entry接口（本质是一个映射(键值对)。
首先Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量Node(键值对)个数，threshold = length * Load factor。也就是说在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。 超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。
默认的负载因子0.75是对空间和时间效率的一个平衡选择，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
size是HashMap中实际存在的键值对数量， modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
```java static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的 table 数组容量 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子为 0.75 static final int MAXIMUM_CAPACITY = 1 << 30; // 集合最大容量的上限是：2的30次幂 static final int TREEIFY_THRESHOLD = 8; // 链表树化临界值 static final int UNTREEIFY_THRESHOLD = 6; // 树转成链表的临界值 static final int MIN_TREEIFY_CAPACITY = 64; // 树化时数组的最小长度
transient Node
```java
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况。一旦出现拉链过长会严重影响HashMap的性能。于是在JDK1.8版本中对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
根据key获取哈希桶数组索引位置
取key的hashCode值、高位运算、取模运算。
HashMap底层数组的长度总是2的n次方，这是HashMap速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值; h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有此方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
构造器
public HashMap() {
//创建 HashMap 对象时，数组 table 默认为 null，加载因子 loadfactor 默认为 0.75；
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
static final int MAXIMUM_CAPACITY = 1 << 30;
int threshold;
//指定初始容量的构造器
public HashMap(int initialCapacity) {
//DEFAULT_LOAD_FACTOR 0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)// 异常:初始容量小于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);//异常:加载因子小于0 or NaN Not a Number
this.loadFactor = loadFactor;// 指定加载因子大小
//计算 table 的大小,确保为2的n次幂
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
// 这里防止cap已经是2的n次幂, 2的n次幂执行下面操作会扩大2倍
//HashMap 会通过一系列的位移运算和或运算得到比传递值大且最接近指定大小的2的n次幂的数值
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;
}
get
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;
// 数组不为空，且根据hash计算的索引位置有结点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 查询的key与该索引位置的元素相同
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 { // 遍历链表 找到对应的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
put
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过进行扩容。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//hash构造算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 这里是判断table是否初始化，table = null or table.length = 0 初始化table:存放元素的Node<K,V>[]数组
if ((tab = table) == null || (n = tab.length) == 0)
//resize():扩容-数组为空给table初始化16个空间
n = (tab = resize()).length;
//根据key的hash值计算索引值,将table中该索引位置的结点赋值给p,并判断p是否为空
if ((p = tab[i = (n - 1) & hash]) == null)
//若p为null(当前位置没有元素)则创建新的结点Node保存当前要添加的数据,存储到当前索引位置
tab[i] = newNode(hash, key, value, null);
else {
// 这里table当前索引位置的结点已经存在数据，下面分情况判断添加元素
Node<K,V> e;
K k;
// 1. 判断要添加的元素(key)与table中当前索引位置的Node结点是否相同 hash 值相等 && (引用相同 || equals判断相等)
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 元素重复
// 2. 判断当前索引位置元素结点是否是红黑树类型
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3. 说明当前索引位置结点为链表,且第一个结点与要添加的元素key不同,就遍历链表判断key是否存在
else {
for (int binCount = 0; ; ++binCount) {
// 如果key和链表中所有节点元素都不相同，则添加到链表最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 添加元素后判断当前链表是否已经有了8个节点，够8个则调用treeifyBin()方法会判断table大小是否足够64个，到达64个才会树化,不满 64 个空间，会先给 table 扩容
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果要添加的元素key在链表中已经存在，则直接退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;// 当前节点后移
}
}
// 要添加的元素 key 已存在，则将重复的元素返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 将要添加的 value 替换掉旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 修改次数
// 添加元素成功,table长度加1, 判断是否扩容 数组长度是否大于阈值
if (++size > threshold)
resize();
// HashMap 没有实现该方法, 供子类实现扩充功能
afterNodeInsertion(evict);
// return null 表示要添加的元素在table中不存在, 添加成功
return null;
}
resize
JDK1.8
//resize() - table 扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 保存之前数组元素
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 保存旧容量
int oldThr = threshold; // 保存旧临界值
int newCap, newThr = 0;
// 将新容量和新边界值扩大为原来2倍(<<1 == *2)
if (oldCap > 0) {
// 旧容量已经到达最大容量就扩大临界值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将容量和临界值扩大2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 将旧临界值赋值给新容量，这里的场景为初始化时使用了带参数的构造器-tableSizeFor()
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 数组初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 这里也是初始化指定容量大小的场景，临界值赋值给容量，这里给临界值重新计算值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // table 边界值更新为新的边界值
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新 table 容量为默认初始容量或之前容量的2倍
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 原数组不为null，说明是扩容-遍历之前的table 赋值给新数组
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 当前索引存在元素 e
oldTab[j] = null; // 方便回收空间
// 1. 当前索引位置只有一个元素，没有下一个结点
if (e.next == null)
// 重新计算当前元素在新table中的索引，将当前索引结点放到新table
newTab[e.hash & (newCap - 1)] = e;
// 2. 当前索引位置有下一个结点，且是红黑树,指定树的操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3. 当前索引位置有下一个结点，这里是链表类型
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 依次遍历链表结点，确定新数组索引位置
do {
next = e.next; // 取出下一个结点
// 判断当前元素在新数组的索引是否改变
if ((e.hash & oldCap) == 0) { // 不改变还是原来的索引位置
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 改变，新索引 = 旧索引 + 旧容量
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { // 存放到之前索引位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) { // 存放到(之前索引+旧容量)的位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
红黑树链表转换
//树化-将数组中的链表转成红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
// 树化判断，table 数组的长度是否大于等于 64，未达到则进行数组扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 判断当前索引位置结点不为null
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null; // 头尾节点
do {
// 将链表结点转换为树结点类型 TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p; // 给头节点赋值为当前索引结点
else { // 将树结点连接起来
p.prev = tl;
tl.next = p;
}
tl = p; // 给尾结点赋值
} while ((e = e.next) != null); // 链表结点后移
// 将树的头节点放在数组的当前索引位置，然后转换成红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index; // 辅助变量
// table 不为空，且指定key的hash计算的索引位置有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v; // 辅助变量
// 1 判断要删除的元素是否是指定索引链表的第一个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 2 不是第一个元素，判断链表是否还有其他元素
else if ((e = p.next) != null) {
// 2.1 有其他元素且为树结点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 2.2 有其他元素，为链表结构
do { // 遍历链表，依次判断要删除的元素的位置
// 根据hash、key的值找到要删除的元素
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break; // 找到，退出
}
p = e; // p 是要删除节点的上一个节点
} while ((e = e.next) != null);
}
}
// 找到元素，执行删除操作
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 树结点删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 链表只有一个元素删除
tab[index] = node.next;
else // 链表中有多个元素删除
p.next = node.next;
++modCount; // 计数器+1
--size; // 长度 -1
afterNodeRemoval(node);
return node;
}
}
return null;
}
table 数组容量必须是 2 的 n 次幂
为了让哈希后的结果更加均匀。
HashMap 在添加元素的时候，添加到数组的索引位置是根据 key 的 hash 值与数组长度减一 做按位与操作计算得来的（hash & (length - 1)）。为了使元素更加分散的添加到数组中，当数组长度为 2 的 n 次幂时，计算索引的结果和 hash % length 相等(取余效率低)，这样能够减少哈希碰撞。也就是说，当 length 为 2 的 n 次幂时 hash & (length - 1) = hash % length； 位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算。
而当我们手动传入数组长度不是 2 的 n 次幂时，HashMap 底层会执行什么样的操作呢？
由于 HashMap 提供了传递数组长度的构造器，所以我们可以手动给 HashMap 传递 table 长度，而数组长度必须是 2 的 n 次幂，当我们传入其他值时，HashMap 会通过一系列的 位移运算 和 或运算 得到比传递值大且最接近指定大小的 2 的 n 次幂的数值；
通过 位移运算 和 或运算 最终得到的结果为从二进制最左侧的1开始，右边全部为1，比如数组长度指定为10
为什么链表长度为 8 时进行树化？
在 hashCode 离散型很好的时候，链表中存储到第八个索引的概率极小，树化的概率非常小。选择大小 8 是从概率学的角度出发，进行的空间与时间的权衡。
数组扩容后如何计算元素的新索引
在 JDK 1.7 是采用重新计算 hash 的方式，这样要对数组中所有的元素重新计算 hash 值，影响效率，Java 8 对计算索引做了优化。
HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1) & hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到”原位置+旧容量“这个位置。
举例：
正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1 bit 是 0还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的节点分散到新的桶中了。
线程安全测试
public class HashMapInfiniteLoop {
private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);
public static void main(String[] args) {
map.put(5， "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
new Thread("Thread1") {
public void run() {
map.put(3, "A");
System.out.println(map);
};
}.start();
}
}
map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
3.LinkedHashMap
继承自HashMap，且直接实现了 Map接口。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{}
- LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序
- LinkedHashMap的put方法沿用了父类HashMap的put方法
- LinkedHashMap的Entry类就是继承了HashMap的Node类
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);
}
}
构造
final boolean accessOrder;
public LinkedHashMap() {
super();//调用父类无参HashMap
accessOrder = false;
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
put
首先：LinkedHashMap重写了newNode()方法，通过此方法保证了插入的顺序性。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
/**
* 将新创建的节点p作为尾结点tail，
* 当然如果存储的第一个节点，那么它即是head节点，也是tail节点，此时节点p的before和after都为null
* 否则，建立与上一次尾结点的链表关系，将当前尾节点p的前一个节点（before）设置为上一次的尾结点last,
* 将上一次尾节点last的后一个节点（after）设置为当前尾结点p
* 通过此方法实现了双向链表功能，完成before,after,head,tail的值设置
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
其次：关于afterNodeAccess()方法，在HashMap中没给具体实现，而在LinkedHashMap重写了，目的是保证操作过的Node节点永远在最后，从而保证读取的顺序性，在调用put方法和get方法时都会用到。
/**
* 当accessOrder为true并且传入的节点不是最后一个时，将传入的node移动到最后一个
*/
void afterNodeAccess(Node<K,V> e) {
//在执行方法前的上一次的尾结点
LinkedHashMap.Entry<K,V> last;
//当accessOrder为true并且传入的节点并不是上一次的尾结点时,执行下面的方法
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p：当前节点
//b：当前节点的前一个节点
//a：当前节点的后一个节点；
//将p.after设置为null，断开了与后一个节点的关系，但还未确定其位置
p.after = null;
/**
* 因为将当前节点p拿掉了，那么节点b和节点a之间断开了，我们先站在节点b的角度建立与节点a
* 的关联，如果节点b为null,表示当前节点p是头结点，节点p拿掉后，p的下一个节点a就是头节点了；
* 否则将节点b的后一个节点设置为节点a
*/
if (b == null)
head = a;
else
b.after = a;
/**
* 因为将当前节点p拿掉了，那么节点a和节点b之间断开了，我们站在节点a的角度建立与节点b
* 的关联，如果节点a为null,表示当前节点p为尾结点，节点p拿掉后，p的前一个节点b为尾结点，
* 但是此时我们并没有直接将节点p赋值给tail,而是给了一个局部变量last(即当前的最后一个节点)，因为
* 直接赋值给tail与该方法最终的目标并不一致；如果节点a不为null将节点a的前一个节点设置为节点b
*
* （因为前面已经判断了(last = tail) != e，说明传入的节点并不是尾结点，既然不是尾结点，那么
* e.after必然不为null，那为什么这里又判断了a == null的情况？
* 以我的理解，java可通过反射机制破坏封装，因此如果都是反射创建出的Entry实体，可能不会满足前面
* 的判断条件）
*/
if (a != null)
a.before = b;
else
last = b;
/**
* 正常情况下last应该也不为空，为什么要判断，原因和前面一样
* 前面设置了p.after为null,此处再将其before值设置为上一次的尾结点last,同时将上一次的尾结点
* last设置为本次p
*/
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
//最后节点p设置为尾结点，完事
tail = p;
++modCount;
}
}
accessOrder为false时，你访问的顺序就是按照你第一次插入的顺序；而accessOrder为true时，你任何一次的操作，包括put、get操作，都会改变map中已有的存储顺序。
afterNodeInsertion(boolean evict)方法，它的目的是移除链表中最老的节点对象，也就是当前在头部的节点对象，但实际上在JDK8中不会执行，因为removeEldestEntry方法始终返回false。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}//需要获取资料的朋友请加Q君样：290194256*
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
remove
remove方法也直接使用了HashMap中的remove，LinkedHashMap重写了其中的afterNodeRemoval(Node e)，该方法在HashMap中没有具体实现，通过此方法在删除节点的时候调整了双链表的结构。
void afterNodeRemoval(Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//将待删除节点的before和after都设置为null
p.before = p.after = null;
/**
* 如果节点b为null，表示待删除节点p为头部节点，该节点拿掉后，该节点的下一个节点a就为头部节点head
* 否则设置待删除节点的上一个节点b的after属性为节点a
*/
if (b == null)
head = a;
else
b.after = a;
/**
* 如果节点a为null，表示待删除节点p为尾部节点，该节点拿掉后，该节点的上一个节点a就为尾部节点tail
* 否则设置待删除节点的下一个节点a的before属性为节点b
*/
if (a == null)
tail = b;
else
a.before = b;
}
4.TreeMap
- TreeMap底层数据结构是一个红黑树，每个key-value都作为一个红黑树的节点。
- 当使用无参构造器创建 TreeMap 是根据key执行自然排序
- 默认是按键值的升序排序，可以使用指定排序规则的构造器使 TreeMap 按照指定规则排序
- TreeMap实现了SotredMap接口，它是有序的集合。
- key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
构造
private final Comparator<? super K> comparator;
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
put
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { // 初始化根节点
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { // 按照指定规则进行排序
do { // 遍历树结点排序
parent = t;
// 这里会调用构造函数指定的排序方法进行比较
cmp = cpr.compare(key, t.key);
// 要添加的元素比当前节点小，遍历左结点（参考构造方法提供的规则）
if (cmp < 0)
t = t.left;
// 要添加的元素比当前节点大，遍历右结点
else if (cmp > 0)
t = t.right;
else // 按照规则相等（不一定是元素相同），替换 value（Map的方法）
return t.setValue(value);
} while (t != null);
}
else { // 按照默认规则排序
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
5.HashTable
- HashTable 的键和值都不能为 null，否则会抛出空指针异常
- 默认初始容量为 11，加载因子 0.75，所以临界值为 11*0.75=8；达到临界值时，默认扩容机制为之前容量的 2 倍加 1
- HashTable 是线程安全
- 线程安全的策略实现代价太大， get/put所有相关操作都是synchronized的， 多线程访问时只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化
参考
若有收获，就点个赞吧
0 人点赞
