一、TreeMap
TreeMap封装了红黑树，在代码里的体现就是private transient Entry<K,V> root; 也就是一个key，value键值对。具体的红黑树操作都在里面，就不细讲了。
1.1 put(k,v)
remove(k)也是和下面道理相似，理解就行。
public V put(K key, V value) {
// 获得根结点
Entry<K,V> t = root;
// 如果根节点为空，那么新建一个Entry()，赋值为根节点
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 下面这段代码目的是找出key应该插在那个父节点之下
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 如果用户自定义了比较器
if (cpr != null) {
// 找到t == null ，那么此时parent就是想要的父节点。
do {
parent = t;
cmp = cpr.compare(key, t.key);
// 判断归属于左子树还是右子树。
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
// 如果已经存在这个key，那么覆盖value
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);
}
// 通过找出parent， 在此结点之下挂上新的结点， 红黑树调整都在Entry内部进行。
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;
}
1.2 一帮以getEntry()方法为基础的获取元素的方法，其中包括containsKey()，get()，remove()等
// 根据key，找出对于的红黑树结点Entry<K,V>
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;
}
1.3 一帮以getFirstEntry()，getLastEntry()为基础的获取头和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()；
//得到最左，即得到最小的key
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
1.4 KeySet 和 EntrySet
由于map没有Iterator，因此遍历需要借助Set
keySet保存了map中的key作为集合，之后可以调用map.get(key)得到value对象。
public static void main(String[] args) {
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(1,2);
map.put(2,3);
map.put(4,5);
map.put(-1,-8);
map.put(-4,-9);
Set<Integer> keySet = map.keySet();
Iterator<Integer> it = keySet.iterator();
while (it.hasNext()) {
Integer key = it.next();
System.out.println(map.get(key));
}
}
map.entrySet()直接把红黑树的keySet取出来
由于取出来的Set上面已经是保存在红黑树上的K,V，因此就可以直接访问K,V。
public static void main(String[] args) {
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(1,2);
map.put(2,3);
map.put(4,5);
map.put(-1,-8);
map.put(-4,-9);
Set<Map.Entry<Integer, Integer>> keySet = map.entrySet();
Iterator<Map.Entry<Integer, Integer>> it = keySet.iterator();
while (it.hasNext()) {
Map.Entry<Integer,Integer> entry = it.next();
System.out.println(entry.getValue());
}
}
两种方法总结，keySet得到key后，还需要在到红黑树中跑一次二分，最终得到V； entrySet直接得到红黑树的keySet，那么就能直接获得值。因此entrySet的方法速度更快。
二、HashMap
2.1 hash解决冲突的方法
1）开发地址法
m是地址长度
di是增量，对di的取法有三种
线性探测再散列：di = 1 , 2 , 3 , … , m-1
平方/二次探测再散列：di = 1^2 , -1^2 , 2^2 , -2^2 , 3^2 , -3^2 , … , k^2 , -k^2
随机探测再散列 di 是一组伪随机数列
例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元，参图8.26 (a)。如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元，参图8.26 (b)。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，………，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。
2）拉链法
每个桶维护一个链表
3）再哈希法
构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
4)建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表
2.2 hashmap的源码分析
cvte面试的时候被问到了hashmap的put(k,v)实现，可见hashmap的重要性
数据域
public class More ...HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量（容量为HashMap中槽的数目）是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子，用于生成桶的大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 某个链表长度大于8，有可能转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 删除冲突节点后，hash相同的节点数目小于这个数，红黑树就恢复成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 扩容的临界值
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组
transient Node[] table;
HashMap的key可以是null
table[0]存放了null的键值对。
HashMap中的结点Node
//继承了Map.Entry<K,V> 每个结点上保存 K,V对
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
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; }
// 重写了hashcoed的计算方法
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;
}
}
红黑树
封装了红黑树，一大段代码都是红黑树的操作，例如插入，删除，返回头节点，还有保持平衡性的调整。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
容量大小capacity 和 加载因子 loadFactor
如果桶的数量 >= 容量（默认为16） * 加载因子(默认0.75) ， 那么就进行扩容。
为什么hashMap的实际容器大小是2^n
传入capacity之后，实际的桶大小是 大于capactity的最近的2^n的数。
hash值的计算是这样的 ： 调用了(length-1) & hash ，因此必须要保证leng = 2^n
对于length = 16, 对应二进制”1 0000”, length-1=”0 1111”
假设此时h = 17 .
(1) 使用”h % length”, 也就是”17 % 16”, 结果是1 .
(2) 使用”h & (length - 1)”, 也就是 “1 0001 & 0 1111”, 结果也是1 .
我们会发现, 因为”0 1111”低位都是”1”, 进行”&”操作, 就能成功保留”1 0001”对应的低位, 将高位的都丢弃, 低位是多少, 最后结果就是多少 .
刚好低位的范围是”0~15”, 刚好是长度为length=16的所有索引 .
HashMap的四个构造函数
// 指定“容量大小”和"加载因子"
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//指定“容量大小”的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 传入子map，会根据子map的大小，当前容器进行调整大小， 最后赋值到当前map上
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//传入key的hash值，value，false，true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab:哈希桶，是一个头节点数组 ， n: 桶的大小 , p: key的哈希值，对于桶的位置i，该位置桶的头节点
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //如果哈希桶是空的
n = (tab = resize()).length; // 调用resize()，对哈希桶进行扩容
if ((p = tab[i = (n - 1) & hash]) == null) //如果 key的hash值，在桶中的位置是头一次出现
tab[i] = newNode(hash, key, value, null); // 生成一个新的结点
else {
// 这类情况就需要顺着桶的头节点，一路摸下去，找到链表上存在的结点。
Node<K,V> e; K k;
// 结点存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 结点为树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 结点为链
else {
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;
}
}
//找出了结点，进行写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get方法
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
rehash
rehash主要是在扩容的时候执行。 扩容的时候，newCap = oldCap << 1 ， 也就是*2 。
rehash做了哪些事呢？
第一步：扩容，<<1位
第二步：取出所有就的Node<K,V>[]oleTable ， 对于每个桶上面的每个结点，都需要挂到新的桶上，它根据新的容量进行下标计算，再把结点挂上去。
多线程执行rehash导致的死锁问题
假设桶1后面挂着的点是这样的。
1）table[1] -> p1 -> p2;
2）线程1对table[1]进行重新挂点时，被中断,那么此时线程1的e和next分别如下
table[1] -> p1(e) -> p2(next);
do{
Entry<K,V> next = e.next;// <--假设线程一执行到这里就被调度挂起了
inti = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}while (e != null);
3)此时线程2完成了rehash，把桶1改变了结构
由于用了头插法，因此线程2执行完之后变成了这样。
table[1] -> p2(next) -> p1(e)
4）这个时候线程1恢复执行，可以发现，e 和 next 构成了循环链表，陷入了死循环。
三、ConcurrentHashMap
HashMap线程安全有以下几种选择：
1）HashTable：内部调用synchronizaed 方法，对类进行上锁
2）Collections.synchronizedMap(map) ：内部持有一个mutex，每个方法都对mutex进行上锁，因此效果和1）差不多。
3）ConcurrentHashMap：分段锁技术
分段锁
早期
默认维护了16把锁，把哈希表通过某种规则划分成16组。多个线程访问同一组，那么他们是互斥的。但是如果多个线程访问不同组，那么他们就可以并发。
java8之后
利用CAS算法和synchronized对链表的头节点上锁实现同步
插入
ConcurrntHashMap学习这方面有助于理解并发编程
- size()方法和mappingCount()方法的异同，两者计算是否准确？
- 多线程环境下如何进行扩容？
四、LinkedHashMap
父类就是HashMap
public LinkedHashMap() {
// 调用HashMap的构造方法，其实就是初始化Entry[] table
super();
// 这里是指是否基于访问排序，默认为false
accessOrder = false;
}