Skip to content

Commit a13ee7d

Browse files
dunwudunwu
committed
🔖 Hash 示例
1 parent 96fa41f commit a13ee7d

File tree

2 files changed

+162
-2
lines changed

2 files changed

+162
-2
lines changed

‎codes/pom.xml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99

1010
<!-- MAVEN COORDINATE BEGIN -->
1111
<groupId>io.github.dunwu</groupId>
12-
<artifactId>algorithms-notes</artifactId>
12+
<artifactId>algorithms</artifactId>
1313
<version>1.0.1</version>
1414
<packaging>jar</packaging>
1515
<!-- MAVEN COORDINATE END -->
@@ -57,7 +57,7 @@
5757

5858

5959
<!-- [Part 3] PROJECT INFO BEGIN -->
60-
<name>${project.artifactId}</name>
60+
<name>${artifactId}</name>
6161
<description>算法+数据结构学习笔记</description>
6262
<url>https://github.com/dunwu/algorithms-notes</url>
6363
<inceptionYear>2016-2017</inceptionYear>

‎codes/src/main/java/io/github/dunwu/algorithm/hash/HashDemo.java‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
package io.github.dunwu.algorithm.hash;
2+
3+
/**
4+
* 为了精简示例代码，所有参数都用 public
5+
*/
6+
@SuppressWarnings("all")
7+
class HashTable {
8+
public int key = 0; // 关键字
9+
public int data = 0; // 数值
10+
public int count = 0; // 探查次数
11+
}
12+
13+
/**
14+
* Hash 表查找示例
15+
*
16+
* @author Zhang Peng
17+
*/
18+
public class HashDemo {
19+
20+
private final static int MAXSIZE = 13;
21+
private final static int MODULO = 13;
22+
private final static int NULLKEY = 1;
23+
private final static int DELKEY = 2;
24+
private final static int SUCCESS = 0;
25+
private final static int FAILED = 0xFFFFFFFF;
26+
27+
/**
28+
* 查找哈希表
29+
* 构造哈希表采用除留取余法，即f(key) = key mod p (p ≤ size)
30+
* 解决冲突采用开放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
31+
* ha为哈希表，p为模，size为哈希表大小，key为要查找的关键字
32+
*/
33+
private int searchHashTable(HashTable[] ha, int p, int size, int key) {
34+
// 采用除留取余法找哈希地址
35+
int addr = key % p;
36+
37+
// 若发生冲突，用开放定址法找下一个哈希地址
38+
while (ha[addr].key != NULLKEY && ha[addr].key != key) {
39+
addr = (addr + 1) % size;
40+
}
41+
42+
if (ha[addr].key == key) {
43+
// 查找成功
44+
return addr;
45+
} else {
46+
// 查找失败
47+
return FAILED;
48+
}
49+
}
50+
51+
/**
52+
* 删除哈希表中关键字为key的记录
53+
* 找到要删除的记录，将关键字置为删除标记DELKEY
54+
*/
55+
public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
56+
int addr = 0;
57+
addr = searchHashTable(ha, p, size, key);
58+
if (FAILED != addr) {
59+
// 将该位置的关键字置为DELKEY
60+
ha[addr].key = DELKEY;
61+
return SUCCESS;
62+
} else {
63+
// 查找不到记录，直接返回NULLKEY
64+
return NULLKEY;
65+
}
66+
}
67+
68+
/**
69+
* 将待插入的关键字key插入哈希表
70+
* 先调用查找算法，若在表中找到待插入的关键字，则插入失败；
71+
* 若在表中找到一个开放地址，则将待插入的结点插入到其中，则插入成功。
72+
*/
73+
private void insertHashTable(HashTable[] ha, int p, int size, int key) {
74+
int i = 1;
75+
int addr = 0;
76+
// 通过哈希函数获取哈希地址
77+
addr = key % p;
78+
// 如果没有冲突，直接插入
79+
if (ha[addr].key == NULLKEY || ha[addr].key == DELKEY) {
80+
ha[addr].key = key;
81+
ha[addr].count = 1;
82+
// 如果有冲突，使用开放定址法处理冲突
83+
} else {
84+
do {
85+
// 寻找下一个哈希地址
86+
addr = (addr + 1) % size;
87+
i++;
88+
} while (ha[addr].key != NULLKEY && ha[addr].key != DELKEY);
89+
90+
ha[addr].key = key;
91+
ha[addr].count = i;
92+
}
93+
}
94+
95+
/**
96+
* 创建哈希表
97+
* 先将哈希表中各关键字清空，使其地址为开放的，然后调用插入算法将给定的关键字序列依次插入。
98+
*/
99+
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
100+
int i = 0;
101+
102+
// 将哈希表中的所有关键字清空
103+
for (i = 0; i < ha.length; i++) {
104+
ha[i].key = NULLKEY;
105+
ha[i].count = 0;
106+
}
107+
108+
// 将关键字序列依次插入哈希表中
109+
for (i = 0; i < list.length; i++) {
110+
this.insertHashTable(ha, p, size, list[i]);
111+
}
112+
}
113+
114+
/**
115+
* 输出哈希表
116+
*/
117+
private void displayHashTable(HashTable[] ha) {
118+
int i = 0;
119+
System.out.format("pos:\t", "pos");
120+
for (i = 0; i < ha.length; i++) {
121+
System.out.format("%4d", i);
122+
}
123+
System.out.println();
124+
125+
System.out.format("key:\t");
126+
for (i = 0; i < ha.length; i++) {
127+
if (ha[i].key != NULLKEY) {
128+
System.out.format("%4d", ha[i].key);
129+
} else {
130+
System.out.format(" ");
131+
}
132+
}
133+
System.out.println();
134+
135+
System.out.format("count:\t");
136+
for (i = 0; i < ha.length; i++) {
137+
if (0 != ha[i].count) {
138+
System.out.format("%4d", ha[i].count);
139+
} else {
140+
System.out.format(" ");
141+
}
142+
}
143+
System.out.println();
144+
}
145+
146+
public static void main(String[] args) {
147+
// int[] list = {3, 112, 245, 27, 44, 19, 76, 29, 90};
148+
int[] list = {1, 9, 25, 11, 12, 35, 17, 29};
149+
HashTable[] ha = new HashTable[MAXSIZE];
150+
for (int i = 0; i < ha.length; i++) {
151+
ha[i] = new HashTable();
152+
}
153+
154+
HashDemo search = new HashDemo();
155+
search.createHashTable(ha, list, MODULO, MAXSIZE);
156+
search.displayHashTable(ha);
157+
158+
}
159+
160+
}

0 commit comments

Comments
 (0)