-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHashTable.java
More file actions
83 lines (72 loc) · 2.19 KB
/
HashTable.java
File metadata and controls
83 lines (72 loc) · 2.19 KB
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
package hash;
/**
* A very simple implementation of a Hash Table DS.
*
*/
public class HashTable {
private static final int TABLE_SIZE = 100;
private Record[] tableData = new Record[TABLE_SIZE]; // say that we won't get more than 100 records
public void put(Object key, Object value) {
int keyCode = key.hashCode();
int step = 0;
int slot = hash(keyCode, step);
while (!isEmpty(slot)) {
slot = hash(keyCode, ++step);
}
tableData[slot] = new Record(key, value);
}
public boolean keyExists(Object key) {
int keyCode = key.hashCode();
int step = 0;
int slot = hash(keyCode, step);
while (tableData[slot] != null && !tableData[slot].getKey().equals(key)) {
slot = hash(keyCode, ++step);
}
if (tableData[slot] != null) return true;
return false;
}
public Object get(Object key) {
int keyCode = key.hashCode();
int step = 0;
int slot = hash(keyCode, step);
while (tableData[slot] != null && !tableData[slot].getKey().equals(key)) {
slot = hash(keyCode, ++step);
}
if (tableData[slot] != null) return tableData[slot].getData();
return null;
}
private int hash(int key, int step) {
if (step == 0)
return key % TABLE_SIZE;
return (key % TABLE_SIZE + step*step) % TABLE_SIZE;
}
private boolean isEmpty(int slot) {
return tableData[slot] == null;
}
private class Record {
Object key;
Object data;
public Record(Object key, Object data) {
this.key = key;
this.data = data;
}
public Object getKey() {
return this.key;
}
public Object getData() {
return this.data;
}
}
public static void main(String[] args) {
HashTable ht = new HashTable();
ht.put("4", 40);
ht.put("6", 60);
ht.put("7", 70);
ht.put("8", 80);
ht.put("9", 90);
ht.put("5", 50);
System.out.println(ht.keyExists("2"));
System.out.println(ht.keyExists("4"));
System.out.println(ht.get(2));
}
}