Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package student_classes;
- import java.util.ArrayList;
- import java.util.Iterator;
- import java.util.LinkedList;
- import java.util.List;
- /**
- * This is a truly minimal implementation of the well-known HashTable
- * class that is still defined in Java (qv). Essentially, a HashTable
- * allows users to associate values with keys in O(1) time (amortized
- * over the life of the running application).
- *
- * Note: this implementation throws NullPointerExceptions if <code>put</code>
- * is called with either a null key or a null value.
- *
- * Moreover, instead of returning Enumerations (old school), this version
- * returns Iterators for its keys and values.
- *
- * You could theoretically use objects of this class as a hash table, but
- * too much would still need to be done, for real applications.
- *
- * @author UMD CS Department.
- *
- * @param <E> ///> Keys type
- * @param <V> ///> Values type.
- */
- public class HashTbl<E, V> {
- /* define your properties here */
- private final int defaultSize=64;
- private Object buckets[] = new Object[ defaultSize ];
- /** Only one public constructor is provided ... in reality, we'd
- * probably like a few more that allowed us to control growth rate,
- * initial size, etc.
- */
- public HashTbl() {
- for (int i = 0; i < defaultSize; i++){
- buckets[i] = new ArrayList<Object[]>();
- }
- }
- /**
- * Installs the <code>value</code> on the <code>key</code> in this
- * table. Note, if either parameter is <code>null</code> a
- * <code>NullPointerException</code> is signaled.
- * @param key
- * @param value
- */
- public void put( E key, V value ) {
- if (key == null || value == null)
- throw new NullPointerException();
- else {
- int hash = key.hashCode();
- ArrayList<Object[]> bucket = (ArrayList<Object[]>)buckets[hash % defaultSize];
- boolean contains = false;
- for (Object[] obj: bucket){
- if (key.equals(obj[0])){
- contains = true;
- obj[1] = value;
- }
- }
- if (!contains){
- Object[] arr = new Object[2];
- arr[0] = key;
- arr[1] = value;
- bucket.add(arr);
- }
- }
- }
- /**
- * Returns the value associated with <code>key</code>. Because this is a table,
- * nulls are not allowed, therefore if a <code>null</code> is returned ... we
- * know that the key wasn't found.
- * @param key
- * @return
- */
- public V get( E key ) {
- int hash = key.hashCode();
- ArrayList<Object[]> bucket = (ArrayList<Object[]>)buckets[hash % defaultSize];
- V value = null;
- for (Object[] obj: bucket){
- if (key.equals(obj[0])){
- value = (V)obj[1];
- }
- }
- return value;
- }
- private ArrayList<E> getKeys() {
- ArrayList<E> keyList = new ArrayList<E>();
- for (int i = 0; i < defaultSize; i++){
- for (int j = 0; j < ((ArrayList<Object[]>)buckets[i]).size(); j++){
- keyList.add((E)((ArrayList<Object[]>)buckets[i]).get(j)[0]);
- }
- }
- return keyList;
- }
- private ArrayList<V> getValues() {
- ArrayList<V> valueList = new ArrayList<V>();
- for (int i = 0; i < defaultSize; i++){
- for (int j = 0; j < ((ArrayList<Object[]>)buckets[i]).size(); j++){
- valueList.add((V)((ArrayList<Object[]>)buckets[i]).get(j)[1]);
- }
- }
- return valueList;
- }
- /**
- * Returns an Iterator over the <code>key</code>s in this table; note, no particular
- * order is specified here.
- * @return an Iterator over Keys.
- */
- public Iterator<E> keys() {
- return getKeys().iterator();
- }
- /**
- * Returns an Iterator over the <code>value</code>s in the table; note, no
- * particular order is assumed.
- * @return
- */
- public Iterator<V> values() {
- return getValues().iterator();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement