HashMap的存储原理
比较数组和链表的查找效率
数组使用下标维护数据，所以查找起来比较快，但是插入和删除的话需要移动后面的数据，数据插入和删除比较慢。
链表使用指针来维护链表结构，查找起来比较慢，因为要从第一个结点开始查找，但是插入和删除的话不需要移动数据，只需要改变指针的指向就可以了，所以插入和删除比较快。
HashMap提供高效的查找，插入和删除。是怎么做到的？
HashMap的存储结构
- HashMap底层是以数组方式进行存储的。将key-value键值对作为数组的一个元素进行存储。
- Key-value都是Map.Entry中的属性。其中将key的值进行hash之后进行存储，即每一个key都是计算hash值，然后再存储。每一个hash值对应一个数组下标，数组下标是根据hash值和数组长度计算得来的。
- 由于不同的key值可能具有相同的hash值，即一个数组的某个位置出现两个相同的元素，对于这种情况，hashmap采用链表的形式进行存储。
图为hashmap的存储结构图。
Entry结构分析
Entry是hashMap中封装key-value键值对的，主要包括如下属性
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
protected Object clone() {
return new Entry<>(hash, key, value,(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}
HashMap属性分析
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
/** *默认情况下，hashmap大小为16.即1<<4就是1乘以2的4次幂=16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** * hashMap的最大值 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** * 默认加载加载因子，即使用空间达到总空间的0.75时，需要扩容。 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** * 声明hashmap一个空数组。 */
static final Entry<?,?>[] EMPTY_TABLE = {};
/** * 最开始时，hashmap是一个空数组。 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/** * map的元素的个数 */
transient int size;
/* * hashmap的实际存储空间大小。这个空间是总空间*加载因子得出的大小。 * 比如默认是16，加载因子是0.74。则threshold就是12。 */
int threshold;
/** * 加载因子，即使用空间达到总空间的0.75时，需要扩容。 */
final float loadFactor;
/** * threshold这个值的最大值就是Integer.MAX_VALUE */
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
PUT方法
put（key,value）方法是hashmap中最重要的方法，使用hashmap最主要的就是使用put,get两个方法。put方法底层存储又是什么呢，我们可以从put方法的源码进行分析
public V put(K key, V value) {
// 首次存储元素，初始化存储空间
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null，则将null放入元素的第一个位置
if (key == null)
return putForNullKey(value);
// 计算key的hash值
int hash = hash(key);
// 根据key的hash值，数组长度计算该Entry<key,value>的数组下标
int i = indexFor(hash, table.length);
/** **如果当前key的已经存在于map中，则将新值替换成旧值。 **/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断同一个key，既要判断hash值相同，还要判断key是同一个key，因为
// 相同的key有可能hash值也相同。双重判断保证是同一个key。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果是新的key需要存储，则增加操作次数modCount++
modCount++;
// 将新增key-value键值对添加中map中。
addEntry(hash, key, value, i);
return null;
}
addEntry方法
addEntry方法是将新增的key-value键值对存入到map中。该方法主要完成两个功能：
1.1. 添加新元素前， 判断是否需要对map的数组进行扩容，如果需要扩容，则扩容空间大小是多少?
什么情况下需要对map的数组进行扩容呢？当hashmap中元素的个数超过数组大小*loadFactor时，就会进行数组扩容，若hashmap的数组默认大小已经是最大的了，就不再进行扩容，而是采取随机碰撞的方法。loadFactor的默认值为0.75，数组大小的默认值为16，所以，当hashmap中元素的个数超过16*0.75=12时，就把数组的大小阔展为2*16=32，即阔展一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。
1.2. 对于新增key-value键值对，如果key的hash值相同，则构造单向列表。
从源码分析结果如下：
/** ** hash:key的hash值
** key:存储的键
** value：存储的value对象值
*** bucketIndex：数组下标位置，即key-value在数组中的位置。
**/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 往数组中添加新的key-value键值对
createEntry(hash, key, value, bucketIndex);
}
createEntry
该方法主要完成两个功能，第一是添加新的key到Entry数组中，第二就是对于不同key的hash值相同的情况下，在同一个数组下标处，构建单向链表进行存储。
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出当前位置的元素，如果是新添加的key,则e为null，已经有的元素为不为空。
Entry<K,V> e = table[bucketIndex];
// 添加新的key-value值或构建链表
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
hashmap中的get方法
首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。所以，hashcode与equals方法对于找到对应元素是两个关键方法。
Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等。
在改写equals方法的时候，需要满足以下三点：
(1) 自反性：就是说a.equals(a)必须为true。
(2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
(3) 传递性：就是说a.equals(b)=true，并且b.equals(c)=true的话，a.equals(c)也必须为true。
通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
hashmap中的hash算法
我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式那？java中是这样做的，
static int indexFor(int h, int length) {
return h & (length-1);
}
首先算得key得hashcode值，然后跟数组的长度-1做一次“与”运算（&）。看上去很简单，其实比较有玄机。比如数组的长度是2的4次方，那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高，我以2的4次方举例，来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
说到这里，我们再回头看一下hashmap中默认的数组大小是多少，查看源代码可以得知是16，为什么是16，而不是15，也不是20呢，看到上面annegu的解释之后我们就清楚了吧，显然是因为16是2的整数次幂的原因，在小数据量的情况下16比15和20更能减少key之间的碰撞，而加快查询的效率。
所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)：
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;