SHARE
TWEET

Hash 3

Krlcc Sep 12th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. import static javax.swing.JRootPane.NONE;
  6.  
  7. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  8.  
  9.     // Each MapEntry object is a pair consisting of a key (a Comparable
  10.     // object) and a value (an arbitrary object).
  11.     K key;
  12.     E value;
  13.  
  14.     public MapEntry (K key, E val) {
  15.         this.key = key;
  16.         this.value = val;
  17.     }
  18.  
  19.     public int compareTo (K that) {
  20.         // Compare this map entry to that map entry.
  21.         @SuppressWarnings("unchecked")
  22.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  23.         return this.key.compareTo(other.key);
  24.     }
  25.  
  26.     public String toString () {
  27.         return "<" + key + "," + value + ">";
  28.     }
  29. }
  30.  
  31. class OBHT<K extends Comparable<K>,E> {
  32.  
  33.     // An object of class OBHT is an open-bucket hash table, containing entries
  34.     // of class MapEntry.
  35.     private MapEntry<K,E>[] buckets;
  36.  
  37.     // buckets[b] is null if bucket b has never been occupied.
  38.     // buckets[b] is former if bucket b is formerly-occupied
  39.     // by an entry that has since been deleted (and not yet replaced).
  40.  
  41.     static final int NONE = -1; // ... distinct from any bucket index.
  42.  
  43.     private static final MapEntry former = new MapEntry(null, null);
  44.     // This guarantees that, for any genuine entry e,
  45.     // e.key.equals(former.key) returns false.
  46.  
  47.     private int occupancy = 0;
  48.     // ... number of occupied or formerly-occupied buckets in this OBHT.
  49.  
  50.     @SuppressWarnings("unchecked")
  51.     public OBHT (int m) {
  52.         // Construct an empty OBHT with m buckets.
  53.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  54.     }
  55.     public E getValue(int i)
  56.     {
  57.         return buckets[i].value;
  58.     }
  59.  
  60.  
  61.     private int hash (K key) {
  62.         // Translate key to an index of the array buckets.
  63.         return Math.abs(key.hashCode()) % buckets.length;
  64.     }
  65.  
  66.     public int search (K targetKey) {
  67.         // Find which if any bucket of this OBHT is occupied by an entry whose key
  68.         // is equal to targetKey. Return the index of that bucket.
  69.         int b = hash(targetKey); int n_search=0;
  70.         for (;;) {
  71.             MapEntry<K,E> oldEntry = buckets[b];
  72.             if (oldEntry == null)
  73.                 return NONE;
  74.             else if (targetKey.equals(oldEntry.key))
  75.                 return b;
  76.             else
  77.             {
  78.                 b = (b + 1) % buckets.length;
  79.                 n_search++;
  80.                 if(n_search==buckets.length)
  81.                     return NONE;
  82.  
  83.             }
  84.         }
  85.     }
  86.  
  87.     public void insert (K key, E val) {
  88.         // Insert the entry <key, val> into this OBHT.
  89.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  90.         int b = hash(key); int n_search=0;
  91.         for (;;) {
  92.             MapEntry<K,E> oldEntry = buckets[b];
  93.             if (oldEntry == null) {
  94.                 if (++occupancy == buckets.length) {
  95.                     System.out.println("Hash tabelata e polna!!!");
  96.                 }
  97.                 buckets[b] = newEntry;
  98.                 return;
  99.             }
  100.             else if (oldEntry == former
  101.                     || key.equals(oldEntry.key)) {
  102.                 buckets[b] = newEntry;
  103.                 return;
  104.             }
  105.             else
  106.             {
  107.                 b = (b + 1) % buckets.length;
  108.                 n_search++;
  109.                 if(n_search==buckets.length)
  110.                     return;
  111.  
  112.             }
  113.         }
  114.     }
  115.  
  116.  
  117.     @SuppressWarnings("unchecked")
  118.     public void delete (K key) {
  119.         // Delete the entry (if any) whose key is equal to key from this OBHT.
  120.         int b = hash(key); int n_search=0;
  121.         for (;;) {
  122.             MapEntry<K,E> oldEntry = buckets[b];
  123.  
  124.             if (oldEntry == null)
  125.                 return;
  126.             else if (key.equals(oldEntry.key)) {
  127.                 buckets[b] = former;//(MapEntry<K,E>)former;
  128.                 return;
  129.             }
  130.             else{
  131.                 b = (b + 1) % buckets.length;
  132.                 n_search++;
  133.                 if(n_search==buckets.length)
  134.                     return;
  135.  
  136.             }
  137.         }
  138.     }
  139.  
  140.  
  141.     public String toString () {
  142.         String temp = "";
  143.         for (int i = 0; i < buckets.length; i++) {
  144.             temp += i + ":";
  145.             if (buckets[i] == null)
  146.                 temp += "\n";
  147.             else if (buckets[i] == former)
  148.                 temp += "former\n";
  149.             else
  150.                 temp += buckets[i] + "\n";
  151.         }
  152.         return temp;
  153.     }
  154.  
  155.  
  156.     public OBHT<K,E> clone () {
  157.         OBHT<K,E> copy = new OBHT<K,E>(buckets.length);
  158.         for (int i = 0; i < buckets.length; i++) {
  159.             MapEntry<K,E> e = buckets[i];
  160.             if (e != null && e != former)
  161.                 copy.buckets[i] = new MapEntry<K,E>(e.key, e.value);
  162.             else
  163.                 copy.buckets[i] = e;
  164.         }
  165.         return copy;
  166.     }
  167. }
  168.  
  169. public class Hash
  170. {
  171.     public static void main(String[] args) throws IOException {
  172.  
  173.         BufferedReader bufferedReader= new BufferedReader(new InputStreamReader(System.in));
  174.  
  175.         String expr=bufferedReader.readLine();
  176.         int N= Integer.parseInt(expr);
  177.         OBHT<String, String> obht= new OBHT<>(N);
  178.  
  179.         for (int i = 0; i <N ; i++) {
  180.             expr=bufferedReader.readLine();     //mace cat
  181.             String [] part= expr.split(" ");
  182.             obht.insert( part[1], part[0]);     //key-> cat value->mace
  183.         }
  184.  
  185.         String englishWord;
  186.         while (!(englishWord=bufferedReader.readLine()).equals("KRAJ"))
  187.         {
  188.  
  189.             int index;
  190.             if((index=obht.search(englishWord))!=-1)
  191.             {
  192.                 System.out.println(obht.getValue(index));
  193.             }
  194.             else
  195.             {
  196.                 System.out.println("/");
  197.             }
  198.  
  199.         }
  200.     }
  201. }
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