JAVA总结（五）-----|JAVA总结（五）----- 容器（三）-----Map
目录
一、为什么使用Map
二、基于红黑树实现的映射表——TreeMap
1、TreeMap的类声明：
2、TreeMap类字段
3、TreeMap的构造器
3、TreeMap.Entry类
4、TreeMap的实现
三、基于散列表实现的映射表——HashMap
1、HashMap的类声明：
2、HashMap的重要字段
3、HashMap的构造器
4、HashMap的实现
四、双向链表散列的映射表——LinkedHashMap
1、LinkedHahsMap的类声明
2、LinkedHashMap的类字段
3、LinkedHashMap的构造器
4、LinkedHashMap的实现
五、其他Map结构
1、谈java引用
2、WeakHashMap
3、IdentityHashMap
4、ConcuurentHashMap
5、不同Map实现类性能对比。
六、Map与Collection的联系
1、entrySet
2、keySet
3、values
一、为什么使用Map 在前两篇文章中，已经介绍了List与Set。List和Set作为Collection的子接口，提供存储元素的不同策略，并介绍了及其实现的类。但Map并不是作为Collection接口子接口，而是顶级接口（在文章的后面将介绍Map接口与Collection接口的关系）。它提供了另外一种存储策略：映射表。
Map接口：Map采用映射表（或称为关联数组）作为存储元素的基本策略：它维护一组键-值关系，使得我们可以用键来查找值。这种策略使得我们可以由一个对象关联到其他的对象，这无异于是解决许多编程问题的杀手锏。Map接口的实现类很多，比如说：HashMap、TreeMap、LinkedHashMap、WeakHashMap、ConcurrentHashMap、IdentityHashMap等（他们的行为特性各各不相同，这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程中工作等。）。这也说明了Map接口相比List、Set更加重要。
文章图片
| Map（interface） | Map基于映射表存储策略存储元素，并且对于键值对中的键必须保证其唯一性，所以对于所有存储在Map中的元素必须重写equals方法 |
| HashMap | hashMap基于散列表实现。插入、删除、查询“键值对”的开销的是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能。当容器存储的元素超过某个阀门时将会进行扩容。对插入的键还必须重写hashCode方法 |
| LinkedHashMap | LinkedHashMap类似于HashMap，不同的是每个槽位上的链表采取双向链表实现。因此，取得“键值对”的顺序是其插入次序，或者是最近最少使用（LRU）次序。它的性能稍差于HashMap，但迭代访问时其性能要优于HashMap。对插入的键还必须重写hashCode方法。（维护插入次序） |
| TreeMap | 基于红黑树实现。查看“键”或“键值对”时，它们会被排序（次序由Comparable或者Comparator决定）。TreeMap特点在于：所得到的结果是进过排序的。TreeMap是唯一带有subMap()方法的Map，它可以返回一颗子树。其键必须实现Comparable接口，或者向构造器传递该键定制的Comparator。（维护元素次序。） |
| WeakHashMap | 弱键（Weak key）映射，允许释放映射所指向的对象；如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收。 |
| ConcurrentHashMap | 线程安全的Map，替代HashTable与synchronizedMap。在线程（2）说过 |
| IdentityHashMap | 使用“==”替代equals对“键”比较的散列映射。 |
1、TreeMap的类声明：
文章图片
在TreeMap的类声明中，它实现了NavigableMap接口，实际上是实现了SortedMap接口， SortedMap接口支持按元素的自然顺序（Integer类型为键按照元素的从小到大，String类型为键按照字典序排序）或者根据Comparator指定的排序进行排序，它还支持返回TreeMap的一颗子树或者返回TreeMap的第一个键或者最后一个键。
2、TreeMap类字段
①、comparator字段
文章图片
文章图片
comparator字段用于接受定制的排序算法，在put、remove、get方法中均可以通过这个字段进行树的检索。如上图
②、root字段
文章图片
root字段为Entry类型，Entry为红黑树的结点结构，root代表着该红黑树的根节点。
③、size字段
文章图片
size字段为该红黑树的结点数量
④、modCount字段
文章图片
modCount字段和在List的modCount作用是相同的，当进行插入或删除时该值增加或减少。
3、TreeMap的构造器
①、TreeMap的无参构造器
文章图片
创建一个默认的TreeMap，其中comparator字段为null，表示元素需要实现comparable接口，才能进行比较。若插入的元素没有实现该接口那么将抛出异常“ClassCastException”表明插入的元素无法转换成Comparable类型。
②、TreeMap接收定制Comparator的构造器
文章图片
此时元素的比较将不会按照元素Comparable接口定义的实现，而是通过传递过来的Comparator进行比较。
③、TreeMap接收Map类型参数填充数据
文章图片
④、TreeMap根据SortedMap构建类结构
文章图片
3、TreeMap.Entry类
Entry类构建了红黑树的结点结构。
①、Entry类的类声明
文章图片
②、Entry类的字段
文章图片
每一个Entry对象，自动拥有空的子节点链接和一个被设置成BLACK值的color字段。
③、Entry类的构造器
文章图片
4、TreeMap的实现
在经上面的介绍之后我们已经到TreeMap有一个初步的认识，TreeMap的键要么实现Comparable，要么传递Comparator，用于树的检索。此外Entry类用于构建红黑树的结点。在下面我们将介绍TreeMap的实现：
①、插入
TreeMap类的插入操作是从root开始，它会做以下几件事：
1）如果root为null，检查key值是否为key。以传递进来的key，value构建新结点，root为这个新结点。
2）如果root不为null，定义整型比较变量cmp，当comparator字段不为null时，根据comparator比较key与检索到的结点t.key，若key < t.key，那么往树的左子树搜索（当key与t.key向等时，那么把传递进来的value对结点t的value进行设置）；否则，往右子树搜索。直到找到t为null时。此时依据key、value创建新结点，链接到该树中，再把该结点颜色设置成红色，进入维护红黑树性质方法中（在上一章已经介绍过怎么维护插入时红黑树性质）。
3）此时当comparator为null时，那么根据元素实现的comparable接口进行比较（比较情况也是如步骤（二）类似）。直到找到t为null时。再依据key、value创建新结点，链接到该树中，再把该结点颜色设置成红色，进入维护红黑树性质方法中。
下面是TreeMap插入的源码：
public V put(K key, V value) {
Entry t = root;
if (t == null) {
compare(key, key);
// type (and possibly null) checkroot = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry parent;
// split comparator and comparable paths
Comparator 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
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) 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 e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
} ②、检索
TreeMap的检索同插入操作，将会从root开始：通过Compartor或者元素的Comparable进行比较检索，如下：
1）当Comparator不为空时，那么通过Comparator进行比较。此时获取根结点p，按照传递进来的key，当key < p.key。那么往树的左子树进行检索，否则往右子树。直到key = p.key；或者p为null。当p为null时，则返回的value也为null。
2）当Comparator为空时，那么只能通过元素实现的Comparable进行比较。之后同步骤1）。
下面是TreeMap实现的源码：
public V get(Object key) {
Entry p = getEntry(key);
return (p==null ? null : p.value);
}final Entry getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}final Entry getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator cpr = comparator;
if (cpr != null) {
Entry p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
} ③、删除
删除某个结点前，我们需要获取key对应的结点。删除时分为三种情况（在上一章中我已经介绍了）：一是该结点没有左孩子；二是该结点有左孩子，没有右孩子；三是该结点有两个孩子。
1）当该结点没有左孩子时，那么把其右孩子替换到删除结点上
2）当该结点有左孩子没有右孩子时，把左孩子替换到删除结点上
3）当该结点有左右孩子时，那么找该结点的后继元素。如果后继元素为删除结点的右孩子，那么直接把右孩子替换到删除结点。否则，先把后继结点的右孩子替换到删除结点上，然后再把后继结点替换删除结点上。
4）当替换完成后，检查替换结点（情况1、2、3中替换到删除结点的结点）的颜色是否为黑色，如果为黑色那么需要维护红黑性质。（上一章也说明为什么黑色结点就会破坏红黑性质和怎么维护红黑性质）
下面为TreeMap删除的源码：
public V remove(Object key) {
Entry p = getEntry(key);
if (p == null)
return null;
V oldValue = https://www.it610.com/article/p.value;
deleteEntry(p);
return oldValue;
}private void deleteEntry(Entry p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry s = successor(p);
p.key = s.key;
p.value = https://www.it610.com/article/s.value;
p = s;
} // p has 2 children// Start fixup at replacement node, if it exists.
Entry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left= replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { //No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
} 至此，已经基本介绍了TreeMap的实现（虽然没有说红黑树的操作，但是我上一章已经说得很详细，这里就不赘述）。虽然说了TreeMap维护了元素的次序，但是我认为只有看过源码才能更好的理解它怎么维护。TreeMap是线程不安全的类，在多线程下不应使用它。
此外关于TreeMap怎么实现返回一颗子树，限于水平与时间有限待我以后回顾时再写。
三、基于散列表实现的映射表——HashMap HashMap是我们最常使用的容器，因为它支持快速检索，而不必维护元素的次序。但是在JDK1.8之后对它有很大的改变。当每个槽位的链表大小超过8时，链表就会转为红黑树（链表的检索实在是没有树快）。
1、HashMap的类声明：
文章图片
2、HashMap的重要字段
①、table字段
文章图片
table字段即为散列表，在第一次使用HashMap时将会被初始化，其大小为散列表内置的常量“DEFAULT_INITIAL_CAPACITY”大小，也即为16。散列表的容量必须是2的幂次方，当不是其2的幂次方那么会找最接近于2的幂次方。
②、loadFactor字段
文章图片
负载因子（load factor）α其值为：表支持存储的元素/表的容量。当负载因子很小的时候，元素存储在同一个槽位上的可能性增加即冲突增加，所以一个好的负载因子应该是最大限度避免冲突。HashMap的默认负载因子大小为常量“DEFAULT_LOAD_FACTOR”即0.75
③、threshold字段
记录当前散列表能支持存储元素的最大值，即散列表的“临界值”。当存储的元素超过该值时那么散列表将会进行扩容。默认值为“DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR”即12。
3、HashMap的构造器
①、HashMap的无参构造器
文章图片
调用无参构造器时，只有loadFactor字段初始化其值为默认值即0.75，当第一次进行插入时，散列表才会被初始化，此时散列表的容量为16，threshold字段为12。
②、HashMap设定初始化容量的构造器
文章图片
③、HashMap设置初始化容量和负载因子大小的构造器
文章图片
调用该构造器时将会检查初始化容量与负载因子是否符合规范。此外当初始化容量不是2的幂次方数时将会进行tableSizeFor操作即搜索最近与初始化容量的2次方数。
4、HashMap的实现
①、容量为什么是2的幂次方
首先我们看看，HashMap怎么找元素的槽位：
文章图片
文章图片
通过key的散列码的高位与低位做“异或”运算得到的新的散列值hash，然后在与散列表的容量减一做“与”运算。为什么要这么做？在上一章介绍一个好的散列函数能减少“冲突”现象。那么这么做也是为了进一步减少“冲突”。首先来看看几个例子：
整型值5的散列值为5，那么调用hash方法后，其散列值为：
5的二进制表示：0000000000000000 000000000000101
5无符号右移16位：0000000000000000 000000000000000
^
0000000000000000 0000000000000101值为5
假设容量为16：16-1 = 15：0000000000000000 0000000000001111
&
0000000000000000 0000000000000101值为5，所以整型值为5会被放入槽位为5处。
整型值6的散列值为6，那么调用hash方法后
6的二进制表示：0000000000000000 000000000000110
6的无符号右移16位：0000000000000000 000000000000000
^
0000000000000000 000000000000110值为6
假设容量为16：16-1 = 15：0000000000000000 0000000000001111
&
0000000000000000 0000000000000110值为5，所以整型值为6会被放入槽位6处
字符串"abc"的散列值为96354，那么调用hash方法后，其散列值为
96354的二进制表示：0000000000000001 0111100001100010
96354无符号右移16位：0000000000000000 0000000000000001
^
0000000000000001 0111100001100011值为96355
假设容量为16：16-1 = 15： 0000000000000000 0000000000001111
&
0000000000000000 0000000000000011值为3，所以字符串"abc"会被放入槽位3处
字符串"bcd"的散列值为97347，那么调用hash方法后，其散列值为：
97347的二进制表示：0000000000000001 0111110001000011
97347无符号右移16为：0000000000000000 0000000000000001
^
0000000000000001 0111110001000010值为97346
假设容量为16：16-1 = 15： 0000000000000000 0000000000001111
&
0000000000000000 0000000000000010值为2，所以字符串"bcd"会被放入槽位2处
字符串"efg"的散列值为100326，那么调用hash方法后，其散列值为：
100326的二进制表示：0000000000000001 1000011111100110
100326无符号右移16位：0000000000000000 0000000000000001
^
0000000000000001 1000011111100111值为10327
假设容量为16：16-1 = 15： 0000000000000000 0000000000001111
&
0000000000000000 0000000000000111值为7，所以字符串"efg"会被放入槽位7处
通过上面的几个例子，对于不同的散列值总是能够保存在不同的槽位下。
当数大于65535，那么其高位就不全0，即使是极端情况低位全为0（那么此时所有的低位全为0的散列码将全部散列到槽位0处），通过异或能修正这个问题，即使低位不全0，通过异或后值并不会偏离原值太多（相对而言）。当数小于65535，那么高位全为0，此时异或结果就是该数本身，此外数的异或在计算中是很快的。这就是为什么需要进行数的右移16为并进行异或运算。
现在考虑另外一个问题，就是为什么在确定槽位时需要“与”容量减一运算。假设容量为8，那么减一后其二进制为0111，任何数与0111进行“与”元素，那么结果就只能是原数的低三位结果。假设容量为16，那么减一其二进制为1111，任何数与1111进行“与”运算，那么结果就只能是原数的第四位结果。假设容量为9，那么减一后其二进制为1000，任何数1000进行“与”运算，那么结果就能依靠原数第四位的情况。所以，容量为2的幂次方减一后更能够依靠原数二进制码的情况，而如果不是2的幂次方那么更大程度只能靠某位或某几位，所以其“冲突”发生更为频繁，这就是为什么需要2的幂次方作为容器的容量了。
②、初始化容量时不是2的幂次方
初始化容量时，将会调用tableSizeFor()方法，该方法将返回接近于初始化容量的2幂次方。
文章图片
假设初始容量为11，那么：
10的二进制表示为：0000000000000000 0000000000001010
10右移一位并进行或： 0000000000000000 0000000000001111
15右移两位并进行或： 0000000000000000 0000000000001111
15右移四位并进行或： 0000000000000000 0000000000001111
15右移八位并进行或： 0000000000000000 0000000000001111
15右移十六位进行或： 0000000000000000 0000000000001111
因此初始容量为11最近的二次幂为2^4。
假设初始容量为329054，那么：
329053的二进制为：0000000000000001 10000010101011101
329053右移一位并进行或：0000000000000001 111000011111111111
493567右移两位并进行或：0000000000000001 111110011111111111
518143右移四位并进行或：0000000000000001 111111111111111111
524287右移八位并进行或：0000000000000001 111111111111111111
524287右移十六位并进行或：0000000000000001 111111111111111111
因此初始容量为329053最近的二次幂为2^19
因此，该方法总是把某数减一的二进制码含1的最高位至最低全变为1。
③、散列表的扩容
散列表的扩容将发生在，初始时或者原散列表存储元素的数量大于threshold。扩容的方法时resize()。散列表扩容的逻辑是把原来存储容量左移一位，和threshold左移一位（也就是说原容量的两倍）。这里面有几种情况：
1）当原容量与threshold为0时，那么新容量与threshold都为默认值即16、12。
2）当原容量为0，threshold不为0时，那么初始容量为threshold（这种情况只能是初始时传递的容量小于等于0）
3）当原容量不为0时并且其值大于MAXIMUM_CAPACITY（即HashMap支持的最大容量）时，那么threshold为Integer.Max_Value。也就是说把“临界值”扩展到整张散列表中
4）当原容量不为0时并且其值小于MAXIMUM_CAPACITY（即HashMap支持的最大容量）时，那么新容量将为原来容量左移一位（如果扩容的容量大于HashMap支持的最大容量或者原容量小于默认容量，“临界值”将不变），并且新threshold为原threshold左移一位。
最后如果新“临界值”为0（处于这种情况只能是初始化时），那么新“临界值”为新容量 * loadFactor（可能客户端程序指定了loadFactor大小）。
扩容的逻辑完成后，那么table字段为扩容后的散列表大小。并且如果原散列表不为空，那么就把原散列表的数据存入新表中。下面是其源码：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 当原容量不为0时
if (oldCap > 0) {
// 原其值大于MAXIMUM_CAPACITY时
if (oldCap >= MAXIMUM_CAPACITY) {
// 临界值为Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
// 并返回，表明把“临界值”扩展到整张散列表中
return oldTab;
}
// 其值小于MAXIMUM_CAPACITY时，新容量为原容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 只有当新容量不大于MAXIMUM_CAPACITY 与旧容量大于DEFAULT_INITIAL_CAPACITY时
// 那么临界值增倍
newThr = oldThr << 1;
}
// 原容量为0时（处于这种情况的只能是初始化时指定容量小于等于0），但原临界值不为0（此时根据threshold初始化容器）
else if (oldThr > 0)
newCap = oldThr;
else {
// 当原容量与threshold为0时，那么此时是第一次调用插入元素
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当新的“临界值”为0时（处于这种情况只能是初始化时），将按照传递的loadFactor加载“临界值”
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
// 当原表中有数据时，那么把原数据插入新表中
if (oldTab != null) {
for (int j = 0;
j < oldCap;
++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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;
} ④、链式散列表插入
HashMap解决元素插入的“冲突”采取的是链接法，即每个槽位链接一张链表：
文章图片
HashMap中对链表结点的定义如下：每个结点含有4个字段，hash字段（结点的散列值）、key字段（结点的关键字元素，其中必须正确实现hashCode和equals方法）、value字段（保存的元素值）、next字段（指向下一个元素）。因此散列表每个槽位维护的是一张单向链表。
文章图片
HashMap的插入元素类似普通的散列表结构插入（参考我的上一章怎么在链接散列中插入元素），但是在JDK1.8后为了维护性能：当每个槽位上的结点数（即 binCount < 7）等于8时，将把链表转化为红黑树支持更快的检索，增加了代码的复杂度；此外当插入元素过多时，将进行散列扩容操作，这也增加性能和空间开销。下面是HashMap插入元素的步骤：
1）判断散列表是否为空，若为空，那么进行初始扩容，此时容量，临界值，负载因子默认为16、12、0.75。用户指定容量与负载因子那么将按用户规定设定。此时n为散列表的长度。否则执行第二步
2）根据“key”的散列值无符号右移16为并进行“异或”操作后在“与”散列表容量-1（即（key.hashCode（） ^ key.hashCode（） >>> 16 ） & hashTable.length）的结果即为对于的槽位下标。若位置为空，那么直接放入插入的元素。否则，p为该槽位的头结点。执行第三步
3）当p结点（此时为某槽位的头结点）的hash值、key值与待插入结点的hash值、key值具有等价关系，那么此时待插入结点的关键字在散列表中已存在，此时将会进行旧值与新值的替换。否则执行第四步
4）判断p结点是否为树结点，若为则进行红黑树的插入。否则执行第五步
5）此时将依据p结点到链表中搜索，找到空位处进行插入或者找到关键字相同的结点（然后执行旧值与新值的替换）。此时如果是插入，那么当计数值binCount大于8时将转化为红黑树。
6）判断当前散列表的容量是否大于“临界值”，若大于则进行扩容，否则插入完成
文章图片
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab;
Node p;
int n, i;
// 判断当前的散列是否为空
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 进行散列表的扩容操作
// p结点为关键字key对应的槽位的头结点 。若该结点为空，那么说明该槽位还未链接元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 把新元素插入该槽位
else {
Node e;
K k;
// 若头结点与关键字key具有等价关系，则说明该关键字已经插入头结点处
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断头结点是否为树结点，若是则进行红黑树插入
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// binCount为记录该槽位链表的数量
// 检索链表中何处为空或关键key在某结点已经插入，为空则插入新结点，
for (int binCount = 0;
;
++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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 = https://www.it610.com/article/e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 检查是否需要进行扩容（逻辑：当前散列表插入的元素大于"临界值"）
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 对于链式插入有几点：
1）初始插入时，散列表进行初始化。
2）查找槽位时并不是简单的根据键的散列码。而是依据散列值无符号右移16为并进行“异或”操作后在“与”散列表容量-1
3）对于插入相同的键，则其旧值将被新插入的新值替换，并返回旧值此时散列表大小不变化。注：散列表键可以为null。
4）当槽中结点是树结点或者链表数量大于8时，将会进行红黑树插入。
⑤、树式散列表插入
在链式散列表插入中，对于某个槽位的链表大小大于8时将会转换为红黑树，并进行树插入。首先看看HashMap对树结点的定义：（水平有限，以后回顾再写）
文章图片
⑥、链式散列表的删除：
同样链式散列表删除与散列表的删除并无过多的不同。最大的还是链表转化为红黑树后进行的删除。下面是其删除的步骤：
1）判断散列表是否为空，是否关键字的槽位中有元素。如果没满足条件则删除失败
2）待删除的元素是否为头结点，若是则执行第五步
3）若槽位中的结点是树结点则进行红黑树删除
4）依次遍历链表直到找到关键字key插入的结点。
5）删除关键字key所在结点的链接，返回关键字的值
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab;
Node p;
int n, index;
// 判断散列表是否为空，是否关键字的槽位中有元素。如果没满足条件则删除失败，否则执行删除
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e;
K k;
V v;
// 若待删除元素为链表的头结点，那么删除头结点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 若槽位中结点为树结点，则进行红黑树删除
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
// 否则，依次遍历当前的链表直到找打待删除关键字对应的结点，若没有找到也删除失败
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到的结点不为null，并且找到的结点value值与待删除结点的value相等，才能执行删除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 在次进行判断找到结点是否为树结点
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
// 链表删除操作
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
} ⑦、树式散列表的删除（水平有限）
⑧、链式散列表的检索
散列表是为了快速检索而产生的数据结构，其中对于不产生“冲突”的元素检索时间复杂度为O（1），即使产生了“冲突”时间复杂度为O（1+链表元素数目）。下面是HashMap对于检索的步骤：
1）判断散列表是否为空，是否关键字的槽位中有元素。如果没满足条件则检索失败
2）判断头结点是否为待查询的元素，若是则返回该头结点；否则执行步骤三
3）判断结点是否为树结点，若是则进行红黑树的检索
4）依次遍历链表元素，当链表中某个结点为待查询元素则返回该结点；否则查询失败
final Node getNode(int hash, Object key) {
Node[] tab;
Node first, e;
int n;
K k;
// 判断散列表是否为空，是否关键字的槽位中有元素。如果没满足条件则检索失败
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断头结点是否为待查询的元素，若是则返回该头结点
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)first).getTreeNode(hash, key);
// 依次遍历链表元素，当链表中某个结点为待查询元素则返回该结点；否则查询失败
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} ⑨、树式散列表的检索
四、双向链表散列的映射表——LinkedHashMap LinkedHashMap的链表是一个双向循环链表，它也是根据散列表作为其实现结构。它继承自HashMap，支持有序的插入次序；当遍历时根据插入次序或LRU的次序。
1、LinkedHahsMap的类声明
文章图片
2、LinkedHashMap的类字段
①、accessOrder
文章图片
该字段为true时则遍历使用LRU次序，false使用插入次序
3、LinkedHashMap的构造器
①、LinkedHashMap无参构造器
文章图片
默认无参构造器将调用HashMap的无参构造器，即此时散列表的默认容量、负载因子为16、0.75。并在遍历时使用插入次序。
②、LinkedHashMap设置初始容量的构造器
文章图片
设置初始容量，并在遍历时使用插入次序。
③、LinkedHashMap设置初始容量与负载因子构造器
文章图片
④、LinkedHashMap设置初始容量与负载因子和accessOrder构造器
文章图片
此时将根据客户端的调用设定遍历时采取什么策略进行输出
⑤、LinkedHashMap带初始容量的构造器
文章图片
4、LinkedHashMap的实现
LinkedHashMap的链表结点增加了两个属性，before与after即该结点的前一个插入结点与后一个插入结点，这两个属性要区别于原来链表的pre（前驱指针）与next（后继指针）。比如说，有结点node2插入，那么此时它的before指向node1（可能node1并不是它的前驱），它的after指向node3（同样，node3可能不是它的后继）。
文章图片
文章图片
LinkedHashMap的插入、删除、检索操作同HashMap，只不过在HashMap有四个专门为LinkedHashMap重写的方法，在LinkedHashMap实现我专门介绍这四个方法：
①、重写的newNode(int hash, K key, V value, Node
在插入时，对于有空位的地方将调用该方法创建包含存入元素的链表结点。在LinkedHashMap同样支持该向功能，只不过它将插入的元素链接在所有结点的最后一个（或者说除了原链表外，还存在一个隐式链表（我称为次序链表）该链表通过before与after属性链接所有结点）。如下图：插入Entry2时，Entry1与它并不在同一张链表中，但Entry1的after为Entry2，Entry2的before为Entry1进行链接与维护次序。
文章图片
文章图片
Node newNode(int hash, K key, V value, Node e) {
LinkedHashMap.Entry p =
new LinkedHashMap.Entry(hash, key, value, e);
// 该方法将会把插入的结点p链接到最后一个位置
linkNodeLast(p);
return p;
}private void linkNodeLast(LinkedHashMap.Entry p) {
// 获取次序链表中最后一个结点
LinkedHashMap.Entry last = tail;
tail = p;
// 如果最后一个结点没有，那么说明该散列表没有插入元素，则插入p
if (last == null)
head = p;
// 否则，进行链接
else {
p.before = last;
last.after = p;
}
} ②、重写的afterNodeInsertion(boolean evict)
该方法支持是否插入后立刻删除次序链表中的第一个结点，即删除最早插入结点。下面是其源码：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
} ③、重写的afterNodeAccess(Node
该方法维护了LRU次序，当构造LinkedHashMap时声明需要使用LRU维护次序时，那么对于访问某个元素或者插入相同关键字元素时都会调用该方法，即进行次序链表的重排序。根据LRU算法：只要有某个元素被访问过那么把这个元素放入次序链表尾部，并且把它的后一个插入结点放入该位置。比如说：当访问过Entry1之后，那么Entry1被放入最后一个位置，Entry2就变成第一个结点，Entry3成为第二个结点。
文章图片
void afterNodeAccess(Node e) { // move node to last
LinkedHashMap.Entry last;
// 维护的次序时根据LRU 并且次序链表中最后一个元素不是维护的结点时，进行重排序
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
p.after = null;
// 当维护结点的before为null，说明此事维护结点为头结点
if (b == null)
head = a;
// 否则，before的after就为维护结点的后一个插入结点
else
b.after = a;
// 当维护结点的after不为null，则把after的before为维护结点的前一个插入元素
if (a != null)
a.before = b;
// 否则 ，将维护结点移动到最后一个结点处，它的前一个插入结点为last（如果last不null的话）
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
} ④、重写的afterNodeRemoval(Node
在删除某结点除了在散列表中解除链接，也需要在次序链表中解除链接（让后一个插入结点放在删除结点处）。
void afterNodeRemoval(Node e) { // unlink
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
// 解除删除结点的before与after的引用
p.before = p.after = null;
// 若删除结点为头结点，那么让其后一个插入结点成为头结点
if (b == null)
head = a;
// 否则，让其后一个插入结点放在当前位置
else
b.after = a;
// 若删除结点为尾结点，那么让其前一个插入结点成为尾结点
if (a == null)
tail = b;
else
a.before = b;
} 五、其他Map结构 1、谈java引用
每一种编程语言都有自己的操纵内存中元素的方式，是直接操纵，还是间接操纵（如C中指针概念）。在java中简化了这种形式，任何对象都可以操纵内存，但操纵的标识符实际上是一个对象的“引用”。它就像遥控器（引用）与电视机（对象）之间的关系。引用与指针的概念不同，指针直接操纵的是地址，而引用操作的是对象。
String s；s是一个引用，但是它并没有指向任何对象。
new String（）是一个对象，但是没有任何引用指向它，我们无法操纵这个对象，也就无法操作相关的内存。
通过 String s = new String（）；语句形式使我们的引用s操作对象。
①、对象生死的判断
java不同于C++它没有析构函数，也就是没有显示释放对象（即对象所占有内存）的方法，当我们创建对象过多后，内存将会被使用殆尽。java设计之初“一处编译，多次运行”的设计理念的实现依归于java虚拟机。java虚拟机就提供了释放对象的方法——垃圾收集器。
在垃圾收集器中通过根搜索算法实现来判断对象是否可存活。这个算法的基本思想是：通过一系列“GC Roots”的对象作为起点，从这些节点开始向下搜索，搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链相连接时，则证明该对象是不可存活的。
文章图片
| 虚拟机栈中（栈帧的局部变量表）中引用的对象 |
| 方法区中类静态属性引用的对象 |
| 方法区中常量属性引用的对象 |
| 本地方法栈中Native方法所引用的对象 |
在JDK1.2之前对引用的概念是狭隘、片面的：如果引用类型的数据中存储的数值代表的是另一块内存的起始地址，就称这个内存代表着一个引用。一个对象在这概念下只有被引用和不被引用。那么描述那些“食之无味，弃之可惜”的对象就显得无能为力。在JDK1.2之后对引用作了以下几点分类：
| 强引用（Strong Reference） | 强引用指在程序代码中普遍存在，类似于Object o = new Object（）这类的引用，只要强引用还在，垃圾收集器就永远不会回收被引用的对象 |
| 软引用（Soft Reference） | 软引用描述一些还有用，但并非必须的对象。对于软引用关联着的对象，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中并进行第二次回收。当这次回收还没有足够的内存，才会抛出内存溢出异常。SoftReference类实现软引用。 |
| 弱引用（Weak Reference） | 弱引用也被用来描述非必须对象，但它的强度要比软引用更弱一些，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。当垃圾收集开始工作时，无论内存是否够用，都会回收弱引用的对象。WeakReference类实现弱引用 |
| 虚引用（Phantom Reference） | 虚引用是最弱的引用，一个对象是否有虚引用存在，完全不会对其生存时间构成影响，也无法通过一个虚引用获取一个对象实例。为一个对象设置虚引用关联的唯一目的就是希望能在这个对象被收集器回收时收到一个系统通知。PhantomReference类实现虚引用 |
WeakHashMap的键是一个被弱引用关联的对象（即该对象需继承WeakReference），这也就表示当系统发生垃圾回收时该“键值对”将会被回收，并且不存在于散列表中。此外WeakHashMap还是通过散列表进行实现的，所以其键需要重写hashCode与equals方法。
①、WeakHashMap类声明
文章图片
②、WeakHashMap字段
1）table字段
文章图片
table字段即为该WeakHashMap所使用的散列表，它是一个根据需求调整大小，并且容量是二的次方数。
2）queu字段
文章图片
queue字段是一个队列，当每次发生GC时把那些弱引用的键存放在该队列中，当做集合操作时，散列表会根据该队里调整散列表的中的数据、大小。
③、WeakHashMap的构造器
WeakHashMap的构造器与HashMap相同，就不赘述。
④、WeakHashMap的实现
在WeakHashMap中插入、删除、检索与HashMap的逻辑相同。但是有一点不同的是，在执行这些操作之前首先需要根据queue字段保存的的那些被GC删除的弱引用对象键，将他们从散列表中删除以保持内存中释放、散列表中无法查询。即expungeStaleEntries（）方法。该方法是一个线程同步方法，它做以下步骤：
1）依次遍历queue的对象，获取它当前出队对象x
2）找到x在散列表的槽位
3）在对应槽位链表中删除x，重复步骤1、直到队列中没有元素
private void expungeStaleEntries() {
// 一次遍历queue队里中的元素
for (Object x;
(x = queue.poll()) != null;
) {
synchronized (queue) {
@SuppressWarnings("unchecked")
Entry e = (Entry) x;
// 找到x在散列表ode位置
int i = indexFor(e.hash, table.length);
// 获取该槽位的头结点
Entry prev = table[i];
Entry p = prev;
// 在次链表中依次遍历直到找到x，并删除它
while (p != null) {
Entry next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = https://www.it610.com/article/null;
// Help GC
size--;
break;
}
prev = p;
p = next;
}
}
}
} 3、IdentityHashMap
IdentityHashMap使用散列表作为其数据结构，在比较键(和值)时使用引用相等代替对象相等。或者说当且仅当两个键k1、k2满足关系（k1==k2）时被认为是相等的。（而在HashMap或其它的类HashMap的结构中两个键只有满足：(k1==null ?k2 = = null: k1.equals (k2))时才被认为相等）。这也就是说IdentityHashMap允许键中存在逻辑相同的键。
4、ConcuurentHashMap
一个同步的HashMap、替换HashTable、synchronizedHashMap。采用锁分解技术，每个槽位将获取一把ReentrantLock锁实现同步操作。（ConcurrentHashMap详解）
5、不同Map实现类性能对比。
文章图片
总结：1）对于任何Map，初始化的元素插入都会耗费一些时间，这是因为进行散列表的初始化。
2）采取散列结构的Map其检索性能要优于树结构的Map。
六、Map与Collection的联系 在第一篇容器文章我说过，容器的遍历通过实现Itertor接口，重写next、hashNext等方法实现遍历。或者实现Iterable接口，实现foreach遍历。对所有的List、Set实现类中都实现了这些接口以支持遍历容器中元素。
Map所有实现类并没有实现Itertor或者Iterable接口。但每个实现类提供了entrySet、keySet、values等方法实现Map中键-值对的遍历。或者说这是Map与Collection的联系。
1、entrySet
①、Entry接口
Entry接口为Map接口中静态嵌套接口
Entry对象是一个映射中键-值对的一个实体、一个视图。Entry对象可以修改映射中对应键的值，也可以获取实体中键值对，通过实现类的entrySet方法获取映射中所有键值对的视图即Entry对象。其里面包括getKey、getValue、setValue等使用方法。
②、entrySet方法
entrySet返回映射中包含所有实体的视图，它是一个Set对象。当通过这个视图更改映射将反应在Map中，反之亦然。
1）TreeMap中entrySet方法
i、EntryItertor类
EntryItertor类继承自PrivateEntryIterator类，它是TreeMap基本的比较器实现类，实现Itertor接口。PrivateEntryIterator类初始化时将expectedModCount=modCount，当进行迭代访问时，如果发现expectedModCount！=modCount将抛出ConcurrentModificationException异常。
PrivateEntryIterator类是一个双向迭代器，支持元素的删除操作。
a）PrivateEntryIterator类字段
*next字段：指向该树下一个结点。初始时为根结点
*lastReturned字段：返回当前检索到的结点。初始时为null
b）PrivateEntryIterator实现
*hasNext方法：当next字段不为null时返回true，否则返回false。表明元素已经遍历完
文章图片
*nextEntry方法（搜索遍历结点后一个结点）：开始时结点e为next所指的结点，随后搜索树中e结点的后继结点。当e为null或者modCount != expectedModCount时抛出异常，返回结点e，并把lastReturned指向e结点。
文章图片
*prevEntry方法（搜索遍历结点前一个结点）：开始时结点e为next所指的结点，随后搜索树中e结点的前驱结点。当e为null或者modCount != expectedModCount时抛出异常，返回结点e，并把lastReturned指向e结点。
文章图片
*remove方法：删除当前遍历结点，通过调用TreeMap的删除操作。删除完成重置expectedModCount = modCount，lastReturned = null。（注：当删除结点没有两个孩子时，那么下一次遍历很可能将发生异常）
ii、EntrySet类
EntrySet继承自AbstractSet，它是TreeMap映射视图，支持元素的遍历（通过创建EntryItertor类实例）、删除、查询。不支持元素的插入操作。当需要映射中实体的视图时，TreeMap将会创建EntrySet实例，并保存该实例到TreeMap的entrySet字段中。（注：EntrySet类中）
文章图片
2）HashMap中entrySet方法
HashMap构建entrySet与TreeMap采取基本相同的逻辑。不同的是针对的数据结构不同。比如说在HashMap中构建遍历器中使用的是HashIterator类，它是一个单向遍历器。同样当需要映射中实体的视图时，HashMap将会创建EntrySet实例，并保存该实例到HashMap的entrySet字段中。
文章图片
2、keySet
keySet方法返回在此映射中包含该键的视图，它是一个Set对象。视图对键的任何更改将会反映在映射中，反之亦然。该视图支持遍历、删除、清除、检索等操作。不支持插入操作。
①、TreeMap中keySet方法
初始时调用keySet方法将会创建一个KeySet对象实例保存在TreeMap中navigableKeySet字段中。并返回该对象
文章图片
KeySet类继承自AbstractSet类实现NavigableSet接口。当初始时将会接收TreeMap实例作为构建的根本。
1）KeyIterator类
KeyIterator类继承自PrivateEntryIterator类，在之前已经说过PrivateEntryIterator类是一个双向遍历器，但KeyIterator类重写nextEntry方法，使其支持返回该结点的键。但并没有重写prevEntry方法。即KeyIterator是一个单向遍历器。
文章图片
2）KeySet类
KeySet类实例返回映射中键的视图，支持视图遍历键、删除某个键、清空该映射表、返回树中某处的键（如root、last等）、返回一颗子树视图键等等操作。
②、HashMap中keySet方法
同TreeMap的keySet方法，返回该HashMap映射中键的视图。仅支持视图遍历键、删除某个键、清空该映射表等操作。此外KeySet类继承自AbstractSet。
文章图片
3、values
【JAVA总结（五）-----|JAVA总结（五）----- 容器（三）-----Map】values方法将返回映射中值的视图，它是一个Collection对象。视图对值的任何更改将会反映在映射中，反之亦然。该视图支持遍历、删除、清除、检索等操作。不支持插入操作。
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- android第三方框架（五）ButterKnife
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- 【故障公告】周五下午的一次突发故障
- 7.9号工作总结～司硕
- 华为旁！大社区、地铁新盘，佳兆业城市广场五期！
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- 五年后，我要成为独立自强自信的女性
- 二十年后的家乡