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）为黑色

如果一个节点为红色，则它的两个子节点为黑色

对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点，黑节点个数成为黑高。