集合框架——Map接口及其实现类源码解析（JDK7/8）
JDK7
好了，老规矩，上源码，
* An object that maps keys to values. A map cannot contain duplicate keys;
* each key can map to at most one value.
总结一下：
- Map是集合框架中的一个顶级接口，Map并不是一个真正意义上的集合（are not true collections），map中存储的是key-value键值对
- 一个map集合中不允许存在重复的key，每个key最多映射一个value
- 但是这个接口提供了三种“集合视角”（collection views ），使得可以像操作集合一样操作它们，具体如下：
- key的集合： map's contents to be viewed as a set of keys
- value的集合：map’s contents to be viewed as a collection of value
- key-value映射（Entry）的集合：map’s contents to be viewed as a set of key-value mappings
- 谨慎的使用可变对象作为键值，map中不允许将自己作为键值，但是可以作为value（但是不要这么做，会出错，例如hashcode、clone、toString、equals）
- 所有Map接口的实现类中都应该提供2个标准的构造函数（）和（map）用来copy
- Map中提供了一个内部接口Entry<K,V>（ A map entry (key-value pair).），用来表示一组key-value对象，获得这些entry的唯一方法就是从Map.entrySet视图的Iterator中，也就是说，map的迭代器迭代的是entry对象，如果在通过Iterator获得entry对象之后，如果移除了map中该元素（除非是通过entry.setValue操作），那么entry的操作是无效的，我给出一个例子。
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
map.put("1", "1");
Set<Entry<String, String>> entries = map.entrySet();
Iterator<Entry<String, String>> iterator = entries.iterator();
//获取entry
Map.Entry<String, String> entry = iterator.next();
//移除map中entry对应的映射对
map.remove("1");
//对entry操作
entry.setValue("2");
System.out.println(entry.getKey());
System.out.println(entry.getValue());
System.out.println(map);
}
图片.png
我们可以看到map中已经没有键值对了，但是entry中依然可以获取，但是这时候entry的操作是无效的。
HashMap
我们来看一下他的内部实现：
图片.png
简单来说，HashMap内部是一个数组，数组里面存放的是一个链表，链表的元素是Entry。
- 再来看一下一些比较重要的字段：
- capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。默认初始化为16.
- loadFactor：负载因子，默认为 0.75
- threshold：扩容的阈值，等于 capacity * loadFactor
- PUT过程分析
跟着源码看一下，
public V put(K key, V value) {
// 当插入第一个元素的时候，需要先初始化数组大小
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 为 null，最终会将这个 entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
// 1. 求 key 的 hash 值
int hash = hash(key);
// 2. 找到对应的数组下标
int i = indexFor(hash, table.length);
// 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，
// 如果有，直接覆盖，put 方法返回旧值就结束了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//fail-fast机制
modCount++;
// 4. 不存在重复的 key，将此 entry 添加到链表中
addEntry(hash, key, value, i);
return null;
}
- 数组初始化：
在第一个元素插入map的时候初始化数组
private void inflateTable(int toSize) {
// 保证数组大小一定是 2 的 n 次方。
// 比如这样初始化：new HashMap(20)，那么处理成初始数组大小是 32
int capacity = roundUpToPowerOf2(toSize);
// 计算扩容阈值：capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化数组吧
table = new Entry[capacity];
initHashSeedAsNeeded(capacity); //ignore
}
//我们来看一下JDK8中计算容量的方法：该方法用来返回大于等于该给定整数的最小2^次幂值；
//首先需要了解一下，7=0111，其最小2^次幂为1000=0111+1；
// 11=1011，其最小2^次幂为10000=01111+1；
//29=011101，其最效2^次幂为100000=011111+1；
//避免n=2^m这种情况，经过下面运算后导致结果比n本身大一倍
int n = cap - 1;
//核心思想就是让n的二进制位全是1（不包括符号位）
n |= n >>> 1;//确保第一次出现1的位及其后1位都是1
n |= n >>> 2;//确保第一次出现1的位及其后3位都是1；
n |= n >>> 4;//确保第一次出现1的位及其后7位都是1；
n |= n >>> 8;//确保第一次出现1的位及其后15位都是1；
n |= n >>> 16;//确保第一次出现1的位及其后所有位都是1；
//到这n=0x00111111...11；
//n+1即为0x0100000......00就是大于等于n的最小2^次幂
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- hash函数，以Java8为例，引用知乎上的回答，也叫作扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key.hashCode（）是Key自带的hashCode()方法，返回一个int类型的散列值。我们大家知道，32位带符号的int表值范围从-2147483648到2147483648。这样只要hash函数松散的话，一般是很难发生碰撞的，因为HashMap的初始容量只有16。，但是如此大的一个数组内存是放不下的，所以这个散列值是不能直接拿来用的，在用之前还要对数组的长度取模运算，得到余数才是索引值。我们来看一下HashMap中是怎么实现的
int index = hash & (arrays.length-1);
那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。
但是这时，又出现了一个问题，即使散列函数很松散，但只取最后几位碰撞也会很严重。这时候hash算法的价值就体现出来了，hashCode右移16位，正好是32bit的一半。与自己本身做异或操作（相同为0，不同为1）。就是为了混合哈希值的高位和地位，增加低位的随机性。并且混合后的值也变相保持了高位的特征。
图片.png
好了，现在找到了对应的index，我们看一下是如何添加进链表的呢，
- 链表添加元素
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容，后面会介绍一下
resize(2 * table.length);
// 扩容以后，重新计算 hash 值
hash = (null != key) ? hash(key) : 0;
// 重新计算扩容后的新的下标
bucketIndex = indexFor(hash, table.length);
}
// 往下看
createEntry(hash, key, value, bucketIndex);
}
// 这个很简单，其实就是将新值放到链表的表头，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
- 数组扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新的数组
Entry[] newTable = new Entry[newCapacity];
// 将原来数组中的值迁移到新的更大的数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
只有当发生哈希冲突并且size（键值对的数量）大于等于阈值时才会扩容，扩容就是用一个新的大数组替换原来的小数组，并将原来数组中的值迁移到新的数组中。
由于是双倍扩容，迁移过程中，会将原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16，那么扩容后，原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置。代码比较简单，这里就不展开了
- get 过程分析
相对于 put 过程，get 过程是非常简单的。- 根据 key 计算 hash 值。
- 找到相应的数组下标：hash & (length - 1)。
- 遍历该数组位置处的链表，直到找到相等(==或equals)的 key。
JDK8
Jdk1.8 中没有 indexFor 函数，直接使用 table[index = (n – 1) & hash]（与运算
交换左右，结果不变）
这里存在一个问题，即使负载因子和 Hash 算法设计的再合理，也免不了会出现拉链过
长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。于是，在 JDK1.8 版本中，
对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（TREEIFY_THRESHOLD
默认超过 8、大于等于）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高
HashMap 的性能（O(logn)）。 当长度小于（UNTREEIFY_THRESHOLD 默认为 6、小于等
于），就会退化成链表
