HashMap简介：
HashMap在日常的开发中应用的非常之广泛，它是基于Hash表，实现了Map接口，以键值对(key-value)形式进行数据存储，HashMap在数据结构上使用的是数组+链表。允许null键和null值，不保证键值对的顺序。
HashMap检索数据的大致流程：
当我们使用HashMap搜索key所对应的value时，HashMap会根据Hash算法对key进行计算，得到一个key的hash值，再根据hash值算出该key在数组中存储的位置index，然后获取数组在index位置的键值对e,再使用链表对e进行遍历，查找遍历的元素是否和给定的key相符合，若有符合的，则返回其value值。
自己手动画了一个HashMap的数据结构图：
HashMap源码分析：
HashMap是存储键值对的集合，实现了Map接口,下面我们看一下Map接口的定义：
/**
*映射key到value的*接口，不能包含重复的key，一个key最多可以映射到一个value,键和值均可为null
*/
public interface Map<K,V> { //返回该map包含的键值对的个数，如果键值对的个数超过了Integer.MAX_VALUE,则返会Integer.MAX_VALUE
int size(); //如果该Map没有包含键值对，则返回true，否则返回false
boolean isEmpty(); //判断该map是否包含指定的key所对应的键值对，key可以为null
boolean containsKey(Object key); //判断该map是否包含指定的value所对应的键值对,若map中包含有一个及以上的key,对应指定的value,则返回true，value可以为null
boolean containsValue(Object value); //返回指定的key所对应的value，若key不存在，则返回null;但是返回null的key,不代表key在map中不存在，有可能是key所对应的value为null
V get(Object key); //将指定的key和value映射为一个键值对，放入map中；若之前该map中包含了指定的Key,则该key所对应的老的值oldValue将会被替换为value
V put(K key, V value); //删除指定的key所对应的键值对，并返回该key对应的value
V remove(Object key); //将指定的map中的键值对复制到当前map中
void putAll(Map<? extends K, ? extends V> m); //清除map中所有的键值对，该操作完成后，该map就是空的了
void clear(); //将map中所有的key返回，由于map中的key是不能重复的，所以用Set集合的方式装载所有的key
Set<K> keySet(); //将map中所有的value返回，由于map中的value是可重复的，所以用Collection集合的方式装载所有的value
Collection<V> values(); //将map中所有的键值对Entry返回，由于map中的键值对是不可重复的（key不可重复），所以用Set集合的方式装载所有的value
Set<Map.Entry<K, V>> entrySet(); //Map中承载键值对的数据结构Entry
interface Entry<K,V> { //返回键值对的键值key
K getKey(); //返回键值对的value值
V getValue(); //将当前键值对的value值 替换为指定的value值
V setValue(V value); //判断指定的对象和当前键值对是否equals相等，若相等，则代表是同一个键值对；
boolean equals(Object o); //返回当前键值对的hashCode值
int hashCode();
} //判断指定对象和当前Map的equals是否相等
boolean equals(Object o); //返回当前Map的hashCode
int hashCode();
}
下面我们具体的看一下HashMap：
//HashMap是基于hash表来实现Map接口的，HashMap维护了下面几个变量：
//HashMap默认的初始化大小为16
static final int DEFAULT_INITIAL_CAPACITY = 16;
//HashMap包含键值对的最大容量为2^30,HashMap的容量一定要是2的整数次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//装载键值对的内部容器Entry数组，长度一定得是2的幂
transient Entry[] table;
//HashMap中包含的键值对的个数
transient int size;
//HashMap的极限 当键值对的个数达到threshold时，数组table要扩容的
int threshold;
//加载因子
final float loadFactor;
//HashMap结构上被改变的次数，结构上的改变包括：键值对的大小的改变，修改HashMap的内部结构（比较进行了rehash操作），此属性用来保持fail-fast
transient volatile int modCount;
接下来我们看一下HashMap的构造函数：
/**
*根据指定的容量initialCapacity和加载因子loadFactor构造HashMap
*/
public HashMap(int initialCapacity, float loadFactor) {
//对initialCapacity进行参数校验，若小于0，则抛出IllegalArgumentException异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//若initialCapacity大于MAXIMUM_CAPACITY(2^30),则将MAXIMUM_CAPACITY赋值给initialCapacity
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//对参数loadFactor进行有效性校验，不能<=0,不能非数字，否则抛出IllegalArgumentException异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor); // Find a power of 2 >= initialCapacity 找到一个2的幂的数capacity，使其不小于参数initialCapacity
int capacity = 1;
//若capacity小于initialCapacity,则将capacity扩大一倍
while (capacity < initialCapacity)
capacity <<= 1; this.loadFactor = loadFactor;
//设置极限，大小为 capacity * loadFactor,即(容量*负载因子)
threshold = (int)(capacity * loadFactor);
//创建一个大小为capacity的Entry数组table,用来保存键值对
table = new Entry[capacity];
//调用方法init(),进行额外的初始化操作
init();
}
//init方法是空的，如果你定制额外的初始化操作，可以继承HashMap，覆盖init()方法
void init() { } //通过指定的容量initialCapacity来构造HashMap，这里使用了默认的加载因子DEFAULT_LOAD_FACTOR 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} //无参的构造函数 加载因子为DEFAULT_LOAD_FACTOR 0.75，容量为默认的DEFAULT_INITIAL_CAPACITY 16，极限为 16*0.75=12
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
下面我们看一下HashMap中承载键值对的数据结构Entry的实现,Entry<K,V>是HashMap的一个静态内部类
/**
*Entry是HashMap里面承载键值对数据的数据结构，实现了Map接口里面的Entry接口，除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外，其他方法均为final方法，表示即使是子类也不能覆写这些方法。
*/
static class Entry<K,V> implements Map.Entry<K,V> {
//键值,被final修饰，表明一旦赋值，不可修改
final K key;
//value值
V value;
//下一个键值对的引用
Entry<K,V> next;
//当前键值对中键值的hash值
final int hash; /**
* Creates new entry.
*/
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;
} //设置value值，返回原来的value值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//比较键值对是否equals相等，只有键、值都相等的情况下，才equals相等
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
//若k1 == k2(k1,k2引用同一个对象),或者k1.equals(k2)为true时，进而判断value值是否相等
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
//若v1 == v2(v1,v2引用同一个对象),或者v1.equals(v2)为true时，此时才能说当前的键值对和指定的的对象equals相等
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
//其他均为false
return false;
} public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
} public final String toString() {
return getKey() + "=" + getValue();
} //此方法只有在key已存在的时候调用m.put(key,value)方法时，才会被调用，即覆盖原来key所对应的value值时被调用
void recordAccess(HashMap<K,V> m) {
}
//此方法在当前键值对被remove时调用
void recordRemoval(HashMap<K,V> m) {
}
}
下面是Hash的put方法的实现：
/**
*将指定的键key,值value放到HashMap中
*/
public V put(K key, V value) {
//首先判断键key是否为null,若为null,则调用putForNullKey(V v)方法完成put
if (key == null)
return putForNullKey(value);
//程序走到这，说明key不为null了，先调用hash(int)方法，计算key.hashCode的hash值
int hash = hash(key.hashCode());
//再调用indexFor(int,int)方法求出此hash值对应在table数组的哪个下标i上 (bucket桶)
int i = indexFor(hash, table.length);
//遍历bucket桶上面的链表元素，找出HashMap中是否有相同的key存在，若存在，则替换其value值，返回原来的value值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//若元素e.hash值和上面计算的hash值相等，并且(e.key == 入参key,或者入参key equals 相等 e.key)，则说明HashMap中存在了和入参相同的key了，执行替换操作
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//在执行替换操作的时候，调用Entry对象的recordAccess(HashMap<K,V> m)方法，这个上面说过了
e.recordAccess(this);
return oldValue;
}
}
//程序走到这，说明原来HashMap中不存在key,则直接将键值对插入即可，由于插入元素，修改了HashMap的结构，因此将modeCount+1
modCount++;
//调用addEntry(int,K,V,int)方法进行键值对的插入
addEntry(hash, key, value, i);
//由于原来HashMap中不存在key，则不存在替换value值问题，因此返回null
return null;
}
当key为null时，HashMap是这样进行数据插入的：
//先看看HashMap中原先是否有key为null的键值对存在，若存在，则替换原来的value值；若不存在，则将key为null的键值对插入到Entry数组的第一个位置table[0]
private V putForNullKey(V value) {
//获取Entry数组的第一个元素:table[0],然后通过e.next进行链表的遍历，若遍历过程中有元素e.key为null,则替换该元素的值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//说明原来之前HashMap中就已经存在key问null的键值对了，现在又插入了一个key为null的新元素，则替换掉原来的key为null的value值
if (e.key == null) {
V oldValue = e.value;
e.value = value;
//在执行替换操作的时候，调用Entry对象的recordAccess(HashMap<K,V> m)方法，这个上面说过了
e.recordAccess(this);
return oldValue;
}
}
//程序走到这，说明HashMap中原来没有key为null的键值对，需要直接插入元素，由于插入元素，修改了HashMap的结构，因此将modeCount+1
modCount++;
//调用addEntry(int,K,V,int)方法进行键值对的插入,这里将入参hash设置为0，K为null,插入的位置index也为0，说明key为null的元素插入在bucket[0]第一个桶上
addEntry(0, null, value, 0);
return null;
}
HashMap在插入数据之前，要根据key值和hash算法来计算key所对应的hash值
//根据key的hashCode值，来计算key的hash值
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
*在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置,如何计算这个位置就是hash算法.
*HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个,
*那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表.
*所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的,但是，“模”运算的消耗还是比较大的，
*能不能找一种更快速，消耗更小的方式那？java中时这样做的 :将hash值和数组长度按照位与&来运算
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
下面我们看一看实际进行数据添加的操作addEntry方法
/**
*将指定的key,value,hash,bucketIndex 插入键值对，若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//取出原来bucketIndex处的键值对e
Entry<K,V> e = table[bucketIndex];
//创建一个新的键值对，使用给定的hash、key、value,并将新键值对的next属性指向e,最后将新键值对放在bucketIndex处
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//将size+1,若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍
if (size++ >= threshold)
//调用resize(int)方法，进行数组的扩容
resize(2 * table.length);
}
我们知道HashMap采用的数组+链表来实现的，当HashMap中元素的个数size大于极限threshold时，会进行数组的扩容操作，这个操作使用resize(int newCapacity)方法实现的：
/**
*将HashMap中Entry数组table的容量扩容至新容量newCapacity,数组的扩容不但涉及到数组元素的复制，还要将原数组中的元素rehash到新的数组中，很耗时;如果能预估到放入HashMap中元素的大小，最好使用new HashMap(size)方式创建足够容量的HashMap，避免不必要的数组扩容(rehash操作)，提高效率
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果原数组的大小已经为允许的最大值MAXIMUM_CAPACITY了，则不能进行扩容了，这里仅仅将极限threshold设置为Integer.MAX_VALUE，然后返回
if (oldCapacity == MAXIMUM_CAPACITY) {
//将极限threshold设置为Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return;
}
//程序走到这，说明可以进行扩容，先创建容量为newCapacity的新Entry数组newTable
Entry[] newTable = new Entry[newCapacity];
//调用tranfer(Entry[] newTable)方法，进行数组元素的移动和rehashing
transfer(newTable);
//将新数组newTable赋值给table
table = newTable;
//计算极限threshold的最新值
threshold = (int)(newCapacity * loadFactor);
} //将原Entry数组table中的所有键值对迁移到新Entry数组newTable上
void transfer(Entry[] newTable) {
//原数组赋值给src
Entry[] src = table;
//新数组长度为newCapacity
int newCapacity = newTable.length;
//遍历原数组
for (int j = 0; j < src.length; j++) {
//获取原数组中的元素(键值对),赋值给e
Entry<K,V> e = src[j];
//若元素e不为null
if (e != null) {
//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
src[j] = null;
//遍历元素e所对应的bucket桶内的所有元素
do {
//获取下一个元素next
Entry<K,V> next = e.next;
//重新计算键值对e在新数组newTable中的bucketIndex位置(即rehash操作)
int i = indexFor(e.hash, newCapacity);
//标记[1]
e.next = newTable[i];
//将当前元素e放入新数组的i位置
newTable[i] = e;
//访问下一个Entry链上的元素
e = next;
} while (e != null);
}
}
}
注释标记[1]处，将newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话)；
若某个桶上面的元素不止一个，则会行成一个链表，在resize过程中，会导致链表逆序排列。比如在第i个桶内，有元素tab[i1]=a -> tab[i2]=b -> tab[i3]=c -> tab[i4]=d,
在resize后，比如会放到新的数组下标j处，则新的链表为newTab[j1]=d -> newTab[j2]=c -> newTab[j3]=b -> newTab[j4]=a
下面我们看一下HashMap检索数据的操作：
//获取指定key所对应的value值
public V get(Object key) {
//若key==null,则直接调用getForNullKey()方法
if (key == null)
return getForNullKey();
//到这说明key != null,先获取key的hash值
int hash = hash(key.hashCode());
//在indexFor(int hash,int length)获取key落在Entry数组的哪个bucket桶上，获取该bucket桶上的元素e,进而遍历e的链表，找相对应的key,若找到则返回key所对应的value值，找不到则返回null
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//若元素e.hash == 上面计算的hash值，并且(e.key 和入参key是同一个对象的引用，或者e.key和入参key equals相等)，
//则认为入参key和当前遍历的元素e的key是同一个,返回e的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
//上面遍历了一遍也没有找到，则返回null
return null;
} //获取key为null的value值，由上面putForNullKey方法可知，key为null的键值对，被放在了Entry数组table的第一个bucket桶(table[0])
private V getForNullKey() {
//获取Entry数组table的第一个元素e,从e开始往下遍历，若找到元素e.key 为null的，则直接返回该元素e.value值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//找到元素e.key 为null的，则直接返回该元素e.value值
if (e.key == null)
return e.value;
}
//从table[0]开始，遍历链表一遍，没有找到key为null的，则返回null
return null;
} //获取指定key所对应的键值对Entry,先获取key的hash值，再获取该hash值应放入哪个hash桶，然后遍历该桶中的键值对，若有则返回该键值对；若没有则返回null
final Entry<K,V> getEntry(Object key) {
//若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值
int hash = (key == null) ? 0 : hash(key.hashCode());
//获取该hash值应放入哪个hash桶,并遍历该hash桶
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//若元素e.hash == hash,并且(e.key == key，或者 key.equals(e.key)为true)，则认为入参key和当前遍历的元素e.key是同一个，返回该元素e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
//若没有则返回null
return null;
}
//判断HashMap中是否含有指定key的键值对，内部用getEntry(Object key)来实现
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//将指定Map中的所有元素(键值对)拷贝到当前HashMap中，对于当前HashMap中存在的key,则进行value值的替换
public void putAll(Map<? extends K, ? extends V> m) {
//若指定的Map中没有元素，则直接返回
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return; //若必要，则进行数组的扩容
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
//计算新的容量
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
//若新容量大于目前数组的长度，则调用resize(int)进行扩容
if (newCapacity > table.length)
resize(newCapacity);
}
//获取指定Map的迭代器，循环调用put(K k,V v)方法，进行键值对的插入
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<? extends K, ? extends V> e = i.next();
put(e.getKey(), e.getValue());
}
}
下面看下HashMap的remove操作：
/**
* 删除指定key所对应的元素
*/
public V remove(Object key) {
//调用方法reomveEntryForKey(Object key)来删除并获取指定的entry
Entry<K,V> e = removeEntryForKey(key);
//若entry为null，则返回null；否则返回entry的value值
return (e == null ? null : e.value);
} /**
*移除并返回指定key所关联的键值对entry,若HashMap中没有键值对和指定的key相关联，则返回null
*/
final Entry<K,V> removeEntryForKey(Object key) {
//若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值
int hash = (key == null) ? 0 : hash(key.hashCode());
//获取key应放入的在数组中的位置索引i
int i = indexFor(hash, table.length);
//标识前一个元素
Entry<K,V> prev = table[i];
//标识遍历过程中的当前元素
Entry<K,V> e = prev;
//遍历bucket桶table[i]中的元素，寻找对应的key
while (e != null) {
//当前元素的下一个元素
Entry<K,V> next = e.next;
Object k;
//元素e.hash和上面计算的hash值相等，并且(key == e.key 或者key.equals(e.key) 为true)，说明找到了指定key所对应的键值对
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//由于删除了一个元素，修改了HashMap的结构，因此将modCount+1
modCount++;
//将size-1
size--;
//若待查找的元素为桶内的第一个元素，则当前元素的下一个元素next放入数组中位置i中
if (prev == e)
table[i] = next;
//否则将上一个元素的next属性指向 当前元素的next
else
prev.next = next;
//当元素被remove时，调用Entry对象的recordRemove(Map<K,V> m)方法
e.recordRemoval(this);
//返回找到的当前元素
return e;
}
//程序走到这，说明当前元素不是要查找的元素；则将当前元素赋值给上一个元素，将下一个元素赋值给当前元素，以完成遍历
prev = e;
e = next;
} return e;
}
//判断HashMap中是否包含指定的对象value
public boolean containsValue(Object value) {
//若value为null，则调用containsNullValue()方法处理
if (value == null)
return containsNullValue();
//将数组table赋值给tab
Entry[] tab = table;
//遍历数组tab的每个索引位置(此层循环对应数组结构)
for (int i = 0; i < tab.length ; i++)
//对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)
for (Entry e = tab[i] ; e != null ; e = e.next)
//若某个元素e.value和指定的value equals相等，则返回true
if (value.equals(e.value))
return true;
//遍历完成没有找到对应的value值，返回false
return false;
} //判断HashMap是否包含value为null的元素
private boolean containsNullValue() {
//将数组table赋值给tab
Entry[] tab = table;
//遍历数组tab的每个索引位置(此层循环对应数组结构)
for (int i = 0; i < tab.length ; i++)
//对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)
for (Entry e = tab[i] ; e != null ; e = e.next)
//若某个元素e.value == null，则返回true
if (e.value == null)
return true;
//没有找到value值为null的，返回false
return false;
}
//清除HashMap中所有的键值对，此操作过后，HashMap就是空的了
public void clear() {
//要删除所有的元素，肯定会对HashMap的结构造成改变，因此modCount+1
modCount++;
Entry[] tab = table;
//遍历数组，将数组中每个索引位置的设置为null
for (int i = 0; i < tab.length; i++)
tab[i] = null;
//将size 修改为0
size = 0;
}
现在看一下上面没有讲的一个构造函数:
//构造一个新的HashMap，以承载指定Map中所有的键值对，使用默认的加载因子DEFAULT_LOAD_FACTOR
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(Map<? extends K, ? extends V>)方法完成元素的迁移
putAllForCreate(m);
} private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<? extends K, ? extends V> e = i.next();
//在迭代器循环中调用putForCreate(K k,V v)来实现元素的创建
putForCreate(e.getKey(), e.getValue());
}
} //该方法和put方法不同，它不会进行数组的扩容resize,和对modCount的检查
private void putForCreate(K key, V value) {
//若key为null,则hash值为0；若key != null,则利用hash(int)计算key的hash值
int hash = (key == null) ? 0 : hash(key.hashCode());
//求key应该放入哪个hash桶(bucket)内
int i = indexFor(hash, table.length);
//遍历链表，若key之前在Map中已经有了，则直接返回
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//调用createEntry(int hash,K k,V v,int bucketIndex)方法完成键值对的创建并加入到链表中
createEntry(hash, key, value, i);
} void createEntry(int hash, K key, V value, int bucketIndex) {
//将bucketIndex位置的元素取出来
Entry<K,V> e = table[bucketIndex];
//创建一个新的键值对，使用给定的hash、key、value,并将新键值对next指向e,最后将新键值对放在bucketIndex处
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//将数组大小size + 1
size++;
}
下面我们讲下HashMap的负载因子loadfactor, 所谓负载因子就是散列表的实际元素数目(n)/散列表的容量(m), 它衡量的是一个散列表的空间的使用程度，默认情况下loadfactor是0.75，它的作用是当HashMap中元素的个数size 大于(HashMap的容量capacity * 负载因子loadfactor)时，该HashMap便会进行扩容resize。
我们先说下hash冲突：
当利用HashMap存数据的时候，先根据key的hashcode值来计算key的hash值(利用hash函数)，再根据hash值来计算该key在数组table中的位置index（hash & (length-1)）,比如我们要存两个键值对key1-value1和key2-value2,
如果key1、key2分别通过hash函数计算的hash值hash1、hash值hash2 相等，那key1和key2一定会落在数组table的同一个位置上，这就产生了冲突，这个冲突是由不同的key值但是却相同的hash值引起的，称之为hash冲突。HashMap解决hash冲突的方式就是链表，虽然key1-value1和key2-value2这两个键值对落在了数组table的同一个位置上，但是它们是链表的方式连接在一起，当HashMap查找key1时，就需要遍历这个链表了。
当负载因子越大的时候，出现hash冲突的可能性越大，这意味着数组table中某个具体的桶bucket上不止有一个元素（此时就构成了链表了）可能性增大，在检索数据的时候需要遍历链表的可能性增大，因此检索的效率就比较低（耗时长），但是空间的利用率越高。
当负载因子越小的时候，出现hash冲突的可能性越小，这意味着数组table中某个具体的桶bucket上不止有一个元素（此时就构成了链表了）可能性减小了，在检索数据的数据需要遍历链表的可能性减小，因此检索的效率就比较高，但是空间利用率越低。
上面的源码解析了提到了HashMap的容量一定得是2的整数此幂(2^n),这又是问什么呢？
通过上面的源码我们知道：根据hash值求该hash值在数组中的位置的实现是： hash & (length-1)，当数组table的长度length为2的整数次幂的时候，那（length-1）二进制表示形式从低位开始一定都是1，直到为0，如果length依次为2,4,8,16,32，64，则(length-1)一次为1,3,7,15,31,63，那(length-1)的二进制形式依次为1,11,111,1111,11111，我们知道二进制的与运算&，当一方位数全是1的时候，进行&运算的结果完全取决于另外一方。
比如从0开始到15,依次和15进行&运算，看看结果的平均分布情况：
| 操作数0-15 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 15的二进制 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 | 1111 |
| 进行位与&操作结果 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
通过位与&操作后，发现0-15完全平均的落在了数组的各个索引位置
下面通过一个小例子予以验证：
public class HashDemo {
private final int[] table;
public HashDemo(int size) {
this.table = new int[size];
for (int i = 0; i < size; i++) {
table[i] = i;
}
}
//求key所对应的在数组中的位置
public int index(int key){
//求hash值
int hash = hash(key);
//返回key所对应的在数组中的位置
return hash & (table.length-1);
}
//HashMap中hash函数的实现,求hash值
public int hash(int h){
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
public static void main(String[] args) {
Map<String,Integer> keyToNumber = new HashMap<String, Integer>();
int size = 16;
HashDemo hashDemo = new HashDemo(size);
int testSize = 1000;
for (int i = 0; i < testSize; i++) {
int index = hashDemo.index(i);
Integer number = keyToNumber.get("key" + index);
if (number == null) {
keyToNumber.put("key"+index,1);
}else {
keyToNumber.put("key"+index,keyToNumber.get("key"+index)+1);
}
}
Iterator<Map.Entry<String, Integer>> it = keyToNumber.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, Integer> entry = it.next();
System.out.println(entry.getKey() + " == "+entry.getValue());
}
}
}
当我们将size设置为16 （2的4次幂）时，控制台输出：
key4 == 62
key3 == 62
key6 == 62
key5 == 62
key0 == 62
key2 == 62
key1 == 62
key10 == 63
key11 == 63
key8 == 63
key7 == 62
key9 == 63
key15 == 63
key14 == 63
key13 == 63
key12 == 63
由上面的输出可见，数据非常平均的分配在了数组的16个索引位置，
当size设置为非2的整数次幂的时候，比如50，这时控制台输出：
key0 == 120
key17 == 124
key16 == 124
key1 == 120
key49 == 128
key48 == 128
key32 == 128
key33 == 128
由此可见1000个数据只分配在了8个索引位置上。
使用HashMap的注意事项：
1.HashMap采用数组+链表的形式存储数据，当预先知道要存储在HashMap中数据量的大小时，可以使用new HashMap(int size)来指定其容量大小，避免HashMap数组扩容导致的元素复制和rehash操作带来的性能损耗。
2.HashMap是基于Hash表、实现了Map接口的，查找元素的时候，先根据key计算器hash值，进而求得key在数组中的位置，但是要尽量避免hash冲突造成的要遍历链表操作，因此在我们手动指定HashMap容量的时候，容量capacity一定得是2的整数次幂，这样可以让数据平均的分配在数组中，减小hash冲突，提高性能。
3.HashMap是非线程安全的，在多线程条件下不要使用HashMap，可以使用ConcurrentHashMap代替。