如有错误或补充，望指出）

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

HashMap 的数据结构是有数组和链表组成的。

数组的特点是：寻址容易，插入和删除困难。

链表的特点是：寻址困难，插入和删除容易。

哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。

在上图可以发现每个元素存储的是一个链表的头结点。

那么这些元素是按照什么样的规则存储到数组中呢？

一般情况是通过 hash(key)%length 获得，也就是元素的 key 的哈希值对数组长度取模得到。

比如上述哈希表中，

12 % 16=12,
28 % 16=12,
108 % 16=12,
140 % 16=12。
所以 12、28、108 以及 140 都存储在数组下标为 12 的位置。

HashMap 里面实现一个静态内部类 HashMapEntry （继承 Map.Entry），其重要的属性有 key，value，next，hash，从属性key，value我们就能很明显的看出来HashMapEntry 就是 HashMap 键值对实现的一个基础 bean，HashMap的基础就是一个线性数组，这个数组就是HashMapEntry []，Map 里面的内容都保存在Entry[]里面。

（欢迎补充...）

这个我们要重点说下，我们一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法），HashTable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低。

HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对HashTable的一个改进。

接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。

首先，length为2的整数次幂的话，h&(length-1) 就相当于对 length 取模，这样便保证了散列的均匀，同时也提升了效率；

其次，length为2的整数次幂的话，为偶数，这样 length-1 为奇数，奇数的最后一位是1，这样便保证了 h&(length-1) 的最后一位可能为 0，也可能为1（这取决于 h 的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。

而如果length为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 h&(length-1) 的最后一位肯定为 0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

参考：HashMap源码剖析