Advertisement
Guest User

Untitled

a guest
Apr 24th, 2015
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.61 KB | None | 0 0
  1. package student_classes;
  2. import java.util.ArrayList;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. /**
  7.  * This is a truly minimal implementation of the well-known HashTable
  8.  * class that is still defined in Java (qv). Essentially, a HashTable
  9.  * allows users to associate values with keys in O(1) time (amortized
  10.  * over the life of the running application).
  11.  *
  12.  * Note: this implementation throws NullPointerExceptions if <code>put</code>
  13.  * is called with either a null key or a null value.
  14.  *
  15.  * Moreover, instead of returning Enumerations (old school), this version
  16.  * returns Iterators for its keys and values.
  17.  *
  18.  * You could theoretically use objects of this class as a hash table, but
  19.  * too much would still need to be done, for real applications.
  20.  *
  21.  * @author UMD CS Department.
  22.  *
  23.  * @param <E> ///> Keys type
  24.  * @param <V> ///> Values type.
  25.  */
  26. public class HashTbl<E, V> {
  27.     /* define your properties here */
  28.     private final int defaultSize=64;
  29.     private Object buckets[] = new Object[ defaultSize ];
  30.     /** Only one public constructor is provided ... in reality, we'd
  31.      * probably like a few more that allowed us to control growth rate,
  32.      * initial size, etc.
  33.      */
  34.     public HashTbl() {
  35.         for (int i = 0; i < defaultSize; i++){
  36.             buckets[i] = new ArrayList<Object[]>();
  37.         }
  38.     }
  39.     /**
  40.      * Installs the <code>value</code> on the <code>key</code> in this
  41.      * table. Note, if either parameter is <code>null</code> a
  42.      * <code>NullPointerException</code> is signaled.
  43.      * @param key
  44.      * @param value
  45.      */
  46.     public void put( E key, V value ) {
  47.         if (key == null || value == null)
  48.             throw new NullPointerException();
  49.         else {
  50.             int hash = key.hashCode();
  51.             ArrayList<Object[]> bucket = (ArrayList<Object[]>)buckets[hash % defaultSize];
  52.             boolean contains = false;
  53.             for (Object[] obj: bucket){
  54.                 if (key.equals(obj[0])){
  55.                     contains = true;
  56.                     obj[1] = value;
  57.                 }
  58.             }
  59.            
  60.             if (!contains){
  61.                 Object[] arr = new Object[2];
  62.                 arr[0] = key;
  63.                 arr[1] = value;
  64.                 bucket.add(arr);
  65.             }
  66.         }
  67.     }
  68.    
  69.     /**
  70.      * Returns the value associated with <code>key</code>. Because this is a table,
  71.      * nulls are not allowed, therefore if a <code>null</code> is returned ... we
  72.      * know that the key wasn't found.
  73.      * @param key
  74.      * @return
  75.      */
  76.     public V get( E key ) {
  77.         int hash = key.hashCode();
  78.         ArrayList<Object[]> bucket = (ArrayList<Object[]>)buckets[hash % defaultSize];
  79.         V value = null;
  80.         for (Object[] obj: bucket){
  81.             if (key.equals(obj[0])){
  82.                 value = (V)obj[1];
  83.             }
  84.         }
  85.         return value;
  86.     }
  87.    
  88.     private ArrayList<E> getKeys() {
  89.         ArrayList<E> keyList = new ArrayList<E>();
  90.         for (int i = 0; i < defaultSize; i++){
  91.             for (int j = 0; j < ((ArrayList<Object[]>)buckets[i]).size(); j++){
  92.                 keyList.add((E)((ArrayList<Object[]>)buckets[i]).get(j)[0]);
  93.                
  94.             }
  95.         }
  96.         return keyList;
  97.     }
  98.    
  99.     private ArrayList<V> getValues() {
  100.         ArrayList<V> valueList = new ArrayList<V>();
  101.         for (int i = 0; i < defaultSize; i++){
  102.             for (int j = 0; j < ((ArrayList<Object[]>)buckets[i]).size(); j++){
  103.                 valueList.add((V)((ArrayList<Object[]>)buckets[i]).get(j)[1]);
  104.                
  105.             }
  106.         }
  107.         return valueList;
  108.     }
  109.    
  110.     /**
  111.      * Returns an Iterator over the <code>key</code>s in this table; note, no particular
  112.      * order is specified here.
  113.      * @return an Iterator over Keys.
  114.      */
  115.     public Iterator<E> keys() {
  116.         return getKeys().iterator();
  117.     }
  118.     /**
  119.      * Returns an Iterator over the <code>value</code>s in the table; note, no
  120.      * particular order is assumed.
  121.      * @return
  122.      */
  123.     public Iterator<V> values() {
  124.         return getValues().iterator();
  125.     }
  126.  
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement