1. HashMap
- 发现很多接发都用到了map,其中C++的vector容器,java是HashMap
- 涉及到之前数据结构盲区 红黑树 https://www.cnblogs.com/shoulinniao/p/11966194.html
2.《Java核心技术卷一》P372,chap9.3:映射
- 映射 MAP 数据结构= 「HashMap」&&「TreeMap」
- 存放 {键KEY:值VALUE}对
- 都只对 键(KEY)进行处理( 散列&& 搜索树排序 )
3.相关方法函数:
1 | //哈希map初始化,自己定义Key和Value的类型 |
- import java.util.HashMap;//导入
- HashMap<K, V> map = new HashMap<K, V>();//定义map,K和V是类,不允许是基本类型?
- put(K, V)
- V get(K)
- V remove(K)//移除K键的值,返回的是V,可以不接收
- size()//返回映射Map中的元素数目
- replace()//替换
map.replace( Key,Value ); <!--1-->
9. computeIfAbsent()//
//如果key键为java的,就添加,并且value为key键的长度 //这个算子就是一个和put功能差不多的算子,都是往map里面添加数据。 map.computeIfAbsent("java", (key)->((String)key).length()); <!--2-->
4.关于遍历方法:
1 | //返回所有 Key-Value 对: |
5.其他:
6.整理下HashMap里面的常见面试考点:
HashMap 默认容量:
- 默认容量是:16 = 1 << 4(位移动 = $1000_2$ = $16_{10}$);
- 默认负载因子是:0.75(根据)(服从泊松分布):红黑树部分也是这个原理:
- 桶中的节点个数服从泊松分布;
- 取 $\lambda = 0.5$ ,此时 ,每个捅中元素个数为 【0,8】个的概率分别如图所示,大于八个,基本已经到达百万分之一的级别,所以 Java8 中选择以 8 作为一个临界数字,来决定是否将链表转化为 红黑树;
- 其中,在 最大桶元素个数 = 7 时,不变,作为缓冲,以防止过于频繁的转换消耗;
如何扩容?
- $2^n$ 的形式,每次翻两倍;(这和 Hash 的工作机制有关:(n - 1)& hash)
- 这样子的好处是,($2^n$-1)= 一个全为1 的二进制树,计算更快;
为什么HashMap的数组大小一定要是 2 的幂?
和 Hash 的工作机制有关;HashMap求索引时用&运算,index=(n-1)&hash
n = length : 表长度 = $2^n$
(HashTable求索引用模运算,index = (hash & 0x7FFFFFFF) % n)
:只有这样才能保证 经过 ( $2^n $ ) 操作后得到全是1 的值;
然后这样才能经过非常快速的位运算,快速拿到数组下标,并且能保证分布均匀
若不是 $2^n$, 则运算过后,会有0存在,那么就会导致,不管 和他进行按位与 运算的数字是多少,都会出现某些位永远是 0,那么就会导致,某些 桶 里的元素永远都是 0个,不均匀且不合理;
HashMap 为什么是线程不安全的?
- 在接近临界点时,若此时两个或者多个线程进行put操作,都会进行resize(扩容)和reHash(为key重新计算所在位置),而reHash在并发的情况下可能会形成
链表环
。 - 总结来说就是在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。
- 为什么在并发执行put操作会引起死循环?是因为多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。
- jdk1.7的情况下,并发扩容时容易形成链表环,此情况在1.8时就好太多太多了。
- 因为在1.8中当链表长度达到阈值(默认长度为8)时,链表会被改成树形(红黑树)结构。如果删剩节点变成7个并不会退回链表,而是保持不变,删剩6个时就会变回链表,7不变是缓冲,防止频繁变换。
- 在JDK1.7中,当并发执行扩容操作时会造成环形链和数据丢失的情况。
- 在JDK1.8中,在并发执行put操作时会发生数据覆盖的情况。
- 在接近临界点时,若此时两个或者多个线程进行put操作,都会进行resize(扩容)和reHash(为key重新计算所在位置),而reHash在并发的情况下可能会形成
Java 7 到 8 做了哪些改进?为什么?
- 如上题所述:
7.拓展
你能想到的做 HashMap 匹配的方法?
- 直接取模:($-2^{31}$ ~ $2^{31} -1$ )% n = (0 , $n-1$)
- 缺点:两个:
- 负数对 n求余,答案是负数;(所以需要额外把 负数 变为 正数 )
- 速度较慢(相比于位运算):因为硬件中“求余”的本质是“除法”
常考的“坑”:扩容:resize()
- 扩容 resize( )包括 rehash ( )
- 机制是,当原来的容器中,容量达到了 0.75 * capacity, 再创建一个 2 * capacity 的新的桶;
- 然后会把旧的桶中的数据 迁移 过去,迁移的时候,伴随着重新地对原始数据进行 rehash 计算;
- resize()里面的 transfer()是一切问题的根源!!
- 死锁问题::本身是线程不安全的;完全是用户的问题;
- 哈希表最致命的缺陷:哈希碰撞——>最差情况下,会变成单链表;链表性能退化
- 所以在java7时代的 Tomcat(2011) 中引起了问题——>可以通过一组精心设计的 恶意请求,造成 DoS(Deny of serveice)
"Aa","BB","C#" 的哈希值是相同的!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
7. ![image-20200622231322114](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183234.png)
## 8. Java8的改进点 && 新API
1. 从 **数组 + 链表**——>**数组 + 链表 / 红黑树**
2. 扩容时,插入顺序的改进:(原来是,从旧的头先取,然后按照“头插法”插入新的桶,导致顺序不稳定)
3. 函数方法:(java 8 引入了 Lamda 表达式)
1. forEach
2. compute 系列
4. Map 的新 API
1. Merge
2. replace
***
# 9.补充
1. **抑或运算**:可以更简单地理解为 **不进位的 加法 !**
2. 红黑树转换,并不是要把整张表都从链表改成红黑树,而是只要 超过 8 个元素的 那个桶,改一下形式,就行了:
3. ![image-20200623000116947](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183235.png)
4. 二叉平衡树,平均查找时间:O($log N$)
5. 单纯的二叉树,有个极端情况:插入顺序是有序的,那么就会造成演化成 **单链表**
6. 而红黑树,经过一定的旋转,保证了查找的效率(具体再仔细看看书)
7. **新的 Java8 中的 resize()函数**:改进成了 **扩容时** 能保持原来的顺序,但是仍然不能保证 **线程安全**,只能说是大搭建撒后了线程冲突的概率。
8. 所以未来可能不会再多线程情况下遇到问题,但是还是不能放心地在多线程环境下使用它!(**Linux中的任务调度 是多线程的,有用到 HashMap**)
9. **HashCode** : 默认使用 **32位** 的 **Int** 的**HashCode**;
***
# 10.面试题常见:
1. 为什么用 数组 +链表:经典的学院派操作
2. Hash 冲突你还知道哪些解决办法:可以在冲突的桶里面,再套一层 Hash 表;即,冲突的进行二次分流;(表中再有个表)
3. 用Lin课的Li身体代替数组结构可以吗?:不可以,数组的随机访问是 O(1)的,不受数组长度的影响,二链表的顺序访问速度是 O(n),不能起到随机访问的效果;
4. get()的操作?:如果第一个元素就是要求的话,那么就直接返回它;不是的话,那么,先判断该桶是什么结构,如果是红黑树,那么就用树的查找方法 查找;否则若是链表结构,就采用链表的顺序访问形式访问
5. 为什么 String 、Integer 这样的 wrapper 类 适合作为键?:因为String是final,具有不变性,而且已经重写了 equals()和hashcode()方法了。不变性是必要的!因为 为了要计算 hashcode(),就要防止键改变,如果键再嵌入时和获取时返回不同的 hashcode 的话,就不能从 HashMap 中找到你想要的对象。
6. 如果HashMap的大小超过了负载因子(load factor)定义的容量怎么办?:扩容:resize() & rehash()「注意,resize()的效率非常低!!!」所以如果预先知道有一个很大的表要创建,那么可以预先再创建时,就指定一个较大的空间,相当于时 **空间换时间**;避免未来的频繁resize()花费很多时间。
##
***
# 11.红黑树:自己补充
![截屏2020-06-23上午12.50.42](/Users/huangshengjie/Desktop/截屏2020-06-23上午12.50.42.png)
* [B站课程](https://www.bilibili.com/video/BV1tE411f7tP?from=search&seid=2421763921920035607):
* [一份链接文章](https://blog.csdn.net/Mr_Helloworld_/article/details/106694724)
* ![image-20200624005349275](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183236.png)
* ![image-20200624005402070](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183237.png)
* ![image-20200624005251467](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183238.png)
***
# 12.正题:001:两数之和:Java版
```java
import java.util.*;
public class twoSum_001 {
public static void main(String[] args) {
}
//暴力法
public int[] twoSum_force(int[] nums, int target){
for(int i=0;i< nums.length;i++){
for(int j=i+1;j< nums.length;j++){
if(nums[j] == target - nums[i]){
return new int[] {i, j};
}
}
}
throw new IllegalArgumentException("No two sum soluition");
}
//两遍 Hash,一遍存,一遍查取;
public int[] twoSum_HashTwice(int[] nums, int target){
Map<Integer, Integer> map = new HashMap<>();
for(int i=0;i< nums.length;i++){
map.put(nums[i],i);
}
for(int i=0; i<nums.length;i++){
int complement = target - nums[i];
if(map.containsKey(complement) && map.get(complement) != i){
return new int[]{i,map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
//一遍 Hash,先查,查不到就接着存;
public int[] twoSum_HashOnce(int[] nums, int target){
Map<Integer, Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int complemenmt = target - nums[i];
if(map.containsKey(complemenmt)){
return new int[]{i,map.get(complemenmt)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution.");
}
}