Skip to content

Commit b4ec05e

Browse files
fuzhengweifuzhengwei
committed
小傅哥，文章代码更新。晚上好
面经手册 · 第3篇《HashMap核心知识，扰动函数、负载因子、扩容链表拆分，深度学习》
1 parent 156b7fc commit b4ec05e

File tree

12 files changed

+215
-0
lines changed

12 files changed

+215
-0
lines changed

‎.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1 +1,2 @@
11
/interview.iml
2+
/interview-04/interview-04.iml

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,5 @@
1111
1. [面经手册 · 开篇《面试官都问我啥》](https://bugstack.cn/interview/2020/07/28/%E9%9D%A2%E7%BB%8F%E6%89%8B%E5%86%8C-%E5%BC%80%E7%AF%87-%E9%9D%A2%E8%AF%95%E5%AE%98%E9%83%BD%E9%97%AE%E6%88%91%E5%95%A5.html)
1212
2. [面经手册 · 第1篇《认知自己的技术栈盲区》](https://bugstack.cn/interview/2020/07/30/%E9%9D%A2%E7%BB%8F%E6%89%8B%E5%86%8C-%E7%AC%AC1%E7%AF%87-%E8%AE%A4%E7%9F%A5%E8%87%AA%E5%B7%B1%E7%9A%84%E6%8A%80%E6%9C%AF%E6%A0%88%E7%9B%B2%E5%8C%BA.html)
1313
3. [面经手册 · 第2篇《数据结构，HashCode为什么使用31作为乘数？》](https://bugstack.cn/interview/2020/08/04/%E9%9D%A2%E7%BB%8F%E6%89%8B%E5%86%8C-%E7%AC%AC2%E7%AF%87-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-HashCode%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BD%BF%E7%94%A831%E4%BD%9C%E4%B8%BA%E4%B9%98%E6%95%B0.html)
14+
4. [面经手册 · 第3篇《HashMap核心知识，扰动函数、负载因子、扩容链表拆分，深度学习》](https://bugstack.cn/interview/2020/08/07/%E9%9D%A2%E7%BB%8F%E6%89%8B%E5%86%8C-%E7%AC%AC3%E7%AF%87-HashMap%E6%A0%B8%E5%BF%83%E7%9F%A5%E8%AF%86-%E6%89%B0%E5%8A%A8%E5%87%BD%E6%95%B0-%E8%B4%9F%E8%BD%BD%E5%9B%A0%E5%AD%90-%E6%89%A9%E5%AE%B9%E9%93%BE%E8%A1%A8%E6%8B%86%E5%88%86-%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0.html)
1415

‎技术框架.pptx renamed to ‎docs/技术框架.pptx

File renamed without changes.

‎面试总结.xmind renamed to ‎docs/面试总结.xmind

File renamed without changes.

‎interview-01/interview-01.iml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,5 +13,6 @@
1313
<orderEntry type="sourceFolder" forTests="false" />
1414
<orderEntry type="library" scope="TEST" name="Maven: junit:junit:4.12" level="project" />
1515
<orderEntry type="library" scope="TEST" name="Maven: org.hamcrest:hamcrest-core:1.3" level="project" />
16+
<orderEntry type="library" name="Maven: com.alibaba:fastjson:1.2.73" level="project" />
1617
</component>
1718
</module>

‎interview-02/interview-02.iml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,5 +11,6 @@
1111
</content>
1212
<orderEntry type="inheritedJdk" />
1313
<orderEntry type="sourceFolder" forTests="false" />
14+
<orderEntry type="library" name="Maven: com.alibaba:fastjson:1.2.73" level="project" />
1415
</component>
1516
</module>

‎interview-03/interview-03.iml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,5 +11,6 @@
1111
</content>
1212
<orderEntry type="inheritedJdk" />
1313
<orderEntry type="sourceFolder" forTests="false" />
14+
<orderEntry type="library" name="Maven: com.alibaba:fastjson:1.2.73" level="project" />
1415
</component>
1516
</module>

‎interview-04/pom.xml

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>interview</artifactId>
7+
<groupId>org.itstack</groupId>
8+
<version>1.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<artifactId>interview-04</artifactId>
13+
14+
15+
</project>

‎interview-04/src/main/java/org/itstack/interview/Disturb.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package org.itstack.interview;
2+
3+
public class Disturb {
4+
5+
public static int disturbHashIdx(String key, int size) {
6+
return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
7+
}
8+
9+
public static int hashIdx(String key, int size) {
10+
return (size - 1) & key.hashCode();
11+
}
12+
13+
}

‎interview-04/src/main/java/org/itstack/interview/FileUtil.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package org.itstack.interview;
2+
3+
import java.io.BufferedReader;
4+
import java.io.FileInputStream;
5+
import java.io.InputStreamReader;
6+
import java.nio.charset.StandardCharsets;
7+
import java.util.HashSet;
8+
import java.util.Set;
9+
10+
public class FileUtil {
11+
12+
/**
13+
* 读取本地文件，单词表
14+
* @param url 单词表.txt文件
15+
* @return 单词集合(去重)
16+
*/
17+
public static Set<String> readWordList(String url) {
18+
Set<String> list = new HashSet<>();
19+
try {
20+
InputStreamReader isr = new InputStreamReader(new FileInputStream(url), StandardCharsets.UTF_8);
21+
BufferedReader br = new BufferedReader(isr);
22+
String line = "";
23+
while ((line = br.readLine()) != null) {
24+
String[] ss = line.split("\t");
25+
list.add(ss[1]);
26+
}
27+
br.close();
28+
isr.close();
29+
} catch (Exception ignore) {
30+
return null;
31+
}
32+
return list;
33+
}
34+
35+
36+
}

‎interview-04/src/test/java/org/itstack/interview/test/ApiTest.java

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
package org.itstack.interview.test;
2+
3+
import com.alibaba.fastjson.JSON;
4+
import org.itstack.interview.Disturb;
5+
import org.itstack.interview.FileUtil;
6+
import org.junit.Before;
7+
import org.junit.Test;
8+
9+
import java.util.*;
10+
11+
public class ApiTest {
12+
13+
private Set<String> words;
14+
15+
@Before
16+
public void before() {
17+
// 读取文件，103976个英语单词库.txt
18+
words = FileUtil.readWordList("E:/itstack/git/github.com/interview/doc/103976个英语单词库.txt");
19+
}
20+
21+
@Test
22+
public void test_disturb() {
23+
Map<Integer, Integer> map = new HashMap<>(16);
24+
for (String word : words) {
25+
// 使用扰动函数
26+
int idx = Disturb.disturbHashIdx(word, 128);
27+
// 不使用扰动函数
28+
// int idx = Disturb.hashIdx(word, 128);
29+
if (map.containsKey(idx)) {
30+
Integer integer = map.get(idx);
31+
map.put(idx, ++integer);
32+
} else {
33+
map.put(idx, 1);
34+
}
35+
}
36+
System.out.println(map.values());
37+
}
38+
39+
40+
@Test
41+
public void test_threshold() {
42+
System.out.println(tableSizeFor(17));
43+
}
44+
45+
static int tableSizeFor(int cap) {
46+
int n = cap - 1;
47+
System.out.println(Integer.toBinaryString(n));
48+
n |= n >>> 1;
49+
System.out.println(Integer.toBinaryString(n));
50+
n |= n >>> 2;
51+
System.out.println(Integer.toBinaryString(n));
52+
n |= n >>> 4;
53+
System.out.println(Integer.toBinaryString(n));
54+
n |= n >>> 8;
55+
System.out.println(Integer.toBinaryString(n));
56+
n |= n >>> 16;
57+
System.out.println(Integer.toBinaryString(n));
58+
return (n < 0) ? 1 : (n >= (1 << 30)) ? (1 << 30) : n + 1;
59+
}
60+
61+
@Test
62+
public void test_hashMapSize() {
63+
Map<String, String> map = new HashMap<>(17);
64+
System.out.println(map.keySet().size());
65+
}
66+
67+
@Test
68+
public void test_hashMap() {
69+
List<String> list = new ArrayList<>();
70+
list.add("jlkk");
71+
list.add("lopi");
72+
list.add("jmdw");
73+
list.add("e4we");
74+
list.add("io98");
75+
list.add("nmhg");
76+
list.add("vfg6");
77+
list.add("gfrt");
78+
list.add("alpo");
79+
list.add("vfbh");
80+
list.add("bnhj");
81+
list.add("zuio");
82+
list.add("iu8e");
83+
list.add("yhjk");
84+
list.add("plop");
85+
list.add("dd0p");
86+
87+
for (String key : list) {
88+
int hash = key.hashCode() ^ (key.hashCode() >>> 16);
89+
System.out.println("字符串：" + key + " \tIdx(16)：" + ((16 - 1) & hash) + " \tBit值：" + Integer.toBinaryString(hash) + " - " + Integer.toBinaryString(hash & 16) + " \t\tIdx(32)：" + ((32 - 1) & hash));
90+
System.out.println(Integer.toBinaryString(key.hashCode()) +" "+ Integer.toBinaryString(hash) + " " + Integer.toBinaryString((32 - 1) & hash));
91+
}
92+
}
93+
94+
95+
@Test
96+
public void t() {
97+
System.out.println(Integer.toBinaryString("小傅哥".hashCode()));
98+
System.out.println(Integer.toBinaryString("小傅哥".hashCode() ^ ("小傅哥".hashCode() >>> 16)));
99+
}
100+
101+
@Test
102+
public void test_128hash() {
103+
104+
// 初始化一组字符串
105+
List<String> list = new ArrayList<>();
106+
list.add("jlkk");
107+
list.add("lopi");
108+
list.add("小傅哥");
109+
list.add("e4we");
110+
list.add("alpo");
111+
list.add("yhjk");
112+
list.add("plop");
113+
114+
// 定义要存放的数组
115+
String[] tab = new String[8];
116+
117+
// 循环存放
118+
for (String key : list) {
119+
int idx = key.hashCode() & (tab.length - 1); // 计算索引位置
120+
System.out.println(String.format("key值=%s Idx=%d", key, idx));
121+
if (null == tab[idx]) {
122+
tab[idx] = key;
123+
continue;
124+
}
125+
tab[idx] = tab[idx] + "->" + key;
126+
}
127+
128+
// 输出测试结果
129+
System.out.println("测试结果：" + JSON.toJSONString(tab));
130+
131+
}
132+
133+
}
134+
135+
//011000
136+
//011111
137+
//
138+
//011000

‎pom.xml

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,15 @@
1212
<module>interview-01</module>
1313
<module>interview-02</module>
1414
<module>interview-03</module>
15+
<module>interview-04</module>
1516
</modules>
1617

18+
<dependencies>
19+
<dependency>
20+
<groupId>com.alibaba</groupId>
21+
<artifactId>fastjson</artifactId>
22+
<version>1.2.73</version>
23+
</dependency>
24+
</dependencies>
1725

1826
</project>

0 commit comments

Comments
 (0)