白话HashMap
通过这篇文章我想回答下列几个问题：
1、HashMap的数据存储结构？
2、存储数据的逻辑？
3、key为null是怎么存储的？
4、怎么根据key取数据的？
5、为什么初始容量必须是2的n次方？
?
第一个问题：hashmap的数据存储结构
?如上图，HashMap由一个数组和一系列的链表组成，存储的数据类型为Entry，一个HashMap的内部类
Entry{hash，key，value，next}。
数组的长度为2的n次方，默认值为16，如果自己设置的值不为2的n次方，则由hashmap自己处理为2的n次方，比如说：
HashMap<String,String> hsm = new HashMap<String,String>(13);
源码如下：
public HashMap(int initialCapacity, float loadFactor) { 。。。。 // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; //实际效果就是2的n次方，当大于initialCapacity后停止循环 this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); //数组扩容临界值 table = new Entry[capacity]; //用计算后的容量初始化数组大小。。。。 }?传入13，实际数组大小为16。
?
第二个问题：存储数据的逻辑
以刚才new的HashMap为例，存入 hsm.put("abc", "奥运、亚运都是浮云，有能耐整好春运");
看源码：
public V put(K key, V value) {if (key == null) //如果key为null，执行特殊存储操作，在问题3中详细回答 return putForNullKey(value); int hash = hash(key.hashCode()); //再次hash int i = indexFor(hash, table.length); //查找在数组中的存储位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果数组当前位置不为null，循环数组对应位置的链表 ?Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果存在符合hash和key的条件的entry ?V oldValue = e.value; e.value = value; e.recordAccess(this); //啥也没干 ?return oldValue; } } modCount++; addEntry(hash, key, value, i); //如果数组当前位置为null，则插入当前entry ?return null; }?查找在数组中的存储位置，源码：
static int indexFor(int h, int length) { return h & (length-1); }?? 如果length为2的n次方，则length-1的二进制为1111...，比如现在（16-1）为1111，经过计算后返回值一定在数组长度范围内。
新增Entry到数组中，源码：
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex]; //new一个新的Entry，并存储在数组的bucketIndex位置上 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //判断数组是否需要扩容 if (size++ >= threshold) resize(2 * table.length); }?第三个问题：key为null是怎么存储的
源码：
private V putForNullKey(V value) { //static final Object NULL_KEY = new Object(); //如果key为null，则用默认的NULL_KEY的hashcode来查找数组中位置 //我还看过不用indexFor（），直接 i=0 的实现，个人认为这种实现更好 int hash = hash(NULL_KEY.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { if (e.key == NULL_KEY) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }? 第四个问题：怎么根据key取数据的
源码：
?
public V get(Object key) {if (key == null)//key为null则用特殊方法取value return getForNullKey(); int hash = hash(key.hashCode()); //根据key的hash值取数组位置 //如果不为null，则循环挂靠在该位置上的链表 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //如果找到则返回value值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } private V getForNullKey() { //取默认NULL_KEY的hash值，查找数组位置 int hash = hash(NULL_KEY.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> e = table[i]; while (true) { if (e == null) return null; if (e.key == NULL_KEY) return e.value; e = e.next; } modCount++; addEntry(hash, (K) NULL_KEY, value, i); return null; }?第五个问题：为什么初始容量必须是2的n次方
看源码：
static int indexFor(int h, int length) { return h & (length-1); }所有的存储和查找都是通过这个方法查找数组中的位置的。
举个不是2的n次方的例子，如果长度为13会发生什么情况？
13-1的二进制为：?1100
也就是说hash值以...1100、...1101、 ...1110、 ...1111为结尾的一系列的key都会落到数组[12]的位置上，换句话说这个位置的链表会很长，通过hash散列的效果差，查找效率会低。
?
?
?
?