-
Notifications
You must be signed in to change notification settings - Fork 53
Expand file tree
/
Copy pathHashTables.java
More file actions
188 lines (156 loc) · 4.95 KB
/
HashTables.java
File metadata and controls
188 lines (156 loc) · 4.95 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/** Copyright 2011 Fabian Steeg, University of Cologne, http://github.com/spinfo */
package spinfo;
import junit.framework.Assert;
import org.junit.Test;
/** Hash Tables: a useful, efficient data structure. */
public class HashTables {
/* The basic idea: a direct-address table */
@Test
public void direct() {
DirectAddressTable t = new DirectAddressTable();
Person tom = new Person("tom");
Person jim = new Person("jim");
t.put(50, tom); // e.g. student ID = 50
t.put(75, jim); // e.g. student ID = 75
Assert.assertEquals(tom, t.get(50));
Assert.assertEquals(jim, t.get(75));
}
static class DirectAddressTable {
Object[] table = new Object[100]; // lots of space wasted
public void put(int key, Object person) { // only numeric key supported
table[key] = person;
}
public Object get(int key) {
return table[key];
}
}
static class Person {
private String name;
public Person(String name) {
this.name = name;
}
@Override
public String toString() {
return name;
}
}
/* A simple hash table using chaining for collisions: */
@Test
public void hashed() {
HashTable t = new HashTable();
Person tom = new Person("tom");
Person jim = new Person("jim");
Person joe = new Person("joe");
t.put(50, tom); // e.g. student ID = 50
t.put(75, jim); // e.g. student ID = 75
t.put(85, joe); // e.g. student ID = 85, hashes to same as 75 here
Assert.assertEquals(tom, t.get(50));
Assert.assertEquals(jim, t.get(75));
Assert.assertEquals(joe, t.get(85));
}
static class HashTable {
Element[] table = new Element[10]; // scale down
static class Element {
Element next;
Object key; // key can be of any type
Object value;
public Element(Object key, Object value) {
this.key = key;
this.value = value;
}
}
public void put(Object key, Object value) {
Element newElement = new Element(key, value);
int slot = hash(key);
Element e = table[slot];
table[slot] = newElement; // place new element in table
/* Handle previous element in the slot with a different key: */
if (e != null && !e.key.equals(newElement.key)) {
newElement.next = e; // add new in front
}
}
public Object get(Object key) {
Element e = table[hash(key)];
if (e == null) // no value in slot
return null;
/* Find element with correct key in list: */
while (!(e.key.equals(key)) && e.next != null) {
e = e.next;
}
return e.key.equals(key) ? e.value : null;
}
private int hash(Object key) {
// simple demo hash: map key to table length
if (key instanceof Integer) {
return ((Integer) key) % table.length;
}
if (key instanceof String) {
return ((String) key).length() % table.length;
}
return key.hashCode() % table.length;
}
}
/* Hashing in practice: equality for custom objects */
@Test
public void equality() {
Student s1 = new Student(5, "John", "Doe");
Student s2 = new Student(8, "Jim", "Jones");
Student s3 = new Student(8, "Jim", "Jones");
Student s4 = new Student(5, "John", "Doe");
/* hashCode has to be implemented consistent with equals: */
Assert.assertEquals(s1, s4);
Assert.assertEquals(s2, s3);
Assert.assertEquals(s1.hashCode(), s4.hashCode());
Assert.assertEquals(s2.hashCode(), s3.hashCode());
Assert.assertFalse(s1.equals(s2));
Assert.assertFalse(s1.hashCode() == s2.hashCode());
}
static class Student {
int id;
String first;
String last;
public Student(int id, String first, String last) {
this.id = id;
this.first = first;
this.last = last;
}
@Override
public String toString() {
return String.format("%s %s (%s)", first, last, id);
}
@Override
public int hashCode() { // use same values as in equals
int result = 17;
result = 31 * result + id;
result = 31 * result + first.hashCode();
result = 31 * result + last.hashCode();
return result;
}
@Override
public boolean equals(Object that) { // use same values as in hashCode
return (that instanceof Student) && ((Student) that).id == this.id
&& ((Student) that).first.equals(this.first)
&& ((Student) that).last.equals(this.last);
}
}
/* Hash table sample usage: counting words */
@Test
public void usage() {
String text = "hi there hi everybody hi there again";
HashTable t = count(text);
Assert.assertEquals(3, t.get("hi"));
Assert.assertEquals(2, t.get("there"));
Assert.assertEquals(1, t.get("everybody"));
}
private HashTable count(String text) {
HashTable t = new HashTable();
String[] words = text.split(" ");
for (String w : words) {
Integer v = (Integer) t.get(w);
if (v == null) // first occurrence
v = 0;
t.put(w, v + 1); // count up
}
return t;
}
}