daily pastebin goal
51%
SHARE
TWEET

Untitled

a guest Sep 14th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class SymbolTable {
  2.     private static final int INIT_CAPACITY = 7;
  3.  
  4.     /* Number of key-value pairs in the symbol table */
  5.     private int N;
  6.     /* Size of linear probing table */
  7.     private int M;
  8.     /* The keys */
  9.     private String[] keys;
  10.     /* The values */
  11.     private Character[] vals;
  12.  
  13.     /**
  14.      * Create an empty hash table - use 7 as default size
  15.      */
  16.     public SymbolTable() {
  17.         this(INIT_CAPACITY);
  18.     }
  19.  
  20.     /**
  21.      * Create linear probing hash table of given capacity
  22.      */
  23.     public SymbolTable(int capacity) {
  24.         N = 0;
  25.         M = capacity;
  26.         keys = new String[M];
  27.         vals = new Character[M];
  28.     }
  29.  
  30.     /**
  31.      * Return the number of key-value pairs in the symbol table
  32.      */
  33.     public int size() {
  34.         return N;
  35.     }
  36.  
  37.     /**
  38.      * Is the symbol table empty?
  39.      */
  40.     public boolean isEmpty() {
  41.         return size() == 0;
  42.     }
  43.  
  44.     /**
  45.      * Does a key-value pair with the given key exist in the symbol table?
  46.      */
  47.     public boolean contains(String key) {
  48.         return get(key) != null;
  49.     }
  50.    
  51.  
  52.     /**
  53.      * Hash function for keys - returns value between 0 and M-1
  54.      */
  55.     public int hash(String key) {
  56.         int i;
  57.         int v = 0;
  58.  
  59.         for (i = 0; i < key.length(); i++) {
  60.             v += key.charAt(i);
  61.         }
  62.         return v % M;
  63.     }
  64.  
  65.     /**
  66.      * Insert the key-value pair into the symbol table
  67.      */
  68.     public void put(String key, Character val) {
  69.  
  70.         if (keys[hash(key)] == null || keys[hash(key)].equals(key)) {
  71.        
  72.         keys[hash(key)] = key;
  73.         vals[hash(key)] = val;
  74.        
  75.         } else {
  76.             for (int i = hash(key)+1; i % M != hash(key); i++){
  77.          
  78.                 if (keys[i % M] == null || keys[i % M].equals(key)) {    
  79.                     keys[i % M] = key;
  80.                     vals[i % M] = val;
  81.                     return;
  82.                     }
  83.             }
  84.         }
  85.        
  86.         }
  87.      // dummy code
  88.  
  89.     /**
  90.      * Return the value associated with the given key, null if no such value
  91.      */
  92.     public Character get(String key) {
  93.         if (keys[hash(key)] == null) {
  94.         return null;
  95.         } else if (keys[hash(key)].equals(key)){
  96.             return vals[hash(key)];
  97.         } else {
  98.             for (int i = hash(key)+1; i % M != hash(key); i++) {
  99.                 if (keys[i % M] .equals(key)){
  100.                     return vals[i % M];
  101.                 }
  102.             }
  103.         }
  104.         return null;
  105.     } // dummy code
  106.  
  107.     /**
  108.      * Delete the key (and associated value) from the symbol table
  109.      */
  110.     public void delete(String key) {
  111.         int tempIndex = 8;
  112.         if (keys[hash(key)].equals(key)) {
  113.             keys[hash(key)] = null;
  114.             vals[hash(key)] = null;
  115.             tempIndex = hash(key);
  116.         } else {
  117.             for (int i = hash(key)+1; i % M != hash(key); i++) {
  118.                 if(keys[i % M] == null){
  119.                     break;
  120.                 } else if (keys[i % M].equals(key)) {
  121.                     keys[i % M] = null;
  122.                     vals[i % M] = null;
  123.                     tempIndex = i % M;
  124.                 }
  125.             }
  126.              
  127.         }
  128.         for (int i = hash(key)+1; i % M != hash(key); i++){
  129.            
  130.             if(keys[i % M] == null){
  131.                
  132.                 return;
  133.             } else if (hash(keys[i % M]) == hash(key)  || (hash(keys[i % M]) == tempIndex)){
  134.                 keys[tempIndex] = keys[i % M];
  135.                 vals[tempIndex] = vals[i % M];
  136.      
  137.                 tempIndex = i % M;
  138.                    
  139.                 keys[i % M] = null;
  140.                 vals[i % M] = null;
  141.             } else if (hash(keys[i % M]) < tempIndex){
  142.                
  143.                 keys[tempIndex] = keys[i % M];
  144.                 vals[tempIndex] = vals[i % M];
  145.                
  146.                 tempIndex = i % M;
  147.                
  148.                 keys[i % M] = null;
  149.                 vals[i % M] = null;
  150.                
  151.                
  152.             }
  153.         }
  154.         return;
  155.     } // dummy code
  156.  
  157.     /**
  158.      * Print the contents of the symbol table
  159.      */
  160.     public void dump() {
  161.         String str = "";
  162.  
  163.         for (int i = 0; i < M; i++) {
  164.             str = str + i + ". " + vals[i];
  165.             if (keys[i] != null) {
  166.                 str = str + " " + keys[i] + " (";
  167.                 str = str + hash(keys[i]) + ")";
  168.             } else {
  169.                 str = str + " -";
  170.             }
  171.             System.out.println(str);
  172.             str = "";
  173.         }
  174.     }
  175. }
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