HashMap可谓是面试中的高频热点问题了，一般可能也就面试前突击复习下，背些知识点，面试后可能就忘了，为了做到不遗忘，我们需要彻底弄懂它的机制。
Hash表介绍
首先我们看一张经典的图：
hash.jpg
这里有一个大小为16的数组，比如说我现在有一个整数32，那么如果使用除余法，496 % 16 = 0，所以496就应该存在数组0的位置上。但这个时候如果再存一个896呢？ 896%16 = 0，按理应该也放在数组0位置，但这个位置已经被496占用了，这种现象被成为hash碰撞，这个时候我么可以在数组0后面挂一个链表，有碰撞的都往链表上加。
以上的除余法是一种散列算法，碰撞后挂链表是一种解决hash碰撞的算法，叫做拉链法。其实还有其他算法，具体的大家可以自己搜索 hash表 去学习，这里介绍只是为了给HashMap的讲解打个基础。
HashMap的hash机制
HashMap的存储形式
通过上面hash表的介绍，我们知道了hash表其实核心存储还是数组，HashMap也一样：
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
当然，这个数组存的不再是上面的整数那么简单，而是一个对象结构：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//省略部分代码
}
HashMap的散列算法
首先，我们一般是存一个key-value进来，第一步就是用key 的hash值计算一个hashcode出来（怎么计算后面再说）
那HashMap到底是如何确定将这个hashcode代表的值放在table[]数组的哪个位置呢？计算方式代码很简单，理解起来确实很难：
int n = table.length;
int hash = 通过key计算出来的hash值
int pos = (n-1)&hash
这段神奇的(n-1)&has其实和hash % n 道理是一样的，但有些地方不一样，
要说位运算效率高，能实现的黑科技也多，但代码确实不好懂，这种计算方式一般人基本都搞不懂，这里我们重点分析下
以table.length = 16为例，所有的数据最终取余后都要分布在16个位置上，从感性上大家都有一种认知：超过了16后，数据太大其实和分布在0到16之间是一样的。这种认知反应在二进制上就是：高位基本没用，只要低位的信息就可以了。所以如果想要利用位运算达到去余的目的，我们就得需要将hash的高位擦除，保留低位。保留多少位数肯定由table.length决定。
那么如何擦除数据呢？
还是以table.length=16为例，除余的结果肯定分布在0到15之间，假设hash值为 10100101 11000100 00100101（二进制），那么真正有用的只后面四位（15转换成二进制后只有后面4位有效），所以看下这个运算：
10100101 11000100 00100101
& 00000000 00000000 00001111
------------------------------------------------
00000000 00000000 00001111
可以看到hash&（n-1)实际就是为了保留hash的低位数据，擦除高位数据，很明显，想要擦除高位，（n-1）的结果低位必须是全1，这也就解释了为什么HashMap的table长度始终是2的平方，只有这样，table.length-1才能保证低位结果是全1。事实上最终结果就是数据在table数组中的位置。
HashMap的hash优化
从上面我们看到，在确定一个数据的存储位置时，HashMap只取了低位数据，这样其实有一个缺陷，那就是我们抛弃了高位信息，也就抛弃了数据分布的离散性，如果数据碰巧有了某种规律，每一次都会产生碰撞，这样就划不来了，一个好的hash散列算法应该要尽量降低碰撞，这个时候我们可以把高位信息利用起来。
这也是为什么HashMap不直接使用key的hash值的原因，如果key的hash算法实现比较糟糕就无法保证数据离散，从而无法减少hash碰撞了。现在我们看下HashMap是怎么优化的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
代码很简单，又是一个位操作，现在我们来详细分析下这样做的目的，
假设key.hashCode() = 10100101 11000100 00100101
现在h >>> 16 就是无符号右移16位，高位补0
变成了 00000000 00000101 00101100
然后：
10100101 11000100 00100101
^ 00000000 00000101 00101100
------------------------------------------------
10100101 11000001 00001001
可以看到，这么做后能够利用高16位信息和低16位信息一起得出一个新的结果，这样新的低位信息其实是老的高位信息和老的低位信息共同作用的结果，这样的话就能减少初始key.hashCode()的碰撞可能性。
总结
这里只是大致的讲解了下HashMap的hash机制，核心的扩容，存储， 查找，删除等具体分析还请静待下一篇文章。
网友评论