SHARE
TWEET

hash

a guest Jun 12th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import edu.princeton.cs.algs4.StdOut;
  2.  
  3. public class HashTables<Key, Value>
  4. {
  5.     private int N;// количество пар ключ-значение в таблице
  6.     private int M  ; // размер таблицы с линейным опробованием
  7.     private Key[] keys;// ключи
  8.     private Value [] vals;// значения
  9.     private int kolizii=0;
  10.  
  11.     public HashTables(int capacity) {
  12.         M = capacity;
  13.         N = 0;
  14.         keys = (Key[]) new Object[M];
  15.         vals = (Value[]) new Object[M];
  16.     }
  17.         public int getKolizii(){
  18.         return kolizii;
  19.         }
  20.  
  21.         private int hash (Key key)
  22.         {
  23.             return (key.hashCode() & 0x7fffffff) % M;
  24.         }
  25.         public void put (Key key, Value val) {
  26.             if (N >= M / 2) resize(2 * M); // удвоение M ;
  27.             int i = hash(key);
  28.             if (key.equals(keys[i])){
  29.                 kolizii++;
  30.             StdOut.println("Коллизия!");
  31.         }
  32.             for (i = hash(key); keys[i] != null; i = (i + 1) % M)
  33.                 if (keys[i].equals(key)) {
  34.                     vals[i] = val;
  35.                     return;
  36.                 }
  37.             keys[i] = key;
  38.             vals[i] = val;
  39.             N++;
  40.         }
  41.         public Value get (Key key)
  42.         {
  43.             for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
  44.                 if (keys[i].equals(key)) return vals[i];
  45.             return null;
  46.         }
  47.     private void resize(int capacity) {
  48.         HashTables<Key, Value> temp = new HashTables<Key, Value>(capacity);
  49.         for (int i = 0; i < M; i++) {
  50.             if (keys[i] != null) {
  51.                 temp.put(keys[i], vals[i]);
  52.             }
  53.         }
  54.         keys = temp.keys;
  55.         vals = temp.vals;
  56.         M    = temp.M;
  57.     }
  58.  
  59.     }
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