（一）（ Map集合底层实现）HashMap、LinkedHashMap、Hashtable，ConcurrentHashMap，TreeMap的底层实现。
(一)HahMap：数组+链表-->构成哈希表形式。【效率高，线程不安全-->不支持并发；put操作会引起死锁，导致CPU利用率接近100%】
1. get（）----从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
put（）----当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部
简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
2.0 HashMap的resize（rehash）【扩容很消耗性能--->所以预设元素个数能有效提高HashMap性能】
3.0 遍历的方式：
HashMap的两种遍历方式
第一种
|
1
2
3
4
5
6
7
|
Map map = new HashMap();
Iterator iter = map.entrySet().iterator(); while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next(); Object key = entry.getKey(); Object val = entry.getValue(); } |
效率高,以后一定要使用此种方式！
第二种
|
1
2
3
4
5
6
|
Map map = new HashMap();
Iterator iter = map.keySet().iterator(); while (iter.hasNext()) {
Object key = iter.next(); Object val = map.get(key); } |
效率低,以后尽量少使用！
（二）LinkedHashMap【继承于HashMap】---哈希表 和 双向链表 【依靠双向链表-->保证 迭代顺序是插入顺序】
1.相比HashMap多了 after 和before两个指针。
1) Entry元素：
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：
- /**
- * 双向链表的表头元素。
- */
- private transient Entry<K,V> header;
- /**
- * LinkedHashMap的Entry元素。
- * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
- */
- private static class Entry<K,V> extends HashMap.Entry<K,V> {
- Entry<K,V> before, after;
- ……
- }
2) 初始化：
通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor);
- accessOrder = false;
- }
3) 存储：
LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
- void addEntry(int hash, K key, V value, int bucketIndex) {
- // 调用create方法，将新元素以双向链表的的形式加入到映射中。
- createEntry(hash, key, value, bucketIndex);
- // 删除最近最少使用元素的策略定义
- Entry<K,V> eldest = header.after;
- if (removeEldestEntry(eldest)) {
- removeEntryForKey(eldest.key);
- } else {
- if (size >= threshold)
- resize(2 * table.length);
- }
- }
- void createEntry(int hash, K key, V value, int bucketIndex) {
- HashMap.Entry<K,V> old = table[bucketIndex];
- Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
- table[bucketIndex] = e;
- // 调用元素的addBrefore方法，将元素加入到哈希、双向链接列表。
- e.addBefore(header);
- size++;
- }
- private void addBefore(Entry<K,V> existingEntry) {
- after = existingEntry;
- before = existingEntry.before;
- before.after = this;
- after.before = this;
- }
4) 读取：
LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
- public V get(Object key) {
- // 调用父类HashMap的getEntry()方法，取得要查找的元素。
- Entry<K,V> e = (Entry<K,V>)getEntry(key);
- if (e == null)
- return null;
- // 记录访问顺序。
- e.recordAccess(this);
- return e.value;
- }
- void recordAccess(HashMap<K,V> m) {
- LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
- // 如果定义了LinkedHashMap的迭代顺序为访问顺序，
- // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。
- if (lm.accessOrder) {
- lm.modCount++;
- remove();
- addBefore(lm.header);
- }
- }
5) 排序模式：
LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。
- private final boolean accessOrder;
一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor);
- accessOrder = false;
- }
这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：
- public LinkedHashMap(int initialCapacity,
- float loadFactor,
- boolean accessOrder) {
- super(initialCapacity, loadFactor);
- this.accessOrder = accessOrder;
- }
该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法，在将新条目插入到映射后，put和 putAll将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
- protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
- return false;
- }
此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。
例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。
- private static final int MAX_ENTRIES = 100;
- protected boolean removeEldestEntry(Map.Entry eldest) {
- return size() > MAX_ENTRIES;
- }
（三）效率低下HashTable的容器【底层实现：【拉链法实现的】哈希表。线程安全，synchronized关键字，锁住整个哈希表】
1.继承自Dictionary ；
实现了 Map接口
2. HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低
（四）ConcurrentHashMap：【高并发，高吞吐量的HashMap。线程安全的，高效的，支持并发（因为用了segment锁分段技术）】
1. 它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment结构)来表示这些不同的部分，【每个段其实就是一个小的hashtable】，它们有自己的锁。只要多个修改操作发生在 不同的段上，它们就可以并发进行。
2.ConcurrentHashMap的结构：【Segment数组结构和HashEntry数组结构组成】
3.put（）方法：
前面的所有的介绍其实都为这个方法做铺垫。ConcurrentHashMap最常用的就是put和get两个方法。现在来介绍put方法，这个put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。另外由于涉及到多线程，put方法就要复杂一点。在多线程中可能有以下两个情况
①如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；
②如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。
整体流程就是首先定义不允许key或value为null的情况放入 对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。
如果这个位置是空的，那么直接放入，而且不需要加锁操作。
如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。4.get方法（）
get方法比较简单，给定一个key来确定value的时候，必须满足两个条件 key相同 hash值相同，对于节点可能在链表或树上的情况，需要分别去查找.
这个方法用于将过长的链表转换为TreeBin对象。但是他并不是直接转换，而是进行一次容量判断，如果容量没有达到转换的要求，直接进行扩容操作并返回；如果满足条件才链表的结构抓换为TreeBin ，这与HashMap不同的是，它并没有把TreeNode直接放入红黑树，而是利用了TreeBin这个小容器来封装所有的TreeNode.
（五）TreeMap：【基于红黑树（一种自平衡的二叉树）实现-->】
1.什么是平衡二叉树：
平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。
2.put方法（）：
如果存在的话，old value被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
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
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;
} |
3. get（）函数
get函数则相对来说比较简单，以log(n)的复杂度进行get
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
final Entry<K,V> 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<? super K> k = (Comparable<? super K>) key;
Entry<K,V> 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;
}public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
} |