HashMap实现原理
HashMap实现原理
HashMap也是我们使用非常多的Collection，它是基于哈希表的 Map 接口的实现，以key-value的形式存在。在HashMap中，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置，我们总是可以通过key快速地存、取value。下面就来分析HashMap的存取。
定义
HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实AbstractMap类已经实现了Map。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//序列号，序列化的时候使用。
private static final long serialVersionUID = 362498820763181265L;
/**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子，用于扩容使用。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当某个桶节点数量大于8时，会转换为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
static final int UNTREEIFY_THRESHOLD = 6;
//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的数组，transient关键字表示该属性不能被序列化
transient Node<K,V>[] table;
//将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient Set<Map.Entry<K,V>> entrySet;
//元素数量
transient int size;
//统计该map修改的次数
transient int modCount;
//临界值，也就是元素数量达到临界值时，会进行扩容。
int threshold;
//也是负载因子，只不过这个是变量。
final float loadFactor;
}这里讲讲为什么默认容量大小为16，负载因子为0.75，主要原因是这两个常量的值都是经过大量的计算和统计得出来的最优解，仅仅是这样而已。
构造函数
HashMap提供了三个构造函数：
- HashMap()：构造一个具有默认初始容量 (16) 和默认负载因子 (0.75) 的空 HashMap。
public HashMap() {
// DEFAULT_LOAD_FACTOR = 0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR;
}- HashMap(int initialCapacity)：构造一个带指定初始容量和默负载因子 (0.75) 的空 HashMap。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}- HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和负载因子的空 HashMap。
初始化
调用构造方法进行初始化
/**
* 构造方法
*
* @param initialCapacity 初始容量
* @param loadFactor 扩容因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//容量参数不合理 报错
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
//初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
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);
}在这里提到了两个参数：初始容量，负载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
tableSizeFor
根据参数返回最近的2的n次幂的大小
//是返回大于输入参数且最近的2的整数次幂的数
static final int tableSizeFor(int cap) {
// 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}这种方法的效率非常高，可见Java8对容器优化了很多
内部数据结构
Node
Node是 HashMap的静态内部，HashMap主干是一个Node数组，Node是HashMap的最基本组成单位。
/**
* HashMap 的Node 节点元素
* @param <K> 元素的key
* @param <V> 元素的Value
*/
static class Node<K,V> implements Map.Entry<K,V> {
// 这个节点所在位置的hash值
final int hash;
//这个节点的Key
final K key;
//这个节点的value
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; }
/**
* 获取HashCode
* key和value 的hash做异或运算 防止hash冲突
* @return
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 设置value
* @param newValue
* @return
*/
public final V setValue(V newValue) {
V oldValue = value;
//替换当前node的value
value = newValue;
//返回旧的value
return oldValue;
}
/**
* equals 比较
* 如果 key和value都一致 判断equals相等
* @param o
* @return
*/
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;
}
}在jdk8之前HashMap是数组加链表的形式实现，但是在1.8之后为提高哈希冲突后链表的查询速度，当桶内链表长度超过树化阀值且总长度超过最小树化容量后会将链表转换为红黑树。
速度
查询与修改
先用散列函数对键进行散列，没有冲突的情况下查询是下标查询，时间复杂度是 O(1),速度很快。
存在哈希冲突的情况，需要对链表/红黑树进行遍历，equals比对查询。
性能上，考虑是链表/红黑树上的元素越是越好，越均匀越好；此外HashMap主干未必越长越好，会有用不到的桶浪费空间。
增加与删除
由于查询速度快，而桶里用链表/红黑树实现，所以添加和删除效率也很高。HashMap会在size超过阀值后进行调整大下(resize)，所以根据具体情况提前给HashMap一个合适的初始长度是个不错的习惯。
put方法
put方法是一个重点方法，这里有 HashMap初始化，数据在 HashMap中是如何储存的，什么情况下链表会转换为红黑树等内容，需要仔细研究。
/**
* put 方法
*
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
//这里继续调用putVal方法
return putVal(hash(key), key, value, false, true);
}putVal 方法
putVal是final修饰的方法，子类 LinkedHashMap也是用的这各方法，evict（看下面的的第5个参数）就是给 LinkedHashMap使用的，HashMap中并没有什么用。
/**
* putVal 方法 真正进行插入操作的方法，
*
* @param hash 传入key的哈希值
* @param key
* @param value
* @param onlyIfAbsent 如果该值是true,如果存在值就不会进行修改操作
* @param evict LinekdHashMap尾操作使用，这里暂无用途
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
/**********初始化********/
// 如果table长度是0或table是null会调整一次大小
// 这时tab会指向调整大下后的Node<K,V>[](主干数组)
// n被赋值为新数组长度
// 如果没有调整大小，tab指向table
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
/********开始查找键的位置，并存储value*******/
// i = (n - 1) & hash这个是获取key应该在哪个桶里,下面详说
// 这里将p指向当前key所需要的那个桶
if ((p = tab[i = (n - 1) & hash]) == null) {
// 如果空桶，也就是无哈希冲突的情况，直接丢个Node进去。
// 此时的tab就是table
tab[i] = newNode(hash, key, value, null);
//存在冲突，开始寻找我们要找的节点
} else {
Node<K, V> e;
K k;
// 判断第一个节点是不是我们找的
// 此时k储存了 p.key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
// hash值相等，key值相等，定位完成,是修改操作
// e来储存p这个节点，一会修改
e = p;
// 判断是否是红黑树节点
} else if (p instanceof TreeNode) {
// 是红黑树节点，存在就返回那个节点，不存在就返回null
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 最终，是链表了，开始对链表遍历查找
} else {
for (int binCount = 0; ; ++binCount) {
// 上面知道第一个接点不是我们要的，直接获取下一个，并储存给e
// 下一个是空，直接丢个Node在这里，然后p.next指向这里
// 这里下一个节点地址给了e
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// ！大于树化阀值，开始树化
// 注意-1是因为binCount是索引而不是长度
// 其实此时链表长度已经是7+1（索引） + 1（新进来的Node）
// 已经大于树化阀值8，也就是说链表长度为8时是不会树化的
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;
}
}
// 上面说了，这有修改操作e才能不是null
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 给e新值
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
// 这个是LinkedHashMap用的，HashMap里是个空实现
afterNodeAccess(e);
// 修改就会把旧值返回去
return oldValue;
}
}
/*********修改完成的后续操作**********/
// 修改次数加1
++modCount;
// 如果size大于阀值，会执行resize()方法调整大小
if (++size > threshold) {
resize();
}
// 这个是给LinkedHashMap用的，HashMap里也是个空实现
afterNodeInsertion(evict);
// 添加成功返回null
return null;
}hash 方法
/** * hash 运算
* @param key
* @return */
static final int hash(Object key) {
int h;
/** * key是null就返回0，key不是null就先取hashCode（）
* 然后与这个hashCode（）无符号右移进行亦或运算 */
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么要使用异或运算
- 这是因为找key的位置时，
(n - 1) & hash是table的索引，n的长度不够大时，只和hashCode()的低16位有关，这样发生冲突的概率就变高。 - 为减少这种影响，设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高16位没有参与下标的计算(table长度比较小时)而引起的碰撞。
resize方法
这也是一个很重要的方法，主要包括两部分，第一部分是根据size是否超过阀值判断是否需要进行扩容，第二部分是扩容后将原Node[]中数据复制到扩容后的Node[]中
扩容的三种情况
- 使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
- 指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） * DEFAULT_LOAD_FACTOR。
- HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍
这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。
扩容部分
/**
* 扩容方法
*
* @return
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
// 原容量，table为null返回0，否则返回table长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原始阈值
int oldThr = threshold;
//新容量，新阈值
int newCap, newThr = 0;
// table已经初始化，旧容量>0
if (oldCap > 0) {
// 容量已经超过最大容量，直接返回去
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 2倍扩容后小于最大容量，并且原容量大于默认初始化容量(我还没想清楚为什么要大于默认初始容量)
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
// 阀值加倍
newThr = oldThr << 1; // double threshold
}
// 原数组容量为0，未初始化，但阀值不为0
// 也就是构造方法里threshold = tableSizeFor(initialCapacity）这个步骤
} else if (oldThr > 0) { // initial capacity was placed in threshold
newCap = oldThr;
// 啥都没有，默认构造
}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;复制数据部分
// 创建新的数组
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
//开始复制数据
if (oldTab != null) {
//开始遍历
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
// 获取桶的第一个节点
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 { // preserve order
// 不是直接进行计算元素在新数组中的位置，而是原位置加原数组长度
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
// 把链表下一个节点放在 next里
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;复制过程，a过去，假设计算后位置不边，进到i,此时i为null，a进去后即是head，又是tail
然后循环，到b，假设计算后还是i，i中已经有a，所以b直接丢到a后面，a任是head,单tail已经变成了b
以此类推，a,b,c,d都会放在i,j中
其实是先拼完链表才装进桶里的，这里只是方便描述，说成是一个一个过去
至此，put方法已经说完了，重点是putVal,hash和resize三个方法。
get方法
/**
* 返回指定的key映射的value，如果value为null，则返回null
* get可以分为三个步骤：
* 1.通过hash(Object key)方法计算key的哈希值hash。
* 2.通过getNode( int hash, Object key)方法获取node。
* 3.如果node为null，返回null，否则返回node.value。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K, V> e;
//根据key及其hash值查询node节点，如果存在，则返回该节点的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}其最终是调用了 getNode 函数。 其逻辑如下
getNode方法
/**
* getNode 方法
*
* @param hash 指定参数key的哈希值
* @param key 指定参数的 key
* @return 返回node，如果没有则返回null
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
//如果哈希表不为空，而且key对应的桶上不为空
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//如果桶中的第一个节点就和指定参数hash和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) {
//如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
}
//如果当前的桶不采用红黑树，即桶中节点结构为链式结构
do {
//匹配上key
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
//返回节点
return e;
}
//遍历元素直到 没有后继节点
} while ((e = e.next) != null);
}
}
//找不到 返回 null
return null;
}remove 方法
remove就是先找到节点位置，然后移除,核心方法是removeNode()
/**
* 删除方法
* @param key 所要删除元素的key
* @return
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}removeNode
/**
* 删除Node节点
*
* @param hash 要删除元素的hash
* @param key 删除元素的key
* @param value remove方法重载时使用，只有同时匹配key-value时移除该节点
* @param matchValue 为true时才会同时匹配key-value进行删除
* @param movable 删除节点后是否改变红黑树的结构，般都为true只有在iterator的时候才为false
* @return
*/
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;
// 1.原数组不为null
// 2. 原数组长度大于0
// 3.key数组中的位置不为空
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
// 声明两个节点node，e
Node<K, V> node = null, e;
K k;
V v;
// 第一个节点就我们要找的节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
// 先给node，在下面删掉
node = p;
//如果第一个不是则向后查找
} else if ((e = p.next) != null) {
// 如果是红黑树，获取该接点并给node
if (p instanceof TreeNode)
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else {
do {
// 如果是要找的节点就把这个节点给node
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
// 不是把节点给p记录
p = e;
//遍历节点一直到没有后继节点
} while ((e = e.next) != null);
}
}
/**********删除节点的部分*********/
//节点不为空
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
// 如果是红黑树节点，使用removeTreeNode移除
if (node instanceof TreeNode) {
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
} else if (node == p)
// 这里执行的就是上面的第一种情况，桶里的第一个节点就是要移除的
tab[index] = node.next;
else {
// 直接将移除的上个节点指向下一个节点
p.next = node.next;
}
// 修改次数再加1
++modCount;
// 长度 -1
--size;
// 给LinkedList使用，这里没啥用
afterNodeRemoval(node);
// 删除的值返回去
return node;
}
}
// 根本没有这个
return null;
}总结
我们现在可以回答开始的几个问题，加深对HashMap的理解：
什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
你知道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)，则使用红黑树来替换链表，从而提高速度。
你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
如果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()时顺着哈希桶数组来遍历，看起来是个乱序。
当两个对象的hashcode相同会发生什么？
因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
如果两个键的hashcode相同，你如何获取值对象？
找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。因此，设计HashMap的key类型时，如果使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择
如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置
你了解重新调整HashMap大小存在什么问题吗？
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。因此在并发环境下，我们使用CurrentHashMap来替代HashMap
为什么String, Interger这样的wrapper类适合作为键？
因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能
微信
支付宝
