· 9 years ago · Nov 25, 2016, 02:02 PM
1package hr.fer.oop.lab4.prob2;
2
3import java.util.Iterator;
4import java.util.NoSuchElementException;
5
6/**
7 * SimpleHashtable implementation.
8 * Overflow is solved by linking elements in the same slot as singly linked list.
9 *
10 * @author Josip Bedenikovic
11 *
12 * @param <K> object representing the key of an entry.
13 * @param <V> object representing the value of an entry.
14 */
15public class SimpleHashtable<K, V> implements Iterable<SimpleHashtable.TableEntry<K, V>>{
16 /**
17 * Integer representing the number of elements stored in hash table.
18 */
19 private int size;
20
21 /**
22 * Array representing the slots of hash table.
23 */
24 protected TableEntry<K, V>[] table;
25
26 /**
27 * Default size of hash table
28 */
29 private static final int DEFAULT_SIZE = 16;
30
31 /**
32 * Constructor creates a new hash table with 16 slots.
33 */
34 @SuppressWarnings("unchecked")
35 public SimpleHashtable (){
36 //size = DEFAULT_SIZE;
37 table = new TableEntry[DEFAULT_SIZE];
38 }
39
40 /**
41 * Constructor creates a new hash table with number of slots set to nearest
42 * power of two that is bigger than given number.
43 * If given capacity is less than 1, method prints a warning.
44 *
45 * @param capacity number from which method calculates the number of slots.
46 *
47 */
48 @SuppressWarnings("unchecked")
49 public SimpleHashtable (int capacity){
50 if (capacity < 1) System.out.println ("Invalid capacity!");
51 else {
52 int powerOfTwo = (int) Math.ceil((Math.log((double) capacity) / Math.log(2.0)));
53 table = new TableEntry[(int) Math.pow(2, powerOfTwo)];
54 }
55 }
56
57 /**
58 * Method for putting a new element in hash table. If an element with the same
59 * key is already in the table, its value will be updated.
60 *
61 * @param key object representing the table key of an entry.
62 * @param value object representing the value of an entry.
63 */
64 public void put (K key, V value){
65 int slotNumber = (int)Math.abs(key.hashCode()) % table.length;
66 if (table[slotNumber] == null){
67 TableEntry<K, V> tmpTableEntry = new TableEntry<K, V> (key, value, null);
68 table[slotNumber] = tmpTableEntry;
69 }
70 else if (table[slotNumber].getKey().equals(key)){
71 table[slotNumber].setValue(value);
72 return;
73 }
74 else {
75 TableEntry<K, V> prevSlot = table[slotNumber];
76 TableEntry<K, V> tmpTableEntry = table[slotNumber].next;
77 do {
78 if (tmpTableEntry != null && tmpTableEntry.getKey().equals(key)){
79 tmpTableEntry.setValue(value);
80 return;
81 }
82 if (tmpTableEntry != null){
83 prevSlot = tmpTableEntry;
84 tmpTableEntry = tmpTableEntry.next;
85 }
86 } while (tmpTableEntry != null);
87 prevSlot.next = new TableEntry<K, V> (key, value, null);
88 }
89 size++;
90 }
91
92 /**
93 * Method for getting an element from table using the key of the element.
94 *
95 * @param key object representing the table key of an entry.
96 * @return value of searched entry if found, otherwise null.
97 */
98 public V get (K key){
99 int slotNumber = Math.abs(key.hashCode()) % table.length;
100 TableEntry<K, V> temp = table[slotNumber];
101 while (temp != null){
102 if (temp.getKey().equals(key)) return temp.getValue();
103 temp = temp.next;
104 }
105 return null;
106 }
107
108 /**
109 * Method for checking if hash table contains an element with given value.
110 *
111 * @param value object representing the value of an entry.
112 * @return true if element with given value exist in hash table, otherwise false.
113 */
114 public boolean containsValue (V value){
115 for (int i = 0; i < table.length; i++){
116 if (table[i] == null) continue;
117 else {
118 TableEntry<K, V> tmpTableEntry = table[i];
119 do {
120 if (tmpTableEntry.getValue().equals(value)) return true;
121 tmpTableEntry = tmpTableEntry.next;
122 } while (tmpTableEntry != null);
123 }
124 }
125 return false;
126 }
127
128 /**
129 * Method for checking if hash table contains an element with given key.
130 *
131 * @param key object representing the key of an entry.
132 * @return true if element with given value exists in hash table, false otherwise.
133 */
134 public boolean containsKey (K key) {
135 if (key == null) return false;
136 int slotNumber = Math.abs(key.hashCode()) % size;
137 if (table[slotNumber] == null) return false;
138 else {
139 TableEntry<K, V> tmpTableEntry = table[slotNumber];
140 do {
141 if (tmpTableEntry.getKey().equals(key)) return true;
142 tmpTableEntry = tmpTableEntry.next;
143 } while (tmpTableEntry != null);
144 }
145 return false;
146 }
147
148 /**
149 * Method removes an element with given key from hash table if it exists, otherwise it does nothing.
150 *
151 * @param key object representing the key of an entry.
152 */
153 public void remove(K key){
154 int hash = Math.abs(key.hashCode()) % this.table.length;
155
156 if(table[hash]!=null){
157 TableEntry<K,V> tempEntry = table[hash];
158 if(tempEntry.key==key){
159 table[hash] = tempEntry.next;
160 size--;
161 }else{
162 while(tempEntry.next.next!=null && tempEntry.next.key!=key){
163 tempEntry = tempEntry.next;
164 }
165
166 if(tempEntry.next.key == key){
167 tempEntry.next = tempEntry.next.next;
168 size--;
169 } else{
170 throw new NoSuchElementException("Not exist");
171 }
172 }
173
174 } else{
175 throw new NoSuchElementException("Not exist");
176 }
177 }
178
179 public void removeAll (SimpleHashtable<K,V> other){
180 if (other == null) return;
181 for (int i = 0; i < this.table.length; i++){
182 TableEntry<K, V> prevSlot = new TableEntry<K, V> (null,null,null);
183 while (this.table[i].equals(null) != true){
184 if (this.table[i].getKey().equals(other.table[0].getKey())){
185 if (prevSlot.equals(null) != true)
186 prevSlot.next = this.table[i].next;
187 else
188 this.table[i] = this.table[i].next;
189 }
190 prevSlot = this.table[i];
191 this.table[i] = this.table[i].next;
192 }
193 }
194 }
195
196
197
198 /**
199 * Method calculates the number of elements in hash table.
200 *
201 * @return size of hash table.
202 */
203 public int size(){
204 return size;
205 }
206
207 /**
208 * Method for checking if hash table is empty.
209 *
210 * @return false if hash table is not empty, true otherwise.
211 */
212 public boolean isEmpty(){
213 for (int i = 0; i < table.length; i++){
214 if(table[i].equals(null) != true) return false;
215 }
216 return true;
217 }
218
219 /**
220 * Method constructs string representation of hash table.
221 *
222 * @return String representing hash table.
223 */
224 @Override
225 public String toString(){
226 String str=" ";
227 for (int i = 0; i < table.length; i++){
228 if (table[i] == null) continue;
229 else {
230 TableEntry<K, V> tmpTableEntry = table[i];
231 do{
232 str += tmpTableEntry.toString() + ", ";
233 tmpTableEntry = tmpTableEntry.next;
234 } while (tmpTableEntry != null);
235 }
236 }
237 if (str.endsWith(", "))
238 str = str.substring(0, str.length() - 2);
239 System.out.println(str);
240 return str;
241 }
242
243 /**
244 * Class implementing the table entry structure and methods for manipulating the table entry.
245 *
246 * @param <K> object representing the key of an entry.
247 * @param <V> object representing the value of an entry.
248 */
249 public static class TableEntry<K, V>{
250 /**
251 * Object representing the key of a table entry. Cannot be null.
252 */
253 private K key;
254
255 /**
256 * Object representing the value of an entry.
257 */
258 private V value;
259
260 /**
261 * Reference to the next table entry instance.
262 */
263 protected TableEntry<K, V> next;
264
265 /**
266 * Constructor which initializes a new table entry instance and sets its key, value
267 * and reference to the next table entry.
268 *
269 * @param key object representing the key of an entry.
270 * @param value object representing the value of an entry.
271 * @param next reference to the next table entry.
272 */
273 public TableEntry(K key, V value, TableEntry<K, V> next){
274 this.key = key;
275 this.value = value;
276 this.next = next;
277 }
278
279 /**
280 * Getter method which returns the key of an entry.
281 *
282 * @return object representing the key of an entry.
283 */
284 public K getKey(){
285 return key;
286 }
287
288 /**
289 * Getter method which returns the value of an entry.
290 *
291 * @return object representing the value of an entry.
292 */
293 public V getValue(){
294 return value;
295 }
296
297 /**
298 * Getter method which returns reference to the next element in table.
299 *
300 * @return reference to the next table entry.
301 */
302 public TableEntry<K,V> getNext(){
303 return next;
304 }
305
306 /**
307 * Setter method which sets value of an entry.
308 *
309 * @param value object representing the value of an entry.
310 */
311 public void setValue(V value){
312 this.value = value;
313 }
314
315 /**
316 * Method overriding the toString() method.
317 *
318 * @return string in form of "{key = value}".
319 */
320 @Override
321 public String toString(){
322 String str;
323 str = "{" + key.toString() + "=" + value.toString() + "}";
324 return str;
325 }
326 }
327
328 /**
329 * Main method
330 *
331 * @param args String array
332 */
333 public static void main(String[] args){
334 //create collection:
335 SimpleHashtable <String, Integer> examMarks = new SimpleHashtable <> ();
336 // fill data:
337 examMarks.put("Ivana", Integer.valueOf(2));
338 examMarks.put("Ante", Integer.valueOf(2));
339 examMarks.put("Jasna", Integer.valueOf(2));
340 examMarks.put("Kristina", Integer.valueOf(5));
341 examMarks.put("Ivana", Integer.valueOf(5)); // overwrites old grade for Ivana
342 // query collection:
343 Integer kristinaGrade = examMarks.get("Kristina");
344 System.out.println("Kristina's exam grade is: " + kristinaGrade); // writes: 5
345 // What is collection's size? Must be four!
346 System.out.println("Number of stored pairs: " + examMarks.size()); // writes: 4
347
348 SimpleHashtable <String, Integer> test = new SimpleHashtable <> ();
349
350 test.put("Ivana", Integer.valueOf(2));
351 test.put("Ante", Integer.valueOf(2));
352
353 examMarks.remove("Ivana");
354
355 examMarks.toString();
356 }
357
358
359 /**
360 *
361 */
362 @Override
363 public Iterator<TableEntry<K, V>> iterator() {
364 Iterator<TableEntry<K, V>> iter = new Iterator<SimpleHashtable.TableEntry<K, V>>() {
365 /**
366 * Integer pointing to current slot.
367 */
368 private int currentSlot = 0;
369
370 /**
371 * Integer pointing to current element.
372 */
373 private int currentElement = 0;
374
375 /**
376 * Method checks if next element exists
377 *
378 * @return true if next element exists, false otherwise.
379 */
380 @Override
381 public boolean hasNext() {
382 if (currentSlot < table.length) {
383 TableEntry<K, V> temp = table[currentSlot];
384 int count = 0;
385 while (count < currentElement) {
386 if (temp == null) return false;
387 temp = temp.getNext();
388 count++;
389 }
390 if (temp != null) return true;
391 }
392 return false;
393 }
394
395 /**
396 * Method searches for the next element from the hash table
397 * and returns it.
398 *
399 * @return next element in hash table.
400 */
401 @Override
402 public TableEntry<K, V> next() {
403 TableEntry<K, V> temp = table[currentSlot];
404 int count = 0;
405 while (count < currentElement) {
406 temp = temp.getNext();
407 count++;
408 }
409 currentElement++;
410 if (temp.getNext() == null) {
411 currentSlot++;
412 currentElement = 0;
413 }
414 return temp;
415 }
416 };
417 return iter;
418 }
419 }