参考链接： Java HashMap
一、什么是Map
根据Map源码上的注释可以得到：
1.Map是一个接口，他是key-value的键值对，一个map不能包含重复的key，并且每一个key只能映射一个value；
2.Map接口提供了三个集合视图：key的集合，value的集合，key-value的集合；
3.Map内元素的顺序取决于Iterator的具体实现逻辑，获取集合内的元素实际上是获取一个迭代器，实现对其中元素的遍历；
4.Map接口的具体实现中存在三种Map结构，其中HashMap和TreeMap都允许存在null值，而HashTable的key不允许为空，但是HashMap不能保证遍历元素的顺序，TreeMap能够保证遍历元素的顺序。
二、HashMap的概念
1.什么是哈希表
哈希表（HashTable，散列表）是根据key-value进行访问的数据结构，他是通过把key映射到表中的一个位置来访问记录，加快查找的速度，其中映射的函数叫做散列函数，存放记录的数组叫做散列表，哈希表的主干是数组。
上面的图中就是一个值插入哈希表中的过程，那么存在的问题就是不同的值在经过hash函数之后可能会映射到相同的位置上，当插入一个元素时，发现该位置已经被占用，这时候就会产生冲突，也就是所谓的哈希冲突，因此哈希函数的设计就至关重要，一个好的哈希函数希望尽可能的保证计算方法简单，但是元素能够均匀的分布在数组中，但是数组是一块连续的且是固定长度的内存空间，不管一个哈希函数设计的多好，都无法避免得到的地址不会发生冲突，因此就需要对哈希冲突进行解决。
（1）开放定址法：当插入一个元素时，发生冲突，继续检查散列表的其他项，直到找到一个位置来放置这个元素，至于检查的顺序可以自定义；
（2）再散列法：使用多个hash函数，如果一个发生冲突，使用下一个hash函数，直到找到一个位置，这种方法增加了计算的时间；
（3）链地址法：在数组的位置使用链表，将同一个hashCode的元素放在链表中，HashMap就是使用的这种方法，数组 链表的结构。
2.什么是HashMap
HashMap是基于哈希表的Map接口的实现，提供所有可选的映射操作，允许使用null值和null键，存储的对象时一个键值对对象Entry<K,V>;
是基于数组 链表的结构实现，在内部维护这一个数组table，数组的每个位置保存着每个链表的表头结点，查找元素时，先通过hash函数得到key值对应的hash值，再根据hash值得到在数组中的索引位置，拿到对应的链表的表头，最后去遍历这个链表，得到对应的value值。
三、HashMap类中的主要方法
1.HashMap中的几个重要的变量
//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//默认最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子，默认为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//数组表，大小可以改变，且大小必须为2的幂
transient Entry[] table;
//当前Map中key-value映射的个数
transient int size;
//下次扩容阈值，当size > capacity * load factor时，开始扩容
int threshold;
//负载因子
final float loadFactor;
//Hash表结构性修改次数，用于实现迭代器快速失败行为
transient volatile int modCount;
2.HashMap的Entry实体
HashMap存储的对象是一个Entry实体，Entry是HashMap中的一个静态内部类，在HashMap类中的源码为：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
//构建一个新的实体
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
.........
}
其中key值定义的为final，因此在定义之后就无法进行修改，key和value就是在调用map时对应的键值对，next存储的是链表中的下一个节点，他是一个单链表，hash是对key的hashcode再次进行哈希运算之后得到的值，存储起来是为了避免重复计算。
3.HashMap的初始化
初始化构造一个hashMap有四种方法，这四种方法都比较好理解，我们主要看一下第一种方法：
在指定了初始化容量和负载因子时，首先会对参数进行检查，符合条件后，会根据初始化容量进行调整，使其必须是2的次幂，因此即使用户在使用时指定了容量，实际初始化的容量不一定等于指定的容量，至于为什么必须得是2的次幂，在后面的过程中在讲，在设置好容量之后，根据当前容量和负载因子计算出下一次扩容时的阈值threshold，也就是map中的元素个数达到这个值之后就要进行扩容。
//1.指定容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " loadFactor);
//根据初始化的容量对实际的容量进行调整，必须为2的次幂
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//根据容量和负载因子计算出当前的阈值
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
//2.仅指定容量，使用默认的负载因子，内部实现实际上还是依赖的第一种方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//3.使用默认容量和负载因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
//4.根据指定的map初始化，根据指定的map的容量和默认容量共同决定初始化容量，使用默认负载因子
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
4.HashMap的put操作
由于HashMap中允许存在null的key，因此在插入元素的时候，需要对key值进行判断，其主要步骤为：
（1）如果key为null值，单独进行处理，putForNullKey（value）；
（2）如果key不是null值，根据key的hashCode再次计算hash值 hash(key.hashCode());
（3）根据hash值和table数组的长度得到该元素在数组中的索引位置i=indexFor(hash,table.length);
（4）取得该位置的链表，如果链表不为空，对链表进行遍历，判断key值在链表中是否存在，已存在用新的value值替代旧值，同时返回旧值；
（5）否则，向该位置的链表的表头插入新的元素addEntry(hash,key,value,i)
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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;
}
}
modCount ;
addEntry(hash, key, value, i);
return null;
}
在put操作中，我们也看到了其中包含好几个方法，接下来对这几个方法进行说明：
当key值为null时，默认是将该元素插入到table[0]的位置，首先也是取到table[0]位置的链表，如果链表不为空，对链表进行遍历，判断是否存在key为null的值，如果存在，将新的value替换旧的值，同时返回旧值，如果不存在，就在链表的表头插入一个新的Entry
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount ;
addEntry(0, null, value, 0);
return null;
}
在put操作中，最终决定元素存放的位置还需要以下两个方法，第一个可以看出来是对一个值使用hash方法，使用了各种异或、移位的操作，他是对key的hashCode再一次进行计算以及二进制位操作的过程，目的是为了使最终在数组中存储的位置尽可能的分布均匀，具体移位操作的过程就不讲了
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
indexFor方法是根据得到的hash值和数组的长度得到最终元素在数组中存放的索引位置，主要使用的是与(&)操作，这种方法也是保证获取的index一定是在数组的范围内，例如，如果数组的默认容量时16，h=25，转换为二进制计算得到的是：index=9，也就是该元素在table[9]的位置。
HashMap的的数组长度一定是2的次幂，在这里也可以看出来，比如长度为16的数组，那么length-1=15，他的二进制是01111，长度为32的数组，length-1=31，二进制为011111，可以看出length-1的低位全部都是1，这样在进行hash&(length-1)操作的时候，只要hash对应的最左边的差异位为0，能够保证所有的位置都可能被用到，例如如果长度是15，那么length-1=14，二进制为01110，与任何值进行&的时候，尾数永远都是0，就会导致0001,1001,1101等尾数为1的位置永远不可能有元素放置进去，所以设置长度为2的次幂的原因也是为了尽可能的保证所有的位置都可以被存储元素。
在put操作中，如果一个key值在数组中不存在的时候，需要往map中加入一个节点，其主要的方法是addEntry，他的主要步骤是：首先根据在table数组中的索引值拿到该位置上的链表e，新建一个Entry，使其的key和value是新加入的元素，next是e，也就是将新加入的值作为链表的表头放到table对应的位置上。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size >= threshold)
resize(2 * table.length);
}
在HashMap中每插入一个新的元素之后，这里新的是指key在map中之前是不存在的，都需要对table数组的容量进行检查，判断是否需要扩容，当当前map中的元素的个数超过设置的阈值时threshold时，调用resize方法，其中传递的参数是当前数组的长度的2倍。
在使用resize的过程中，首先要判断当前数组的容量是否已经是最大值，如果是最大值，直接将阈值设置为Integer的最大值，然后返回，也就是不对数组进行扩容了。
否则，创建一个新的数组newTable，他的容量时当前数组容量的2倍，然后调用transfer方法，将旧数组中的元素复制到新的数组中，返回新的数组，每次的扩容操作都是将数组翻倍，然后对每一个元素重新计算位置，因此扩容操作是一个耗费时间和资源的操作。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
接下来看一下transfer方法，他是对老的数组进行遍历，取出table中每一个索引位置上的链表，然后对链表进行遍历，取出链表中的每一个Entry，根据其中的hash值和新的数组的length重新计算新的索引位置，然后将元素插入新的链表中，这一步会使得原有数组中的所有元素的位置被重新计算。
//复制老的键值对到新的数组中
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j ) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
5.HashMap的get操作
HashMap的get操作相比put操作就简单很多，首先是判断key值是否为null，如果是null，则直接调用getForNummKey()方法去table[0]的位置查找元素，拿到table[0]处的链表进行遍历，这里只需要判断链表中的key值是否是null，返回对应的value值。
如果key值不是null，则需要对key.hashCode再次计算hash值，调用indexFor方法拿到在table中的索引位置，获取到对应的链表。拿到链表后，需要对链表进行遍历，判断hashCode值是否相等以及key值是否相等，共同判断key值是否在HashMap中存在，从而拿到对应的value值。在这里也就说明了为什么把一个对象放入到HashMap的时候，最好是重写hashCode()方法和equals方法，hashCode()可以确定元素在数组中的位置，而equals方法在链表比较的时候会用到。
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
四、HashMap的多线程不安全的体现
1.resize扩容时死循环
在扩容操作是，是对链表进行循环操作，如果同时有两个线程在对同一个链表进行transfer操作，线程A在transfer的时候会修改为value2.next=value1, 线程B操作时，根据原始链表拿到的是value1.next=value2，而由于线程A已经修改为value2.next=value1,那么就会存在死循环的问题。
2.数据不一致
当一个线程在对HashMap进行resize操作，而另一个线程在进行get操作时，比如原始数组长度时16，扩容之后是32，在进行get操作根据扩容之前的length拿到index1，而这个时候另一个线程正好对index1的链表做好扩容操作，那么从index1的位置取出来的元素肯定是null，这时候可以使用ConcurrentHashMap（ConcurrentHashMap在之后再讲）
五、HashMap总结
1.HashMap是由数组和链表组成的，数组是HashMap的主体，链表是为了解决哈希冲突的问题，对于HashMap的插入问题，如果插入位置不含有链表，那么直接插入到链表的表头即可，如果包含链表，需要先遍历链表，判断key是否已经在链表中存在，存在则替换value值，不存在则插入到链表的表头。
2.HashMap中是根据hashCode和equals方法来决定存放的位置，因此不允许一个map将自己作为key值，但是可以将自己作为value值。
3.HashMap是线程不安全的，对于多线程环境下，无法保证数据的正确性，使用的时候需要注意。
4.如果在使用时能评估到HashMap中元素的个数，建议指定初始化容量的大小，在HashMap中默认容量时16，在插入元素的时候，会对元素进行检查是否需要扩容，每次扩容就是新建一个原来2倍容量的数组，对原有的元素全部重新哈希，因此如果不断插入元素，那么会需要不断的扩容，不断的哈希，这时候产生的内存开销和cpu开销在某些情况下可能是致命的。
