近日，国新办就工业和信息化发展情况举行发布会，工信部部长肖亚庆表示，在APP中看到不喜欢的广告很难找到关闭按钮，对于这种广告骚扰，群众反映很多。如果不想看到广告，关闭按钮应该很明显。遇到网络不良和垃圾信息，可以打12321举报。
本篇文章来自
进击的鱼儿
同学的投稿，分享了自己对HashMap源码的相关理解，相信会对大家有所帮助！同时也感谢作者贡献的精彩文章！
https://juejin.cn/user/4406498333823310
HashMap(哈希表)，是根据key而直接访问内存存储位置的数据结构。也就是说，它通过计算一个关于key的函数，将所需查询的数据映射到表中的一个位置来访问记录，这加快了查找速度。这个映射函数称作散列函数，存放记录的数组称作散列表，也叫哈希表。
-
put(key, value)：向哈希映射中插入（键，值）对。如果键对应的值已存在，更新这个值。
-
get(key)：返回给定键所对应的值，如果映射中不包含这个键，返回null。
-
remove(key)：如果映射中存在这个键，删除这个键值对。
为了实现HashMap有两个关键的问题，即散列函数和冲突处理。
-
散列函数：若关键字为k，则其值存放在f(k)的位置上。因此，不用比较就可以直接通过key找到value。
-
冲突处理：如果k1≠k2，而f(k1)=f(k2)，即对于不同的key得到了同一个散列地址，这种现象称为冲突。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就使关键字经过散列函数得到一个随机的地址，从而减少冲突。
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
-
直接定址法：hash(k)=a∗k+b，其中 ab 为常数
-
-
-
除留余数法：取key被某个不大于散列表表长m的数p取模为散列地址。即hash(k)=k%p,(p≤m)。不仅可以对key直接取模，也可以在随机数法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突
为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
其中hash(key) 为散列函数，m为散列表长，d为增量序列，i为已发生冲突次数。增量序列可有下列取法：
，其中ab为常数，且a≠0。假设a = 1,相当于在发生冲突时逐个探测存放地址的表，直到找到一个空单元，把散列地址存在该空单元。
称为平方探测。相对线性探测，相当于发生冲突时探测间隔i个单元的位置是否为空，如果为空，将地址存放进去。
下图显示线性探测填装一个散列表的过程。
关键字为{80,11,40}，此时线性探测方程是
当填装40的时候，地址0已经填装了80，取i = 1 ，往地址1查找，发现地址0已经装填了11，取i = 2 ，往地址2查找，发现为空，将40填装在地址为2的空单元。
表的大小选取至关重要，此处选取10作为大小，发生冲突的几率就比选择质数11作为大小的可能性大。越是质数，取余就越可能均匀分布在表的各处。
从图中容易发现在函数地址的表中，散列函数的结果如果不均匀的分布表的单元，形成区块，会造成线性探测和平方探测产生聚集，散列到区块中的关键字需要多次的探测才能找到空单元插入，造成了时间浪费。
对于相同的散列值，将它们用一个链表链接起来，每个链表相互独立。
hash是一些散列函数。即在上次散列计算发生冲突时，利用该此冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生聚集，但增加了计算时间。
如图，这里使用java中LinkedList实现单链表。
public static class MyHashMap<K, V> {
private static int DEFAULT_BUCKET_SIZE = 10;//默认长度10
private Bucket[] buckets;
public MyHashMap() {
buckets = new Bucket[DEFAULT_BUCKET_SIZE];
}
public void put(K key, V value) {
int hashKey = key.hashCode() % buckets.length;
this.buckets[hashKey].put(key, value);
}
public V get(K key) {
int hashKey = key.hashCode() % buckets.length;
return buckets[hashKey].get(key);
}
public void remove(K key) {
int hashKey = key.hashCode() % buckets.length;
buckets[hashKey].remove(key);
}
}
private static class Pair<K, V> {
public K key;
public V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
}
private static class Bucket<K, V> {
private List> bucket;
public Bucket() {
bucket = new LinkedList<>();
}
public V get(K key) {
for (Pair pair : bucket) {
if (pair.key.equals(key)) {
return pair.value;
}
}
return null;
}
public void put(K key, V value) {
boolean found = false;
for (Pair pair : bucket) {
if (pair.key.equals(key)) {
pair.value = value;
found = true
;
}
}
if (!found)
this.bucket.add(new Pair<>(key, value));
}
public void remove(K key) {
for (Pair pair : this.bucket) {
if (pair.key.equals(key)) {
this.bucket.remove(pair);
break;
}
}
}
}
/**
* 测试
*/
public void test(){
MyHashMap hashMap = new MyHashMap<>();
hashMap.put(80,"A");
hashMap.put(11,"B");
hashMap.put(40,"D");
hashMap.put(25,"C");
System.out.println(hashMap.get(40));
}
-
时间复杂度：O(N/k)。其中N指的是所有可能值数量，K指的是预定义的散列地址长度。
-
假设值是平均分布的，因此可以考虑每个链表的平均长度是N/k。
-
对于每个操作，最坏情况下需要遍历整个链表，因此时间复杂度是O(N/k)。
-
空间复杂度：O(K+M)，其中K指的是预定义的散列地址长度，M指已经插入到HashMap中值的个数。
一个最简单的HashMap完成了，来分析一下有哪些问题：
-
单链表的查询、插入、删除时间复杂度都是O(N)，效率并不高。
-
散列地址长度固定为10，随着插入的元素增加，链表的长度会原来越长，而我们的时间复杂度是O(N/k),k = 10固定，N一直增大，可想而知算法的效率越来越低。
对于第一个问题，可以换成一个效率更高的数据结构来解决，比如红黑树，可以把时间复杂度从O(N)降低到O(logN)。
第二个问题，既然时间复杂度是O(N/K)，那是不是只要把K取值大一些就好了？确实K增大时间复杂度降低，但是空间复杂度为O(K+M)，K增大的同时也会增大空间复杂度。
综合考虑下，应该让N和K保持一定的比例关系，不至于N很大，K很小导致时间复杂度太高，同时也不会N很小，K很大浪费空间，让时间复杂度相对稳定。
载荷因子定义定义为：a = 填入表中的元素个数 / 散列表的长度。
可以看出载荷因子实际上就等于上文说的N/K。
a是散列表装满程度的标志因子。由于表长是定值，所以a越大，表明填入的元素越多，产生冲突的可能行就越大，反之，a越小，表明填入的元素越少，产生冲突的可能行越小。因此对于空间比较大，注重时间的情景可以选取小一些的a，反之相反。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。
Java8 HashMap是JDK中实现的散列表，它做了很多的优化，对于上文提到的问题，来看看它是如何巧妙的解决的。
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
成员变量中有个Node健值对数组，很明显其散列表中存储的正是Node，从注释可以看到如果需要，这个数组会resized，并且数组的长度总是2的幂！，从上文除留余数法中说的散列表的长度应该取素数得知这里的是一个非常规的设计，而之所以这么设计要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位散列表索引位置时，也加入了高位参与运算的过程。
既然散列标存放的是Node，而Node即可以是链表的节点，也可以是树的节点，那java中使用的什么呢？
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) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//初始化
if ((p = tab[i = (n - 1) & hash]) == null) // 1
//对应散列地址为空，直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//散列表对应地址第一个key就相同，直接更新
else if (p instanceof TreeNode)
//如果红黑树的节点，那么就插入到红黑树中
e = ((TreeNode)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
//如果链表长度>=(TREEIFY_THRESHOLD = 8),就将该链表转换成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;//p指向next节点
}
}
if (e != null) { //要插入的节点已存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //onlyIfAbsent用来控制已存在时是否更新值
e.value = value;//更新值
afterNodeAccess(e);//模板方法，交由子类实现
return oldValue;
}
}
++modCount;
if (++size > threshold)
//存储元素个数大雨threshld，重新调整大小
resize();
afterNodeInsertion(evict);//模板方法
return null;
}
可以看到Node并不固定为一种数据结构，在节点个数大于等于8时，将会从链表转换成红黑树。在节点个数小于8时，链表的平局查找次数小于8/2 = 4，相比而言红黑树的查找次数小于log(8) = 3，因此只有在链表长度大于等于8时才有必要转换成红黑树，虽然链表个数大于等于8时转换成红黑树的平均查找次数依然小于链表，但是差距很小，且转换成树结构的也需要时间，来看看JDK中给出的实验数据：
