HashMap
- 存储 key-value 映射关系
- HashMap中key值可以为空
- HashMap扩容策略为每次扩容为当前容量的2倍
- HashMap由于是根据哈希值进行存储的，因此它的存储位置是不确定的，遍历顺序也是不确定的。
- HashMap是非线程安全的，多线程下操作HashMap会导致数据的不一致。
- HashMap的key值是不可改变的。
- HashMap是使用数组 + 链表 + 红黑树(jdk 1.8引入)实现的。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
/* HashMap 数组默认初始容量 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/* HashMap 最大容量 --- ( 1073741824 )大概十个亿 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/* HashMap 默认加载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/* 单个结点树化的最小链表容量 */
static final int TREEIFY_THRESHOLD = 8;
/* 单个结点反树化的最小链表容量 */
static final int UNTREEIFY_THRESHOLD = 6;
/* 整个HashMap 树化的最小元素数量 */
static final int MIN_TREEIFY_CAPACITY = 64;
/* 节点数组 */
transient Node<K,V>[] table;
/* entry 集合 */
transient Set<Map.Entry<K,V>> entrySet;
/* HashMap 中元素的数量 */
transient int size;
/* HashMap 结构修改次数 fail-fast机制判断机制 */
transient int modCount;
/* 当 size 属性值大于该值时需要进行扩容 / threshold=(table.length* load factor) */
int threshold;
/* 加载因子 */
final float loadFactor;
}
为什么HashMap 的加载因子默认为 0.75：
太小会造成HashMap的空间大量浪费，太大会造成哈希冲突过多影响查询效率。
为什么 HashMap 的树化阈值为 8：
官方解释：
在理想情况下，在随机哈希码下，在容器中的节点频率遵循泊松分布，其参数平均为约0.5，对于默认大小调整阀值为0.75，尽管由于粒度的调整而存在较大的差异。忽略方差，列表大小k的期望发生的(exp(-0.5) pow(0.5, k) / factorial(k)),取值和概率如下：
即数组同一个位置上链表的长度大于八的可能性很小。因此我们选择 8 作为树化的阈值。
我的理解：
- 首先看为什么要进行树化？
HashMap进行树化的原因是当出现了多个元素哈希值相同，他们会被放到数组的同一个位置中并用链表进行连接，而当同一个位置的链表元素过多时，HashMap的查询效率就会急剧下降，因此我们需要处理在数组同一个位置链表元素积累过多时的元素查询效率【假如哈希函数处理的足够好，根本不会出现哈希冲突的话，我们也就不需要进行树化了不是吗^ - ^】。 - 再看HashMap怎么处理树化？
其实就是由于数组同一个位置上的链表长度大于 8 的可能性很小，因此若以8 作为阈值的话树化的效率最高，因为链表和红黑树在元素数量较少的情况下查询速度差别不是很明显，比方说在 HashMap 中有较大可能出现一个数组位置上链表数为 3 ，若是选择 3 作为树化阈值 ，那么我们就需要频繁的对HashMap 的链表节点进行树化，反而降低了HashMap整体查询效率，而当选择 8 为阈值时，可以有效解决由于某种原因造成的哈希数组某一个单元链表数量过长的影响，并且由于一般情况下同一个位置存在 8 个链表元素的几率很小，HashMap不会频繁的进行树化而增加自己的负担。
为什么HashMap的反树化阈值为 6：
因为树化阈值为 8 ，那么反树化阈值一定是低于树化阈值的。假如设置为 7，那么当我需要对同一个元素进行：插入删除插入删除插入删除……并且此时该元素对应的数组位置上元素数量已经达到树化阈值，此时我的HashMap就需要进行：树化反树化树化反树化……，所以，我们不能设置为 7 ， 那么 6 就是一个合适的选择。
HashMap的两个树化阈值：
HashMap中有两个树化阈值：
TREEIFY_THRESHOLD = 8；
MIN_TREEIFY_CAPACITY = 64；
那么这两个的关系我们从源码中可以找到答案。
putVal() 方法部分代码：
...
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
...
treeifyBin() 方法部分代码：
...
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
...
我们可以看出，当每一个数组上的链表结点数量大于等于 7 时调用treeifyBin方法准备进行树化操作，进入treeifyBin方法内部还需要再次判断，若底层数组的长度大于等于 64 则进行树化操作，否则执行数组的扩容操作。
HashMap 构造函数：
/* 默认构造函数 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // default = 0.75
}
/* 可以设置初始容量的构造函数 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/* 可以设置初始容量和加载因子的构造函数 */
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);
}
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;
}
/* 可以传递Map 参数的构造函数 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
tableSizeFor 方法：
当你调用空构造函数来建立HashMap时，默认数组容量为 16。当你传入自己的 initialCapacity 进行HashMap 初始化时，则会进入tableSizeFor 方法进行数组数量的再次赋值，tableSizeFor 方法的作用是将传入的initialCapacity 参数转换为 大于等于initialCapacity 的 2 的幂次方。
PS：
传入 : 1 传入： 3 传入：5 传入：10 传入：12 传入：17
数组：2 数组：4 数组：8 数组：16 数组：16 数组：32
tableSizeFor方法是为了方便计算哈希值出现的
说一说HashMap中元素哈希值的计算方式：
我们知道 key.hashCode()函数是调用的键自己的哈希函数，返回值是一个int类型的散列值，当然， int类型的数据范围在-2147483648到2147483647，我们的HashMap不一定会有这么大的存储空间，因此这个散列值是不能够拿来直接使用的，那么我们要想使用它，可以用它和哈希桶的长度进行取模运算，这样便可以使得下标全部在哈希桶内。
对于一般的取模运算，HashMap做了一个改进，即使所有容器的容量控制在2的幂次方，取模运算也就变成了 h&(length-1)。
例如我们的容器容量为16，那么length-1的值变为15，对于15来讲他的二进制码为
00000000 00000000 00000000 00001111
假如我们计算出来的哈希码为
10100011 00110011 11000110 01010011
我们想要哈希码对哈希桶长度进行取模运算，h&(length-1) 的值即为
00000000 00000000 00000000 00000011
这样哈希码的高位就会全部为零，而参与计算的低位即为哈希码原来的低位值，这样的运算效率会比直接取模优秀更多。
那么HashMap中为什么会存在二次hash呢？
讲道理，我们一开始计算的哈希为 int 类型的整数，那么他的冲突概率可以说是非常小了，但是我们对他进行了取模运算，这样大幅缩减了他的初始值，因此哈希冲突的概率会明显增大（只要低位相同就会在一个桶中），HashMap为了解决这个问题进行了二次hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个方法是将我们计算出来的哈希值低16位与他的高16为进行异或运算，目的是为了保留一部分来自哈希码高位的信息，这样即使他们的低16位开始相同，在对高位进行异或运算之后也可能改变低16位的数值，在存放到哈希桶中时也不会放到一个桶中，这样便打散了原来在一个桶中的元素。使得哈希表的效率更高。
【参照：https://www.zhihu.com/question/20733617/answer/111577937】
put 方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 插入时首先判断当前结点为链表结点还是红黑树结点，按照合适的结点类型进行结点的插入。
* 当链表结点数等于 7 时进行树化操作。在treeifyBin函数中有一个判断：
* 即 当底层数组的长度大于等于数组最小树化阈值（64）时才进行树化操作，
* 否则执行数组的扩容操作。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
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;
}
}
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();
afterNodeInsertion(evict);
return null;
}
// 树化函数
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
网友评论