CYE8MPNH

1import java.util.*;
2
3/**
4 * Entry objects are used to represent "Key-Value" pairs.
5 * An entry can be created by using new Entry(String key, Integer Value)
6 * The .equals() method of Entry will compare the keys only.
7 */
8class Entry {
9  public final String key;
10  public final Integer value;
11
12  public Entry(String s, Integer v) {
13    key = s;
14    value = v;
15  }
16
17  public boolean equals(String s) {
18    return s == null && key == null || key.equals(s);
19  }
20
21  @Override
22  public boolean equals(Object o) {
23    return this == o || o != null && getClass() == o.getClass() && this.equals(((Entry) o).key);
24  }
25
26  public String getKey() {
27    return key;
28  }
29
30  public int getValue() {
31    return value;
32  }
33}
34
35abstract class HashTable {
36  protected LinkedList<Entry>[] myTable;
37
38  /**
39   * Constructs a new HashTable.
40   *
41   * @param capacity
42   *     to be used as capacity of the table.
43   * @throws IllegalArgumentException
44   *     if the input capacity is invalid.
45   */
46  @SuppressWarnings("unchecked")
47  public HashTable(int capacity) {
48    if(capacity <= 1) throw new IllegalArgumentException();
49    myTable = new LinkedList[capacity];
50  }
51
52  /**
53   * Add a key value pair to the HashTable.
54   *
55   * @param key
56   *     to identify the value.
57   * @param value
58   *     that is identified by the key.
59   */
60  public void put(String key, Integer value) {
61    int hashedKey = hash(key);  //get the hashedKey
62    
63    //create the bucket if it is not already there
64    if( myTable[hashedKey] == null){
65      myTable[hashedKey] = new LinkedList<>();
66    }
67    
68    Entry entry = new Entry(key, value); 
69    
70    myTable[hashedKey].remove(entry);
71    myTable[hashedKey].add(entry);
72    
73  }
74
75  /**
76   * @param key
77   *     to look for in the HashTable.
78   * @return true iff the key is in the HashTable.
79   */
80  public boolean containsKey(String key) {
81    return get(key) != null;
82  }
83
84  /**
85   * Get a value from the HashTable.
86   *
87   * @param key
88   *     that identifies the value.
89   * @return the value associated with the key or `null` if the key is not in the HashTable.
90   */
91  public Integer get(String key) {
92    int i = hash(key);  //get the hashed key
93    if(myTable[i] == null) return null; //because no linked list exists there
94    for(Entry entry : myTable[i]){
95      if(entry.getKey().equals(key) || (entry.getKey() == null && key == null)) {
96        return entry.getValue();
97      }
98    }
99    return null; 
100  }
101
102  /**
103   * @return the capacity of the HashTable.
104   */
105  public int getCapacity() {
106    return myTable.length;
107  }
108
109  /**
110   * Hashes a string/key.
111   *
112   * @param item
113   *     to hash.
114   * @return the hashcode of the string, modulo the capacity of the HashTable.
115   */
116  public abstract int hash(String item);
117}