HashMap底层实现原理
大家都知道HashMap是存储key-value形式的集合，允许key和value为null。那么HashMap底层到底是如何实现的呢？今天查了一些资料，简单记录一下。
HashMap底层通过数组和链表实现。数组可以理解，那么链表是用来做什么的呢？这是因为两个不同的对象，hashCode是可能相等的。为了在数组存储hashCode相等的两个不同对象，实际上，一个数组里面的元素，是一个链表。当根据hashCode，得到数组的索引时，先去数组中该处是否已经有值，如果有，再去判断两个对象是否相等，如果相等，则替换旧值，如果不等，则在链表尾部添加元素。
看一下HashMap的put方法：
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
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;
}
}
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
} 通过上面方法可以清楚的看出，当遇到hashCode相等的情况时，是如何处理的。
仔细看一下代码，我们发现，数组索引的位置并不是直接通过hashCode得到的，而是先调用了hash()方法，从新计算hash值，然后再通过indexFor()方法计算，才最终得到数组的索引。为什么不直接使用hashCode呢？带着这个疑问，我们依次看看上面两个方法：
static int indexFor(int h, int length) {
return h & (length-1);
} 先看indexFor方法，它对length-1进行了与操作，当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。而HashMap底层数组的长度总是 2 的 n 次方，这是HashMap在速度上的优化。
按道理讲，这样就可以了得到索引了，为何还要下面的hash方法呢？先看看hash()方法的作用是什么
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}可以看出，它是对hashCode的高16位和低16位做了一个异或操作。这样就相当于，我们在执行indexFor()方法时，引入了高16位的数据，减少了hash碰撞的可能性。从而get请求查询需要遍历链表的情况表少，查询操作更快。