Skip to content

Commit 6e5f41a

Browse files
fuzhengweifuzhengwei
committed
小傅哥，文章代码更新。晚上好😄
1 parent 055e2b5 commit 6e5f41a

File tree

18 files changed

+345
-0
lines changed

18 files changed

+345
-0
lines changed

‎interview-01/interview-01.iml

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module org.jetbrains.idea.maven.project.MavenProjectsManager.isMavenModule="true" type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" LANGUAGE_LEVEL="JDK_1_5">
4+
<output url="file://$MODULE_DIR$/target/classes" />
5+
<output-test url="file://$MODULE_DIR$/target/test-classes" />
6+
<content url="file://$MODULE_DIR$">
7+
<sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" />
8+
<sourceFolder url="file://$MODULE_DIR$/src/main/resources" type="java-resource" />
9+
<sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" />
10+
<excludeFolder url="file://$MODULE_DIR$/target" />
11+
</content>
12+
<orderEntry type="inheritedJdk" />
13+
<orderEntry type="sourceFolder" forTests="false" />
14+
<orderEntry type="library" scope="TEST" name="Maven: junit:junit:4.12" level="project" />
15+
<orderEntry type="library" scope="TEST" name="Maven: org.hamcrest:hamcrest-core:1.3" level="project" />
16+
</component>
17+
</module>

‎interview-01/pom.xml

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
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-01</artifactId>
13+
<dependencies>
14+
<dependency>
15+
<groupId>junit</groupId>
16+
<artifactId>junit</artifactId>
17+
<version>4.12</version>
18+
<scope>test</scope>
19+
</dependency>
20+
</dependencies>
21+
22+
23+
</project>

‎interview-01/src/main/java/org/itstack/interview/T.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package org.itstack.interview;
2+
3+
/**
4+
* 博客：https://bugstack.cn - 沉淀、分享、成长，让自己和他人都能有所收获！
5+
* 公众号：bugstack虫洞栈
6+
* Create by 小傅哥(fustack) @2020
7+
*/
8+
public class T
9+
{
10+
}

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package org.itstack.interview.test;
2+
3+
4+
public class ApiTest {
5+
6+
7+
}

‎interview-01/服务端技术面试总结.xmind

6.18 MB
Binary file not shown.

‎interview-02/interview-02.iml

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+
<module org.jetbrains.idea.maven.project.MavenProjectsManager.isMavenModule="true" type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" LANGUAGE_LEVEL="JDK_1_5">
4+
<output url="file://$MODULE_DIR$/target/classes" />
5+
<output-test url="file://$MODULE_DIR$/target/test-classes" />
6+
<content url="file://$MODULE_DIR$">
7+
<sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" />
8+
<sourceFolder url="file://$MODULE_DIR$/src/main/resources" type="java-resource" />
9+
<sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" />
10+
<excludeFolder url="file://$MODULE_DIR$/target" />
11+
</content>
12+
<orderEntry type="inheritedJdk" />
13+
<orderEntry type="sourceFolder" forTests="false" />
14+
</component>
15+
</module>

‎interview-02/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-02</artifactId>
13+
14+
15+
</project>

‎interview-02/src/main/java/org/itstack/interview/T.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package org.itstack.interview;
2+
3+
/**
4+
* 博客：https://bugstack.cn - 沉淀、分享、成长，让自己和他人都能有所收获！
5+
* 公众号：bugstack虫洞栈
6+
* Create by 小傅哥(fustack) @2020
7+
*/
8+
public class T
9+
{
10+
}

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

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package org.itstack.interview.test;
2+
3+
4+
public class ApiTest {
5+
6+
7+
}

‎interview-02/技术框架.pptx

52.2 KB
Binary file not shown.

‎interview-03/103976个英语单词库.txt

Lines changed: 1 addition & 0 deletions
Large diffs are not rendered by default.

‎interview-03/HashCode散列分布.xlsx

40.7 KB
Binary file not shown.

‎interview-03/interview-03.iml

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+
<module org.jetbrains.idea.maven.project.MavenProjectsManager.isMavenModule="true" type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" LANGUAGE_LEVEL="JDK_1_5">
4+
<output url="file://$MODULE_DIR$/target/classes" />
5+
<output-test url="file://$MODULE_DIR$/target/test-classes" />
6+
<content url="file://$MODULE_DIR$">
7+
<sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" />
8+
<sourceFolder url="file://$MODULE_DIR$/src/main/resources" type="java-resource" />
9+
<sourceFolder url="file://$MODULE_DIR$/src/test/java" isTestSource="true" />
10+
<excludeFolder url="file://$MODULE_DIR$/target" />
11+
</content>
12+
<orderEntry type="inheritedJdk" />
13+
<orderEntry type="sourceFolder" forTests="false" />
14+
</component>
15+
</module>

‎interview-03/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-03</artifactId>
13+
14+
15+
</project>

‎interview-03/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-03/src/main/java/org/itstack/interview/HashCode.java

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package org.itstack.interview;
2+
3+
import java.util.*;
4+
5+
public class HashCode {
6+
7+
/**
8+
* public int hashCode() {
9+
* int h = hash;
10+
* if (h == 0 && value.length > 0) {
11+
* char val[] = value;
12+
* for (int i = 0; i < value.length; i++) {
13+
* h = 31 * h + val[i];
14+
* }
15+
* hash = h;
16+
* }
17+
* return h;
18+
* }
19+
*/
20+
public static Integer hashCode(String str, Integer multiplier) {
21+
int hash = 0;
22+
for (int i = 0; i < str.length(); i++) {
23+
hash = multiplier * hash + str.charAt(i);
24+
}
25+
return hash;
26+
}
27+
28+
/**
29+
* 计算Hash碰撞概率
30+
*/
31+
private static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashCodeList) {
32+
int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
33+
int minHash = hashCodeList.stream().min(Integer::compareTo).get();
34+
35+
int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
36+
double collisionRate = (collisionCount * 1.0) / hashCodeList.size();
37+
38+
return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
39+
}
40+
41+
public static List<RateInfo> collisionRateList(Set<String> strList, Integer... multipliers) {
42+
List<RateInfo> rateInfoList = new ArrayList<>();
43+
for (Integer multiplier : multipliers) {
44+
List<Integer> hashCodeList = new ArrayList<>();
45+
for (String str : strList) {
46+
Integer hashCode = hashCode(str, multiplier);
47+
hashCodeList.add(hashCode);
48+
}
49+
rateInfoList.add(hashCollisionRate(multiplier, hashCodeList));
50+
}
51+
return rateInfoList;
52+
}
53+
54+
public static Map<Integer, Integer> hashArea(List<Integer> hashCodeList) {
55+
Map<Integer, Integer> statistics = new LinkedHashMap<>();
56+
int start = 0;
57+
for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
58+
long min = i;
59+
long max = min + 67108864;
60+
// 筛选出每个格子里的哈希值数量，java8流统计；https://bugstack.cn/itstack-demo-any/2019/12/10/%E6%9C%89%E7%82%B9%E5%B9%B2%E8%B4%A7-Jdk1.8%E6%96%B0%E7%89%B9%E6%80%A7%E5%AE%9E%E6%88%98%E7%AF%87(41%E4%B8%AA%E6%A1%88%E4%BE%8B).html
61+
int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
62+
statistics.put(start++, num);
63+
}
64+
return statistics;
65+
}
66+
67+
public static Map<Integer, Integer> hashArea(Set<String> strList, Integer multiplier){
68+
List<Integer> hashCodeList = new ArrayList<>();
69+
for (String str : strList) {
70+
Integer hashCode = hashCode(str, multiplier);
71+
hashCodeList.add(hashCode);
72+
}
73+
return hashArea(hashCodeList);
74+
}
75+
76+
}

‎interview-03/src/main/java/org/itstack/interview/RateInfo.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package org.itstack.interview;
2+
3+
public class RateInfo {
4+
5+
private int maxHash; // 最大Hash
6+
private int minHash; // 最小Hash
7+
private int multiplier; // hash计算乘机因子
8+
private int collisionCount; // 碰撞数
9+
private double collisionRate; // 碰撞比率
10+
11+
public RateInfo(int maxHash, int minHash, int multiplier, int collisionCount, double collisionRate) {
12+
this.maxHash = maxHash;
13+
this.minHash = minHash;
14+
this.multiplier = multiplier;
15+
this.collisionCount = collisionCount;
16+
this.collisionRate = collisionRate;
17+
}
18+
19+
public int getMaxHash() {
20+
return maxHash;
21+
}
22+
23+
public void setMaxHash(int maxHash) {
24+
this.maxHash = maxHash;
25+
}
26+
27+
public int getMinHash() {
28+
return minHash;
29+
}
30+
31+
public void setMinHash(int minHash) {
32+
this.minHash = minHash;
33+
}
34+
35+
public int getMultiplier() {
36+
return multiplier;
37+
}
38+
39+
public void setMultiplier(int multiplier) {
40+
this.multiplier = multiplier;
41+
}
42+
43+
public int getCollisionCount() {
44+
return collisionCount;
45+
}
46+
47+
public void setCollisionCount(int collisionCount) {
48+
this.collisionCount = collisionCount;
49+
}
50+
51+
public double getCollisionRate() {
52+
return collisionRate;
53+
}
54+
55+
public void setCollisionRate(double collisionRate) {
56+
this.collisionRate = collisionRate;
57+
}
58+
}

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package org.itstack.interview.test;
2+
3+
import org.itstack.interview.FileUtil;
4+
import org.itstack.interview.HashCode;
5+
import org.itstack.interview.RateInfo;
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+
"abc".hashCode();
18+
// 读取文件，103976个英语单词库.txt
19+
words = FileUtil.readWordList("E:/itstack/git/github.com/interview/interview-01/103976个英语单词库.txt");
20+
}
21+
22+
@Test
23+
public void test_collisionRate() {
24+
System.out.println("单词数量：" + words.size());
25+
List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
26+
for (RateInfo rate : rateInfoList) {
27+
System.out.println(String.format("乘数 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞数量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
28+
}
29+
}
30+
31+
@Test
32+
public void test_hashArea() {
33+
System.out.println(HashCode.hashArea(words, 2).values());
34+
System.out.println(HashCode.hashArea(words, 7).values());
35+
System.out.println(HashCode.hashArea(words, 31).values());
36+
System.out.println(HashCode.hashArea(words, 32).values());
37+
System.out.println(HashCode.hashArea(words, 199).values());
38+
}
39+
40+
}

0 commit comments

Comments
 (0)