Skip to content

Commit 173b828

Browse files
author
chenweijie
committed
adjust
1 parent 09d09f4 commit 173b828

File tree

12 files changed

+615
-7
lines changed

12 files changed

+615
-7
lines changed

‎src/main/java/com/chen/algorithm/exercise/ArraySearch.java renamed to ‎src/main/java/com/chen/algorithm/exercise/exercise1/ArraySearch.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.chen.algorithm.exercise;
1+
package com.chen.algorithm.exercise.exercise1;
22

33

44
/**

‎src/main/java/com/chen/algorithm/exercise/ReplaceSpace.java renamed to ‎src/main/java/com/chen/algorithm/exercise/exercise2/ReplaceSpace.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.chen.algorithm.exercise;
1+
package com.chen.algorithm.exercise.exercise2;
22

33
/**
44
* 请实现一个函数，将一个字符串中的每个空格替换成“%20”。

‎src/main/java/com/chen/algorithm/exercise/PrintLinkList.java renamed to ‎src/main/java/com/chen/algorithm/exercise/exercise3/PrintLinkList.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.chen.algorithm.exercise;
1+
package com.chen.algorithm.exercise.exercise3;
22

33
import java.util.ArrayList;
44

‎src/main/java/com/chen/dataStructure/hash/HashChain.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package com.chen.dataStructure.hash;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2019-04-14 01:48
6+
*/
7+
public class HashChain {
8+
9+
/**
10+
* 数组中存放链表
11+
*/
12+
private SortLink[] hashArray;
13+
14+
private int arraySize;
15+
16+
public HashChain(int size){
17+
arraySize = size;
18+
hashArray = new SortLink[arraySize];
19+
//new 出每个空链表初始化数组
20+
for(int i = 0 ; i < arraySize ; i++){
21+
hashArray[i] = new SortLink();
22+
}
23+
}
24+
25+
public void displayTable(){
26+
for(int i = 0 ; i < arraySize ; i++){
27+
System.out.print(i + "：");
28+
hashArray[i].displayLink();
29+
}
30+
}
31+
32+
public int hashFunction(int key) {
33+
return key % arraySize;
34+
}
35+
36+
public void insert(SortLink.LinkNode node) {
37+
int key = node.getKey();
38+
int hashVal = hashFunction(key);
39+
//直接往链表中添加即可
40+
hashArray[hashVal].insert(node);
41+
}
42+
43+
public SortLink.LinkNode delete(int key){
44+
int hashVal = hashFunction(key);
45+
SortLink.LinkNode temp = find(key);
46+
//从链表中找到要删除的数据项，直接删除
47+
hashArray[hashVal].delete(key);
48+
return temp;
49+
}
50+
51+
public SortLink.LinkNode find(int key){
52+
int hashVal = hashFunction(key);
53+
SortLink.LinkNode node = hashArray[hashVal].find(key);
54+
return node;
55+
}
56+
57+
58+
59+
60+
61+
62+
63+
64+
65+
66+
67+
68+
69+
70+
71+
}

‎src/main/java/com/chen/dataStructure/hash/HashDouble.java

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
package com.chen.dataStructure.hash;
2+
3+
/**
4+
* 再hash算法
5+
* @author : chen weijie
6+
* @Date: 2019-04-14 01:34
7+
*/
8+
public class HashDouble {
9+
10+
private DataItem[] hashArray; //DataItem类，表示每个数据项信息
11+
private int arraySize;//数组的初始大小
12+
private int itemNum;//数组实际存储了多少项数据
13+
private DataItem nonItem;//用于删除数据项
14+
15+
public HashDouble(){
16+
this.arraySize = 13;
17+
hashArray = new DataItem[arraySize];
18+
nonItem = new DataItem(-1);//删除的数据项下标为-1
19+
}
20+
21+
public static class DataItem{
22+
private int iData;
23+
public DataItem(int iData){
24+
this.iData = iData;
25+
}
26+
public int getKey(){
27+
return iData;
28+
}
29+
}
30+
31+
//判断数组是否存储满了
32+
public boolean isFull(){
33+
return (itemNum == arraySize);
34+
}
35+
36+
//判断数组是否为空
37+
public boolean isEmpty(){
38+
return (itemNum == 0);
39+
}
40+
41+
//打印数组内容
42+
public void display(){
43+
System.out.println("Table:");
44+
for(int j = 0 ; j < arraySize ; j++){
45+
if(hashArray[j] != null){
46+
System.out.print(hashArray[j].getKey() + " ");
47+
}else{
48+
System.out.print("** ");
49+
}
50+
}
51+
}
52+
53+
//通过哈希函数转换得到数组下标
54+
public int hashFunction1(int key){
55+
return key%arraySize;
56+
}
57+
58+
public int hashFunction2(int key){
59+
return 5 - key%5;
60+
}
61+
62+
/**
63+
* 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。
64+
* 但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上。
65+
* 因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。
66+
* 这个过程叫做重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。
67+
*/
68+
public void extendHashTable(){
69+
int num = arraySize;
70+
itemNum = 0;//重新计数，因为下面要把原来的数据转移到新的扩张的数组中
71+
arraySize *= 2;//数组大小翻倍
72+
DataItem[] oldHashArray = hashArray;
73+
hashArray = new DataItem[arraySize];
74+
for(int i = 0 ; i < num ; i++){
75+
insert(oldHashArray[i]);
76+
}
77+
}
78+
79+
//插入数据项
80+
public void insert(DataItem item){
81+
if(isFull()){
82+
//扩展哈希表
83+
System.out.println("哈希表已满，重新哈希化...");
84+
extendHashTable();
85+
}
86+
int key = item.getKey();
87+
int hashVal = hashFunction1(key);
88+
int stepSize = hashFunction2(key);//用第二个哈希函数计算探测步数
89+
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
90+
hashVal += stepSize;
91+
hashVal %= arraySize;//以指定的步数向后探测
92+
}
93+
hashArray[hashVal] = item;
94+
itemNum++;
95+
}
96+
97+
98+
//删除数据项
99+
public DataItem delete(int key){
100+
if(isEmpty()){
101+
System.out.println("Hash Table is Empty!");
102+
return null;
103+
}
104+
int hashVal = hashFunction1(key);
105+
int stepSize = hashFunction2(key);
106+
while(hashArray[hashVal] != null){
107+
if(hashArray[hashVal].getKey() == key){
108+
DataItem temp = hashArray[hashVal];
109+
hashArray[hashVal] = nonItem;//nonItem表示空Item,其key为-1
110+
itemNum--;
111+
return temp;
112+
}
113+
hashVal += stepSize;
114+
hashVal %= arraySize;
115+
}
116+
return null;
117+
}
118+
119+
//查找数据项
120+
public DataItem find(int key){
121+
int hashVal = hashFunction1(key);
122+
int stepSize = hashFunction2(key);
123+
while(hashArray[hashVal] != null){
124+
if(hashArray[hashVal].getKey() == key){
125+
return hashArray[hashVal];
126+
}
127+
hashVal += stepSize;
128+
hashVal %= arraySize;
129+
}
130+
return null;
131+
}
132+
133+
134+
135+
136+
}

‎src/main/java/com/chen/dataStructure/hash/MyHashTable.java

Lines changed: 171 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,171 @@
1+
package com.chen.dataStructure.hash;
2+
3+
/**
4+
* 线性探测
5+
* @author : chen weijie
6+
* @Date: 2019-04-14 00:56
7+
*/
8+
public class MyHashTable {
9+
10+
/**
11+
* DataItem类，表示每个数据项信息
12+
*/
13+
private DataItem [] hashArray;
14+
15+
/**
16+
* 数组的初始大小
17+
*/
18+
private int arraySize;
19+
20+
/**
21+
* 数组实际存储了多少项数据
22+
*/
23+
private int itemNum;
24+
25+
26+
/**
27+
* 用于删除数据项
28+
*/
29+
private DataItem nonItem;
30+
31+
32+
public MyHashTable(int arraySize){
33+
this.arraySize = arraySize;
34+
hashArray = new DataItem[arraySize];
35+
//删除的数据项下标为-1
36+
nonItem = new DataItem(-1);
37+
}
38+
39+
/**
40+
* 判断数组是否存储满了
41+
*/
42+
public boolean isFull(){
43+
return (itemNum == arraySize);
44+
}
45+
46+
//判断数组是否为空
47+
public boolean isEmpty(){
48+
return (itemNum == 0);
49+
}
50+
51+
//打印数组内容
52+
public void display(){
53+
System.out.println("Table:");
54+
for(int j = 0 ; j < arraySize ; j++){
55+
if(hashArray[j] != null){
56+
System.out.print(hashArray[j].getKey() + " ");
57+
}else{
58+
System.out.print("** ");
59+
}
60+
}
61+
}
62+
63+
//通过哈希函数转换得到数组下标
64+
public int hashFunction(int key) {
65+
return key % arraySize;
66+
}
67+
68+
69+
/**
70+
* 查找关键值
71+
*
72+
* @param key
73+
* @return
74+
*/
75+
public DataItem find(int key) {
76+
77+
int hashVal = hashFunction(key);
78+
while (hashArray[hashVal] != null) {
79+
if (hashArray[hashVal].getKey() == key) {
80+
return hashArray[hashVal];
81+
}
82+
++hashVal;
83+
hashVal %= arraySize;
84+
}
85+
return null;
86+
}
87+
88+
/**
89+
* 插入数据项
90+
*
91+
* @param item
92+
*/
93+
public void insert(DataItem item) {
94+
95+
if (isFull()) {
96+
//扩展哈希表
97+
System.out.println("哈希表已满，重新哈希化...");
98+
extendHashTable();
99+
}
100+
101+
102+
int key = item.getKey();
103+
int hashVal = hashFunction(key);
104+
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
105+
++hashVal;
106+
hashVal %= arraySize;
107+
}
108+
hashArray[hashVal] = item;
109+
itemNum++;
110+
}
111+
112+
/**
113+
* 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。
114+
* 但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上。
115+
* 因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。
116+
* 这个过程叫做重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。
117+
*/
118+
public void extendHashTable() {
119+
120+
int num = arraySize;
121+
//重新计数，因为下面要把原来的数据转移到新的扩张的数组中
122+
itemNum = 0;
123+
arraySize *= 2;
124+
DataItem[] oldHashArray = hashArray;
125+
hashArray = new DataItem[arraySize];
126+
127+
for (int i = 0; i < num; i++) {
128+
insert(oldHashArray[i]);
129+
}
130+
}
131+
132+
/**
133+
* 删除元素
134+
*
135+
* @param key
136+
* @return
137+
*/
138+
public DataItem delete(int key) {
139+
if (isEmpty()) {
140+
System.out.println("Hash Table is Empty!");
141+
return null;
142+
}
143+
144+
int hashVal = hashFunction(key);
145+
while (hashArray[hashVal] != null) {
146+
if (hashArray[hashVal].getKey() == key) {
147+
DataItem temp = hashArray[hashVal];
148+
hashArray[hashVal] = nonItem;
149+
itemNum--;
150+
return temp;
151+
}
152+
++hashVal;
153+
hashVal %= arraySize;
154+
}
155+
return null;
156+
}
157+
158+
159+
public static class DataItem {
160+
161+
private int iData;
162+
163+
public int getKey() {
164+
return iData;
165+
}
166+
167+
public DataItem(int iData) {
168+
this.iData = iData;
169+
}
170+
}
171+
}

0 commit comments

Comments
 (0)