SHARE
TWEET

Untitled

a guest Jan 15th, 2020 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import 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.  */
  8. class 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.  
  35. abstract 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){
  49.       throw new IllegalArgumentException();
  50.     }else{
  51.     myTable = new LinkedList[capacity];
  52.     }
  53.     for(int i = 0; i < capacity; i++){
  54.       myTable[i] = new LinkedList<Entry>();
  55.     }
  56.   }
  57.  
  58.   /**
  59.    * Add a key value pair to the HashTable.
  60.    *
  61.    * @param key
  62.    *     to identify the value.
  63.    * @param value
  64.    *     that is identified by the key.
  65.    */
  66.   public void put(String key, Integer value) {
  67.    int hash = hash(key);
  68.    if(containsKey(key)){
  69.      int val = this.get(key);
  70.      myTable[hash].remove(new Entry(key, val));
  71.    }
  72.    myTable[hash].add(new Entry(key, value));
  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.     int hash = hash(key);
  82.     for(Entry e : myTable[hash]){
  83.       if(e.equals(key)){
  84.         return true;
  85.       }
  86.     }
  87.     return false;
  88.   }
  89.  
  90.   /**
  91.    * Get a value from the HashTable.
  92.    *
  93.    * @param key
  94.    *     that identifies the value.
  95.    * @return the value associated with the key or `null` if the key is not in the HashTable.
  96.    */
  97.   public Integer get(String key) {
  98.    int hash = hash(key);
  99.    
  100.    for(Entry e : myTable[hash]){
  101.      if(e.equals(key)){
  102.        return e.getValue();
  103.      }
  104.    }
  105.    return null;
  106.   }
  107.  
  108.   /**
  109.    * @return the capacity of the HashTable.
  110.    */
  111.   public int getCapacity() {
  112.     return myTable.length;
  113.   }
  114.  
  115.   /**
  116.    * Hashes a string/key.
  117.    *
  118.    * @param item
  119.    *     to hash.
  120.    * @return the hashcode of the string, modulo the capacity of the HashTable.
  121.    */
  122.   public abstract int hash(String item);
  123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top