一、HashMap概述
HashMap是基于哈希表的Map接口实现的,此实现提供所有可选的映射操作。存储的是<key，value>对的映射，允许多个null值和一个null键。但此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
除了HashMap是非同步以及允许使用null外，HashMap 类与 Hashtable大致相同。
此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
注意，此实现不是同步的。 如果多个线程同时访问一个HashMap实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。这通常是通过同步那些用来封装列表的 对象来实现的。但如果没有这样的对象存在，则应该使用{@link Collections#synchronizedMap Collections.synchronizedMap}来进行“包装”，该方法最好是在创建时完成，为了避免对映射进行意外的非同步操作。
Map m = Collections.synchronizedMap(new HashMap(...));
二、HashMap的数据结构
HashMap实际上是一个“链表的数组”的数据结构，每个元素存放链表头结点的数组，即数组和链表的结合体。
从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表，链表中的每个元素为一个包含可以值，key哈希码，value值的Node节点。该数组的下标索引为key的哈希码。
三、HashMap源码解析1.映射项Node<K,V>结构
//实现Map.Entry<K,V>接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //hash码
final K key;
V value;
Node<K,V> next; //指向链表中下一个实例
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//返回此映射项的哈希值:key值的哈希码与value值的哈希码按位异或的结果
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//用指定值替换对应于此项的值,并返回旧值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//比较指定对象与此项的相等性
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2. HashMap类结构
//通过HahMap实现的接口可知，其支持所有映射操作，能被克隆，支持序列化
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
//默认初始容量16，必须为2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//table是一个Node<K,V>[]数组类型，而Node<K,V>实际上就是一个元素值为<key,value>对的单向链表。
//哈希表的"key-value键值对"都是存储在Node<K,V>数组中的。
transient Node<K,V>[] table;
//用来指向entrySet()返回的set集合
transient Set<Map.Entry<K,V>> entrySet;
//HashMap的大小,即保存的键值对的数量
transient int size;
//用来实现fail-fast机制的，记录HashMap结构化修改的次数
transient int modCount;
//下次需扩容的临界值，size>=threshold就会扩容
//如果table数组没有被分配，则该值为初始容量值16；或若该值为0，也表明该值为初始容量值
int threshold;
//加载因子
final float loadFactor;
......
}
HashMap包含了几个重要的成员变量：table, size, threshold, loadFactor。
(01) table是一个Node[]数组类型，而Node实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Node数组中的。
(02) size是HashMap的大小，它是HashMap保存的键值对的数量。
(03) threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时（size>=threshold），就需要将HashMap的容量加倍。
(04) loadFactor就是加载因子。
注意：HashMap的数据结构和冲突处理方法？
通过HashMap数据存储数组Node<K,V>[] table，及数据节点Node<K,V>的数据结构可知：HashMap是实现"key-value键值对"的映射关系的，是通过“拉链法”解决哈希冲突的。简单的构造图如下所示：
3. 构造函数
HashMap提供了四种方式的构造器，可以构造一个带指定初始容量和加载因子的空HashMap，构造一个带指定初始容量和默认加载因子(0.75)的空 HashMap，构造一个默认初始容量为16和默认加载因子为0.75的空HashMap，以及构造一个包含指定Map的元素的HashMap，容量与指定Map容量相同，加载因子为默认的0.75。
//找出“大于Capacity”的最小的2的幂,使Hash表的容量保持为2的次方倍
//算法的思想：通过使用逻辑运算来替代取余，这里有一个规律，就是当N为2的次方（Power of two），那么X％N==X&(N-1)。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; //>>> 无符号右移,高位补0
n |= n >>> 2; //a|=b的意思就是把a和b按位或然后赋值给a
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//构造一个带指定初始容量和加载因子的空HashMap
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//构造一个带指定初始容量和默认加载因子(0.75)的空 HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造一个具有默认初始容量 (16)和默认加载因子 (0.75)的空 HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造一个映射关系与指定 Map相同的新 HashMap,容量与指定Map容量相同，加载因子为默认的0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4.resize()方法
在HashMap的四种构造函数中并没有对其成员变量Node<K,V>[] table进行任何初始化的工作，那么HashMap是如何构造一个默认初始容量为16的空表的？该初始化的诱发条件是在向HashMap中添加第一对<key,value>时，通过put(K key, V value) -> putVal(hash(key), key, value, false, true) -> resize()方法。故HashMap中尤其重要的resize()方法主要实现了两个功能：
1.在table数组为null时，对其进行初始化，默认容量为16；
2.当tables数组非空，但需要调整HashMap的容量时，将hash表容量翻倍。
//resize()方法作用有两种：1.初始化hash表的容量，为16； 2.将hash表容量翻倍
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //旧hash表
int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧hash表容量
int oldThr = threshold; //旧hash表阈值
int newCap, newThr = 0; //新hash表容量与扩容临界值
//2.旧hash表非空，则表容量翻倍
if (oldCap > 0) {
//如果当前的hash表长度已经达到最大值，则不在进行调整
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} //更新新hash表容量：翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//更新扩容临界值
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//1. 初始化hash表容量，设为默认值16
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建一个初始容量为新hash表长度的newTab数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果旧hash表非空，则按序将旧hash表中的元素重定向到新hash表
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e; //e按序指向oldTab数组中的元素，即每个链表中的头结点
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //如果链表只有一个头节点
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//对链表进行秩序维护：因为我们使用的是两倍扩容的方法，所以每个桶里面的元素必须要么待在原来的
//索引所对应的位置，要么在新的桶中位置偏移两倍
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
5.查找
HashMap提供了get(Object key)、containsKey(Object key)、containsValue(Object value)这些查找键值对的方法。
//返回指定key所映射的value；如果对于该键来说，此映射不包含任何映射关系，则返回 null
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { //key的哈希值为数组下标
if (first.hash == hash && //检查第一个节点
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果第一个节点不对，则向后检查
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
//如果此映射包含对于指定键的映射关系，则返回 true。
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
//如果此映射将一个或多个键映射到指定值，则返回 true。
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//外层循环搜索数组
for (int i = 0; i < tab.length; ++i) {
//内层循环搜索链表
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
6.添加
HashMap提供了put(K key, V value)、putAll(Map<? extends K, ? extends V> m)这些添加键值对的方法。
/**
* 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换。
*
* @param key 指定值将要关联的键
* @param value 指定键将要关联的值
* @return 与 key关联的旧值；如果 key没有任何映射关系，则返回 null。（返回 null 还可能表示该映射之前将null与 key关联。）
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 用于实现 Map.put()和相关的方法
*
* @param hash 键的hash码
* @param key 键
* @param value 值
* @param onlyIfAbsent if true, don't change existing value
* @param evict evict=false：表明该hash表处于初始化创建的过程中
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//此处分两种情况：1.当table为null时，用默认容量16初始化table数组；2.当table非空时
if ((tab = table) == null || (n = tab.length) == 0) //旧hash表为null或旧hash表长度为0
n = (tab = resize()).length; //初始化hash表的长度（16）
//此处又分为两种情况：1.key的hash值对应的那个节点为空；2.key的hash值对应的那个节点不为空
if ((p = tab[i = (n - 1) & hash]) == null) //该key的hash值对应的那个节点为空，即表示还没有元素被散列至此
tab[i] = newNode(hash, key, value, null); //则创建一个新的new Node<>(hash, key, value, next);
else {
//该key的hash值对应的那个节点不为空，先与链表上的第一个节点p比较
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //向后查找
}
}
//若该key对应的value已经存在，则用新的value取代旧的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //如果加入该键值对后超过最大阀值，则进行resize操作
resize();
afterNodeInsertion(evict);
return null;
}
//将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
//用于帮助实现Map.putAll()方法 和Map构造器，当evict=false时表示构造初始HashMap。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size(); //得到指定Map的大小
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY); //得到按指定Map大小计算出的HashMap所需的容量
if (t > threshold) //如果容量大于阈值
threshold = tableSizeFor(t);
}
else if (s > threshold) //指定Map的大小>扩容临界值,扩容
resize();
//通过迭代器，将“m”中的元素逐个添加到HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
7.清空与删除
HashMap提供了remove(Object key)删除键值对、clear()清除所有键值对的方法。
//从此映射中移除指定键的映射关系（如果存在）
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 用于实现 Map.remove()方法和其他相关的方法
*
* @param hash 键的hash值
* @param key 键
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//table数组非空，键的hash值所指向的数组中的元素非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v; //node指向最终的结果结点，e为链表中的遍历指针
if (p.hash == hash && //检查第一个节点，如果匹配成功
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//如果第一个节点匹配不成功，则向后遍历链表查找
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //删除node结点
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
//从此映射中移除所有映射关系
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
8.其他公开的方法
size()、isEmpty()、clone()
//返回此映射中的键-值映射关系数
public int size() {
return size;
}
//如果此映射不包含键-值映射关系，则返回 true
public boolean isEmpty() {
return size == 0;
}
//返回此 HashMap 实例的浅表副本
public Object clone() {
HashMap<K,V> result;
try {
result = (HashMap<K,V>)super.clone(); //调用父类clone方法
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize();
result.putMapEntries(this, false); //将此HashMap元素放入result中
return result;
}
支持序列化的写入函数writeObject(java.io.ObjectOutputStream s)和读取函数readObject(java.io.ObjectInputStream s)：
//java.io.Serializable的写入函数,将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
//java.io.Serializable的读取函数：根据写入方式读出,将HashMap的“总的容量，实际容量，所有的Entry”依次读出
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
s.readInt(); // Read and ignore number of buckets
int mappings = s.readInt(); // Read number of mappings (size)
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
// Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
四、HashMap的键集、值集和键值对集
HashMap是一个很有用的集合框架，通过下述三个方法可以分别得到HashMap的键集、值集和键值对集。
键集：Set<K> keySet()
值集：Collection<K> values()
键值对集：Set<Map.Entry<K,V>> entrySet()
得到这三种collection 视图后，可以使用Iterator迭代器进行遍历。
五、总结：
1、4中创建构造函数的方式，但是创建过程中没有对table[]的容量进行初始化工作，这个初始化工作是在put()--putAll()--resize()方法中进行的；
2、resize()方法：首先判断原table[]是否为空，如果为空，容量值就置为默认的初始容量16，否则为原先的两倍，然后遍历原先table[]数组的，头节点是链表还是红黑树，以后将原先的元素放置新的table[]中去；
3、查询：查询主要根据key获得value，这个是先检查第一个节点是否是要查询的key，不是就往后进行查询；判断是否包含指定的key，使用getNode方法；判断是否包含的value，嵌套查询；
4、新增：
（1）、新增k-v键值对：首先判断table[]数组是否初始化过或者长度是否为0，若是，那么初始化table[]数组，长度为16，若不是，判断传入的key值的hash值是否已经存在节点，如果没有则新建一个节点，若已存在，查看第一个节点处理hash冲突的方式，分为链表或者红黑树，红黑树调用树的插入方法，链表则判断这个链表中的key是否存在传入的key，若不存在则插入到末端，若存在则用新值替换掉旧值；
对key的hashCode()做hash，然后再计算index;
如果没碰撞直接放到bucket里；
如果碰撞了，以链表的形式存在buckets后；
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
如果节点已经存在就替换oldvalue(保证key的唯一性)
如果bucket满了(超过loadfactor*current capacity)，就要resize。
（2）、新增map：首先判断table[]是否为null，若为null，先计算hashmap的容量，然后和阈值对比，大于则重新赋值，若不为null，若size大于阈值，则进行扩容，然后遍历map，将key-v键值对使用putval方法插入。
5、通过h &(table.length -1)来得到该对象的保存位及数组的index，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
6、删除：
（1）、删除Node,首先判断table[]是否为空，不为空，找到该key存放的table数组的位置，然后和第一个节点进行比较，hash和key都一致则删除该节点，如果不同，那么往后遍历查询，获取对应的节点，最后删除节点；
（2）、clear方法将table[]置为Null
7、我们现在可以回答开始的几个问题，加深对HashMap的理解：
（1）、什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
（2）、你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
（3）、你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
（4）、你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
（5）、如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
关于Java集合的小抄中是这样描述的：
以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶(比如哈希值1和17取模16后都属于第一个哈希桶)，Entry用一个next属性实现多个Entry以单向链表存放，后入桶的Entry将next指向桶当前的Entry。
查找哈希值为17的key时，先定位到第一个哈希桶，然后以链表遍历桶里所有元素，逐个比较其key值。
当Entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%，但看代码不是)，会成倍扩容桶数组，并重新分配所有原来的Entry，所以这里也最好有个预估值。
取模用位运算(hash & (arrayLength-1))会比较快，所以数组的大小永远是2的N次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator()时顺着哈希桶数组来遍历，看起来是个乱序。
（6）、当两个对象的hashcode相同会发生什么？
因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
（7）、如果两个键的hashcode相同，你如何获取值对象？
找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。因此，设计HashMap的key类型时，如果使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择
（8）、如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置
（9）、你了解重新调整HashMap大小存在什么问题吗？
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。因此在并发环境下，我们使用CurrentHashMap来替代HashMap
（10）、为什么String, Interger这样的wrapper类适合作为键？
因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能
（11）、为什么桶的数组大小始终是2的幂次方呢？
因为hashmap在进行相关操作时，比如Put的时候，首先会根据key值调用hashCode方法，找到对应的在桶中的保存位置及数组index，采用hash & (arrayLength-1)来算得Index的值，发现为2的幂次方出现相同的值的可能性比较少，也就减小了碰撞的机率，那么元素存放就是比较均匀了，如果元素没有大于桶数和负载因子乘积大小时，这是每个位置就只会存放一个元素，那么查询等操作的时候就没必要变量单链表，这样很好的提高了性能。
（12）、resize最大的性能消耗在哪？
最大的消耗是在将旧的table[]中的元素放置新的table[]中，需要变量原先数组的所有数据，通过计算确认在新数组中位置。