JAVA Map 之元素定位，冲突碰撞
基本特性：
- 维持健值对的集合接口，健不可以重复，每一个健只能映射到一个值。
- Map替代了原来的虚拟类Directory。
- Map提供了三种集合视角，keys（KeySet），values（Values），entries（key-value）（EntrySet），Map元素的顺序体现于遍历器返回的Map元素顺序。
- 需要注意的是，不可以用可变的元素作Map的健，这会影响到equals对键值的操作，例如，不可以使用Map自身作为key，但是可以作为value。
- 一些Map的实现对key-value有特殊的要求，如key不可以为null。
HashMap：
查找索引：
jdk1.7 数组散列结构：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
length为2的n次方的情况下，length-1 则二进制末尾为1，“&” 操作计算结果末尾位置与h二进制末尾相同（否则，末尾为0，和任何数的 “&” 操作，末尾都为0，散列性降低，易发生碰撞），定位索引的位置优劣取决于哈希函数生成哈希值的散列均匀程度。
h & (length -1) 相当于 h % length 但前者性能优于后者
jdk1.8
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
...
索引策略同1.7
map 容量： 2的n次方
jdk1.7：指定 initialCapacity 则为 initialCapacity，不指定则为 DEFAULT_INITIAL_CAPACITY 16
涉及需要扩展容量时：
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize 找到一个大于等于toSize的2的n次方数
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
jdk1.8： 如果指定初始容量 initialCapacity 则通过tableSizeFor 优化容量，如果不指定，则默认为 DEFAULT_INITIAL_CAPACITY 16；
构造函数：
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);
}
...
/**
* 生成一个2的n次方数最为目标容量
* Returns a power of two size for the given target capacity.
* Hackers Delight, sec 3.2 章节3.2介绍的上舍入算法
*/
static final int tableSizeFor(int cap) {
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;
}
容量调整时，需要调用 tableSizeFor。
碰撞：
jdk1.7：使用数组散列，索引到同一位置的不同元素，使用链表存储，碰撞元素插入链表头部。
jdk1.8： TREEIFY_THRESHOLD 变量控制使用链表还是树，当链表节点数达到 TREEIFY_THRESHOLD（默认8），改为使用红黑树存储碰撞元素。
ConcurrentHashMap：
jdk1.7 segment 分段加锁
jdk1.8 synchronized（synchronized (f) ）； cas（casTabAt）
TreeMap:
红黑树：
满足特定红黑性质的二叉搜索树，区别于平衡二叉树（AVL：左右子树高度差不能超过1），近似平衡（任何路径不能长于最小路径的2倍），节点增加color数据位（其它为k、left、right）。
节点标为红色，黑色
根节点时黑色的
每个叶节点（NIL）为黑色
如果一个节点为红色，则它的两个子节点为黑色
对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点，黑节点个数成为黑高。