gowtham900

AbstractHashMap

Oct 22nd, 2021
845
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.Random;
  3.  
  4. public abstract class AbstractHashMap<K,V> extends AbstractMap<K,V>{
  5.     protected int n=0;
  6.     protected int capacity;
  7.     private int prime;
  8.     private long scale,shift;
  9.     public AbstractHashMap(int cap,int p){
  10.         prime=p;
  11.         capacity=cap;
  12.         Random rand=new Random();
  13.         scale=rand.nextInt(prime-1)+1;
  14.         shift=rand.nextInt(prime);
  15.         createTable();
  16.     }
  17.     public AbstractHashMap(int cap){
  18.         this(cap,109345121);
  19.     }
  20.     public AbstractHashMap(){
  21.         this(17);
  22.     }
  23.     public int size(){
  24.         return n;
  25.     }
  26.     public V get(K key){
  27.         return bucketGet(hashValue(key),key);
  28.     }
  29.     public V remove(K key){
  30.         return bucketRemove(hashValue(key),key);
  31.     }
  32.     public V put(K key,V value){
  33.         V answer =bucketPut(hashValue(key),key,value);
  34.         if(n>capacity/2)
  35.             resize(2*capacity-1);
  36.         return answer;
  37.     }
  38.     private int hashValue(K key){
  39.         return (int)((Math.abs(key.hashCode()*scale+shift)%prime)%capacity);
  40.     }
  41.     private void resize(int newCap){
  42.         ArrayList<Entry<K,V>>buffer=new ArrayList<>(n);
  43.         for(Entry<K,V>e:entrySet())
  44.             buffer.add(e);
  45.         capacity=newCap;
  46.         createTable();
  47.         n=0;
  48.         for(Entry<K,V>e:buffer)
  49.             put(e.getKey(),e.getValue());
  50.  
  51.     }
  52.     protected abstract void createTable();
  53.     protected abstract V bucketGet(int h,K k);
  54.     protected abstract V bucketPut(int h,K k,V v);
  55.     protected abstract V bucketRemove(int h,K k);
  56. }
RAW Paste Data