什么啊？面试官还在问HashMap了，老知识点了啊
导读：HashMap为什么经常被面试官问到，但是经常被面试官问趴下怎么办？哈，原理我不知道？笑话！不就是一个hash加一个map嘛，多简单啊？ 答：利用key的hashCode重新hash计算出当前对象的元素在数组中的下标，存储到数组里面就行了，...
HashMap为什么经常被面试官问到，但是经常被面试官问趴下怎么办？
哈，原理我不知道？笑话！
不就是一个hash加一个map嘛，多简单啊？ 答：利用key的hashCode重新hash计算出当前对象的元素在数组中的下标，存储到数组里面就行了，底层就是数组嘛！ 然后面试官说了句：好的，我知道了，回去听消息吧！
这种答复并不是面试官想要看到的，想要听到程序员有自己的理解和分析优化！客官，来，1.7源码！
/**
*继承AbstractMap，并重写Map接口
**/
public class HashMapK,V>
extends AbstractMapK,V>
implements MapK,V>
, Cloneable, Serializable
static final int DEFAULT_INITIAL_CAPACITY = 1 4;
// 位运算，1左移4位=16
static final int MAXIMUM_CAPACITY = 1 30;
//位运算，左移30位=1073741824
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//负载因子0.75
transient EntryK,V>
[] table;
//entry数组 entry又是个单链表结构
transient int size;
//hashmap长度
int threshold;
//capacity * load factor 阈值比如16*0.75 = 12
void resize(int newCapacity)；//扩容方法
static int indexFor(int h, int length) {
return h &
(length-1);
//计算index方法
}
void createEntry(int hash, K key, V value, int bucketIndex) {
EntryK,V>
e = table[bucketIndex];
table[bucketIndex] = new Entry>
(hash, key, value, e);
//头插法解决hash冲突
size++;
}
通过源码可以知道，HashMap的默认初始化长度为1 4=16，最大容量为130=1073741824. 可以看出1.7是采用数组加单链表的结构，Entry是一个继承Map.Entry的单链表结构。size就是hashmap的长度，threshold就是插入扩容的阈值。 从reSize方法可以看出，1.7是先进行扩容再插入数据的。
别着急，1.7是怎么进行扩容再插入的嘛！
容量初始值为16，当插入数据数量大于阈值（capacity * load factor=12）并发生hash冲突时就进行扩容。每次扩容都是2的n次幂，这样好处就是利于位运算，并且length-1的二进制最后一位为1，减少了hash碰撞。且插入时是通过int i = indexFor(e.hash, newCapacity); 重新计算的，即hash & （length-1），并重新设置阈值（newCapacity * loadFactor）。
void resize(int newCapacity) {
//扩容方法：resize(2 * table.length)，当容量不足时（容量 >
阈值），则扩容（扩到2倍）
Entry[] oldTable = table;
//复制旧的哈希表
int oldCapacity = oldTable.length;
//旧的容量
if (oldCapacity == MAXIMUM_CAPACITY) //容量如果等于最大值，则不再扩容
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &
&
(newCapacity >
= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
//转移数据到新哈希表里
table = newTable;
//完成扩容
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
//重新设置阈值
}
void transfer(Entry[] newTable, boolean rehash) {
//将旧哈希表的数据移到新的哈希表里
//过程：按旧链表的正序遍历链表、在新链表的头部依次插入
int newCapacity = newTable.length;
for (EntryK,V>
e : table) {
//遍历哈希表
while(null != e) {
EntryK,V>
next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//重新计算index值
e.next = newTable[i];
newTable[i] = e;
//头部插入
e = next;
}
}
}
还有1.8吗，太难了。挺住，坚持坚持就看完了！
客官，还有1.8呢public class HashMapK,V>
extends AbstractMapK,V>
implements MapK,V>
, Cloneable, Serializable
static final int DEFAULT_INITIAL_CAPACITY = 1 4;
static final int MAXIMUM_CAPACITY = 1 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Bins are converted to trees when adding an element to a bin with at least this many nodes.
static final int TREEIFY_THRESHOLD = 8;
//当桶的节点数量大于该阈值时转换为红黑树
static final int UNTREEIFY_THRESHOLD = 6;
//当桶的节点数小于该阈值时会转换成链表，前提是当前是红黑树结构
static final int MIN_TREEIFY_CAPACITY = 64;
//桶的节点数大于该容量时也会转换成红黑树
static class NodeK,V>
implements Map.EntryK,V>
;
//换成节点了
static final class TreeNodeK,V>
extends LinkedHashMap.EntryK,V>
;
//树节点
transient NodeK,V>
[] table;
//数组加单链表，后期会转红黑树
transient SetMap.EntryK,V>
>
entrySet;
//数据的另一种存储方式，主要用于迭代功能
transient int size;
//hashmap元素数量
transient int modCount;
//该map的修改次数从源码可以看出，初始容量还是16，负载因子还是0.75，只是多了关于红黑树的知识点。1.8采用数组加单链表加红黑树的数据结构，扩容还是扩2的n次幂。
hash方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >
>
>
16);
}
通过判断key值是否为空，如果空就为0，不为空就异或运算。
存值方法put
public V put(K key, V value) {
//存值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
NodeK,V>
[] tab;
NodeK,V>
p;
int n, i;
//获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) &
hash]) == null)//(length-1)&
hash计算出索引值，判断当前哈希桶是否为空
tab[i] = newNode(hash, key, value, null);
//空就赋值给当前桶
else {
//该哈希桶不为空，会发生hash冲突，以下为发生hash冲突几种情况
NodeK,V>
e;
K k;
//第一种情况，当前的hash值相同，且key值也相同，e = p表示首节点。
if (p.hash == hash &
&
((k = p.key) == key || (key != null &
&
key.equals(k))))
e = p;
//第二种情况，如果当前桶为树节点实例且不是首节点，即红黑树节点。是树节点则在红黑树中添加
else if (p instanceof TreeNode)
e = ((TreeNodeK,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);
//节点数大于等于7，则转换红黑树结构（从0开始到7）
break;
}
if (e.hash == hash &
&
((k = e.key) == key || (key != null &
&
key.equals(k))))
break;
//插入节点与next节点重复，跳出循环
p = e;
}
}
if (e != null) {
//在节点中存在重复的值，直接覆盖旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//修改次数加一
if (++size >
threshold)
resize();
//容量增一，判断是否需要扩容
afterNodeInsertion(evict);
//添加成功
return null;
}
总的来说就是put的时候会进行判断当前桶是否为空，空就直接赋值。不为空且hash相同，则存在冲突，此时需要处理冲突的三种情况： ①当前桶不为空，且key值相同，则直接覆盖。 ②当前桶不为空，则桶节点不为首节点，且为红黑树节点，则在红黑树中添加。（节点数> =TREEIFY_THRESHOLD） ③当前桶为不为空，不为首节点，不为红黑树节点，则为链表节点。(节点数TREEIFY_THRESHOLD）添加时如果大于等于7（从0到7），则需要转为红黑树节点。
插入值过后就需要判断容量问题，此时就需要reSize()方法,从上述的源码中if (++size > threshold)就知道JDK1.8是先插入再进行判断扩容的。当链表深度大于8时，会自动扩容为红黑树结构，时间复杂度从O（n）转到O（logn）
final NodeK,V>
[] resize() {
//扩容方法
NodeK,V>
[] oldTab = table;
//之前旧的哈希表
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//old的表的阈值
int newCap, newThr = 0;
if (oldCap >
0) {
if (oldCap >
= MAXIMUM_CAPACITY) {
//容量大于最大值
threshold = Integer.MAX_VALUE;
//此时阈值为整数最大值
return oldTab;
//最大限度 不能扩容了
}
//左移一位，新的哈希表扩容两倍，且要小于最大容量；且旧容量要比默认初始容量大
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;
//初始化的阈值
else {
//容量为0，阈值就为容量*负载因子
newCap = DEFAULT_INITIAL_CAPACITY;
//默认初始容量16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//阈值16*0.75=12
}
if (newThr == 0) {
//如果初始化容量小于16时，没有阈值。因为构造函数可以自己设初始容量
float ft = (float)newCap * loadFactor;
newThr = (newCap MAXIMUM_CAPACITY &
&
ft (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//赋值给阈值
@SuppressWarnings({
"rawtypes","unchecked"}
)
NodeK,V>
[] newTab = (NodeK,V>
[])new Node[newCap];
table = newTab;
//扩容后将旧的哈希表赋值到新的哈希表中
if (oldTab != null) {
for (int j = 0;
j oldCap;
++j) {
NodeK,V>
e;
if ((e = oldTab[j]) != null) {
//当前哈希桶节点为e
oldTab[j] = null;
if (e.next == null)//没有下个节点
newTab[e.hash &
(newCap - 1)] = e;
//重新计算index，放入新的哈希表中
else if (e instanceof TreeNode)//有next节点，且为树节点，将此树转移到新的cap中
((TreeNodeK,V>
)e).split(this, newTab, j, oldCap);
else {
// preserve order 链表情况，将链表插入到新的哈希表节点中
NodeK,V>
loHead = null, loTail = null;
NodeK,V>
hiHead = null, hiTail = null;
NodeK,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;
//返回新的哈希表
}
总的来讲，插入数据后扩容过程分为以下几个步骤：
①当前容量是否超过最大容量，超过则不扩容，直接返回。且阈值（threshold）为整数的最大值 ②当前容量小于最大容量且大于初始容量。容量扩大两倍，阈值也扩大两倍
扩容后就将旧的表数据转移到新的表，利用hash& length-1计算index值，判断当前桶节点属于链表节点还是红黑树节点，再依次移入。
public V remove(Object key) {
NodeK,V>
e;
//判断删除的节点是否为空，不为空就返回该节点值
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final NodeK,V>
removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
NodeK,V>
[] tab;
NodeK,V>
p;
int n, index;
if ((tab = table) != null &
&
(n = tab.length) >
0 &
&
(p = tab[index = (n - 1) &
hash]) != null) {
NodeK,V>
node = null, e;
K k;
V v;
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 = ((TreeNodeK,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)//如果删除的是红黑树节点
((TreeNodeK,V>
)node).removeTreeNode(this, tab, movable);
else if (node == p)//普通节点
tab[index] = node.next;
else//链表节点，修改next值
p.next = node.next;
++modCount;
//修改次数加一
--size;
//元素减一
afterNodeRemoval(node);
return node;
}
}
return null;
//表示没有该节点，没找到
}
区别加总结
相同点： 计算index都是hash& length-1 不同点： ①JDK1.7时采用的是数组加单链表的数据结构，JDK1.8采用的是数组加单链表加红黑树的数据结构 ②1.7是先扩容再插入，1.8是先插入再扩容 ③解决冲突时，1.7是头插法的纵向延伸，但会容易逆序环形链表死循环问题；1.8是加入了红黑树，采用尾插法，能够避免出现逆序死循环的问题。
HashMap有哪些不足，怎么解决和优化
hashmap具有键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化的特性，即
为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键
HashMap 中的 key若 Object类型， 则需实现哪些方法？
部分内容借鉴网址： www.jianshu.com/p/8324a3457… 确实写的好，佩服！
Hashmap确实还有很多可以深挖的知识点，这也是我第一次认真的写一篇文章，在我这么写了几千字的面子上就点个小心心呗，以后我会隔几天写一篇技术栈的文章并且同步到github上！有什么写的不好的地方和不足，欢迎大家指出！
隔壁写的实在是太好了，导致我有点力不从心，就这样吧！声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 什么啊？面试官还在问HashMap了，老知识点了啊
本文地址： https://pptw.com/jishu/9934.html