Java源码学习:HashMap实现原理
软件设计 2017-09-14
HashMap继承制AbstractMap，很多通用的方法，比如size()、isEmpty()，都已经在这里实现了。来看一个比较简单的方法，get方法：
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
} 单从这里看看不到Map的搜索策略，这里显示的仅仅就是遍历全部元素挨个测试是否匹配。
remove方法中先匹配到元素，然后利用迭代器Iterator的remove方法将元素从记录中删除。
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
} 终于看到存储key和value的地方了，这里马上出现了两个Java关键字，transient和volatile：
transient volatile Set<K> keySet = null;
transient volatile Collection<V> values = null; transient关键字的意思是说改字段不会被持久化和反持久化，这个会在对象序列化到文件时用到。参考这里。
volatile就比较复杂一点儿了，一旦一个共享变量（类的成员变量、类的静态成员变量）被volatile修饰之后，那么就具备了两层语义：
1）保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。
2）禁止进行指令重排序。
[blockquote]
参考：http://www.cnblogs.com/dolphin0520/p/3920373.html
[/blockquote]
有点儿线程安全的意思，就是说一个变量被另外一个线程修改了，其他在使用这个变量的线程也会知道。
文章中所举例子：
//线程1
boolean stop = false;
while(!stop){
doSomething();
}
//线程2
stop = true 以上代码是有可能死循环的。
接下来初始化Entry时，如果用一个Map去初始化另外一个Map，那么这个Map的初始大小将为原先Map的2倍：
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
} 拿到原先Map的size之后初始化一个新的Entry数组，这个数组的的size增加到原先Map的2倍。方法Integer.highestOneBit(num)的作用是得到比num还大的但是是2的指数倍的数。这些数其实就是2,4,8,16,32,64,128,256,512
可以看出JDK源码中很多地方对于*2这种操作都不是直接乘以2，而是采用向左位移一位，比如：
(number - 1) << 1
HashMap数据结构
插入元素
1、key为null的Entry存放在数组Entry[]的第一位的Entry链表中，即Entry[0]，仔细看看，Map.put()方法其实是有返回值的，这个返回值就是被替换掉的Value（如果存在的话）。
2、key不为空，通过Hash散列之后存入数组不同位置的链表中。散列中用到了按位与（&）运算：
/**
* 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);
} 如何进行Hash散列
按位与运算规则如下：
0 & 0 = 1
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
也就是只有同时两个都为1时才等于1。这里要求数组的长度必须是2指数倍是有原因的。比如length = 256（2的8次方），那么它换算成二进制就是1后面8个0：
100000000
256 - 1 换算成二进制刚好是7个1：
1111111
用这个数与任意的数N进行按位与运算的效果是：保留N的后7位：
1 1 1 1 1 1 1
& 1 0 1 0 0 1 0 1 0
-------------------------------
0 0 1 0 0 1 0 1 0 后面这7位就像亮着的几盏灯，亮几盏就能截取多少位。正是这样实现了数据的Hash散列。
从上面的代码可以看出，Hash散列时仅用到了了Object.hashCode()的后几位，如果n - 1 = 15即0x1111,那么发送Hash冲突的可能性会非常大，为了解决这个问题，可以理解为需要在原先的Object.hashClde()基础之上做一些混淆，即使整个原始HashCode都会影响最终的散列。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} 这里通过高位与低位（向右位移的距离不一样）的异或运算进行“混淆”。
总结
HashMap的实现原理?
通过元素的哈希码来做映射，将数据散列到一个数组中，如果发生了哈希冲突则将冲突的元素形成一个链表进行存储。Java8中进行了优化，冲突的元素多到一定程度时，将改链表为红黑树，这样有效提高了高冲突时的性能；
HashMap需要注意些什么?
注意两个参数：
容量（Capacity）：容器也可以叫做数组的初始大小，如果元素增加到一定程度（也就是负载因子），就会将容量翻倍。
负载因子（Load factor）：默认负载因子是0.75，也就是当元素超过四分之三的时候会增加数组的大小。
需要注意的是，如果你想要HashMap遍历得更快，应该把容量设计得小点儿、负载因子设计大点儿，这样其实是让HashMap的数组存储地更密集些，能提高遍历速度。
