SeparateChainingHashST.java
8.18 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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/******************************************************************************
* Compilation: javac SeparateChainingHashST.java
* Execution: java SeparateChainingHashST < input.txt
* Dependencies: StdIn.java StdOut.java
* Data files: http://algs4.cs.princeton.edu/34hash/tinyST.txt
*
* A symbol table implemented with a separate-chaining hash table.
*
******************************************************************************/
package edu.princeton.cs.algs4;
/**
* The {@code SeparateChainingHashST} class represents a symbol table of generic
* key-value pairs.
* It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
* <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
* It also provides a <em>keys</em> method for iterating over all of the keys.
* A symbol table implements the <em>associative array</em> abstraction:
* when associating a value with a key that is already in the symbol table,
* the convention is to replace the old value with the new value.
* Unlike {@link java.util.Map}, this class uses the convention that
* values cannot be {@code null}—setting the
* value associated with a key to {@code null} is equivalent to deleting the key
* from the symbol table.
* <p>
* This implementation uses a separate chaining hash table. It requires that
* the key type overrides the {@code equals()} and {@code hashCode()} methods.
* The expected time per <em>put</em>, <em>contains</em>, or <em>remove</em>
* operation is constant, subject to the uniform hashing assumption.
* The <em>size</em>, and <em>is-empty</em> operations take constant time.
* Construction takes constant time.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/34hash">Section 3.4</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
* For other implementations, see {@link ST}, {@link BinarySearchST},
* {@link SequentialSearchST}, {@link BST}, {@link RedBlackBST}, and
* {@link LinearProbingHashST},
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n; // number of key-value pairs
private int m; // hash table size
private SequentialSearchST<Key, Value>[] st; // array of linked-list symbol tables
/**
* Initializes an empty symbol table.
*/
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
/**
* Initializes an empty symbol table with {@code m} chains.
* @param m the initial number of chains
*/
public SeparateChainingHashST(int m) {
this.m = m;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
// resize the hash table to have the given number of chains,
// rehashing all of the keys
private void resize(int chains) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
for (int i = 0; i < m; i++) {
for (Key key : st[i].keys()) {
temp.put(key, st[i].get(key));
}
}
this.m = temp.m;
this.n = temp.n;
this.st = temp.st;
}
// hash value between 0 and m-1
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
/**
* Returns the number of key-value pairs in this symbol table.
*
* @return the number of key-value pairs in this symbol table
*/
public int size() {
return n;
}
/**
* Returns true if this symbol table is empty.
*
* @return {@code true} if this symbol table is empty;
* {@code false} otherwise
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns true if this symbol table contains the specified key.
*
* @param key the key
* @return {@code true} if this symbol table contains {@code key};
* {@code false} otherwise
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public boolean contains(Key key) {
if (key == null) throw new IllegalArgumentException("argument to contains() is null");
return get(key) != null;
}
/**
* Returns the value associated with the specified key in this symbol table.
*
* @param key the key
* @return the value associated with {@code key} in the symbol table;
* {@code null} if no such value
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
int i = hash(key);
return st[i].get(key);
}
/**
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
* Deletes the specified key (and its associated value) from this symbol table
* if the specified value is {@code null}.
*
* @param key the key
* @param val the value
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
// double table size if average length of list >= 10
if (n >= 10*m) resize(2*m);
int i = hash(key);
if (!st[i].contains(key)) n++;
st[i].put(key, val);
}
/**
* Removes the specified key and its associated value from this symbol table
* (if the key is in this symbol table).
*
* @param key the key
* @throws IllegalArgumentException if {@code key} is {@code null}
*/
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
int i = hash(key);
if (st[i].contains(key)) n--;
st[i].delete(key);
// halve table size if average length of list <= 2
if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);
}
// return keys in symbol table as an Iterable
public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++) {
for (Key key : st[i].keys())
queue.enqueue(key);
}
return queue;
}
/**
* Unit tests the {@code SeparateChainingHashST} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++) {
String key = StdIn.readString();
st.put(key, i);
}
// print keys
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}
/******************************************************************************
* Copyright 2002-2016, Robert Sedgewick and Kevin Wayne.
*
* This file is part of algs4.jar, which accompanies the textbook
*
* Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
* Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
* http://algs4.cs.princeton.edu
*
*
* algs4.jar is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* algs4.jar is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with algs4.jar. If not, see http://www.gnu.org/licenses.
******************************************************************************/