共计 5485 个字符，预计需要花费 14 分钟才能阅读完成。
jdk1.8 对 hashmap 的简略介绍
基于哈希表实现的 Map 接口。此实现提供了所有可选映射操作，并容许空值 (value) 和空键 (key)。(HashMap 类大抵相当于 Hashtable，只是它是线程不平安的，并且容许空值) 这个类不能保障映射的程序; 特地是, 它不能保障程序随工夫放弃不变。
hashmap 底层构造
hashmap 底层由数组和链表实现(jdk1.8 中当链表的长度大于 8 时, 链表会转换成红黑树)
hashmap 的初始容量和最多容量
初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16最大容量 1 << 30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 为什么不是 1 << 31, 因为最左侧的一位示意符号位, 容量不能为正数为什么规定容量必须是 2 的 n 次幂
- 放慢 hash 计算速度
- 均匀分布，缩小 hash 抵触
// 计算索引算法
i=(len - 1) & hashlen 为数组的长度, 因为 len 是 2 的 n 次方,(n-1)转换成 2 进制后全副为 1.
2 的 n 次方，能够通过位移操作来实现，能够放慢 hash 计算速度，联合按位与计算放慢数组下标的计算。例如在 HashMap 做扩容时，满足 2 的幂就是相当于每次扩容都是翻倍（就是 <<1 右移一位），这样扩容时在从新计算下标地位时，只有两种状况，一种是下标不变，另一种是下标变为：原下标地位 + 扩容前容量，这样扩容后节点挪动绝对较少，也能够进步性能。。
能够改善数据的均匀分布，缩小 hash 抵触，毕竟 hash 抵触越大，代表数组中一个链的长度越大，这样的话会升高 hashmap 的性能。
其中要害代码为 HashMap 中的数组下标计算：i = (n – 1) & hash，该计算方法能够实现一个均匀分布。
hashmap 怎么计算 hash 值, 为什么
高 16 位和低 16 位进行异或
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}次要还是为了解决 hash 碰撞问题。让高位和低位都参加 hash 值的计算
怎么指定 hashmap 的初始值, 怎么保障输出的值是 2 的 n 次方
new HashMap<>(n);保障输出的值是 2 的 n 次方, 该算法让最高位的 1 前面的位全变为 1
// 返回大于输出参数且最近的 2 的整数次幂的数。比方 10，则返回 16
// Returns a power of two size for the given target capacity.
static final int tableSizeFor(int cap) {
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;
}hashmap 在什么状况下进行扩容
加载因子 0.75. 如果默认容量是 16, 那么当元素达到 16 x 0.75=12 时, 就会产生扩容.
static final float DEFAULT_LOAD_FACTOR = 0.75f;为什么加载因子是 0.75
在 HashMap 的源码中有这么一段正文
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million大略意思是:
在现实状况下，应用随机哈希码，在扩容阈值（加载因子）为 0.75 的状况下，节点呈现在频率在 Hash 桶（表）中遵循参数均匀为 0.5 的泊松散布。疏忽方差，即 X = λt，P(λt = k)，其中 λt = 0.5 的状况，按公式
抉择 0.75 作为默认的加载因子，齐全是工夫和空间老本上寻求的一种折衷抉择。
在 jdk1.8 中在什么状况下链表会转换成红黑树
static final int TREEIFY_THRESHOLD = 8;jdk1.8 resize 的过程
当 put 时，如果发现目前的 bucket 占用水平曾经超过了 Load Factor 所心愿的比例，那么就会产生 resize。在 resize 的过程，简略的说就是把 bucket 裁减为 2 倍，之后从新计算 index，把节点再放到新的 bucket 中。resize 的正文是这样形容的：当超过限度的时候会 resize，然而又因为咱们应用的是 2 次幂的扩大(指长度扩为原来 2 倍)，所以，元素的地位要么是在原地位，要么是在原地位再挪动 2 次幂的地位。
例如咱们从 16 扩大为 32 时，具体的变动如下所示：
因而元素在从新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的 mask 范畴在高位多 1bit(红色)，因而新的 index 就会产生这样的变动：
因而，咱们在裁减 HashMap 的时候，不须要从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。能够看看下图为 16 裁减为 32 的 resize 示意图：
这个设计的确十分的奇妙，既省去了从新计算 hash 值的工夫，而且同时，因为新增的 1bit 是 0 还是 1 能够认为是随机的，因而 resize 的过程，平均的把之前的抵触的节点扩散到新的 bucket 了。
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
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 { // 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"})
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 = 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;
}你晓得 get 和 put 的原理吗？equals()和 hashCode()的都有什么作用？
通过对 key 的 hashCode()进行 hashing，并计算下标 ( n-1 & hash)，从而取得 buckets 的地位。如果产生碰撞，则利用 key.equals() 办法去链表或树中去查找对应的节点
头插法与尾插法
jdk1.7 插入元素到单链表中采纳头插法，jdk1.8 采纳的是尾插法。
- jdk1.7 插入链表的头部, 有一种认识是新插入的数据被查问的概率比拟大, 插入到头部查问绝对比拟快. 然而在多线程环境中扩容可能会造成循环链表, 导致 CPU100%
- jdk1.8 改良: 采纳尾插法, 在扩容时不必从新计算 hash 值, 元素索引值的变换是有法则的.
Entry 与 Node
- jdk1.7 一对 key,value 叫做 Entry
- jdk1.8 一对 key,value 叫做 Node
为什么要重写 equals 和 hashCode
- hashCode 决定了 Node/Entry 在数组中的地位
- equals 在元素产生碰撞时比拟应用
hashmap 默认应用 java.lang.Object#equals 比照的是对象的地址,hashmap 对象存储堆中, 地址必定不一样, 所以要依据业务实现本人的 equals, 然而 equals 判断须要, 然而 hashmap 在判断是先判断 hashCode 相等后才会去执行 equals.
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
....案例
public class Name {
private String first; //first name
private String last; //last name
public String getFirst() {return first;}
public void setFirst(String first) {this.first = first;}
public String getLast() {return last;}
public void setLast(String last) {this.last = last;}
public Name(String first, String last) {
this.first = first;
this.last = last;
}
@Override
public boolean equals(Object object) {System.out.println("equals is running...");
Name name = (Name) object;
return first.equals(name.getFirst()) && last.equals(name.getLast());
}
public static void main(String[] args) {Map<Name, String> map = new HashMap<Name, String>();
Name n1 = new Name("mali", "sb");
System.out.println("the hashCode of n1 :" + n1.hashCode());
map.put(n1, "yes");
Name n2 = new Name("mali", "sb");
System.out.println("the hashCode of n2 :" + n2.hashCode());
System.out.println("is the key existed? ture or false? ->"
+ map.containsKey(n2));
}
}
原文: https://rumenz.com/rumenbiji/java-hashmap-interview.html
