CSci 2101: Hashtables

JUnit Test code for Hashtables

More tests are needed.

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import org.junit.Before;
import org.junit.Test;


public class TestHashTable {
	OurHashtable<Integer, String> emptyTable = new HashtableSeparateChaining<Integer, String>();
	OurHashtable<Integer, String> fourElementTable = new HashtableSeparateChaining<Integer, String>();
	OurHashtable<Integer, String> repeatedKeysTable= new HashtableSeparateChaining<Integer, String>();
	
	
	@Before
	public void setUp() {
		// setting up fourElement table, no repeats	
		fourElementTable.put(4,"apple");
		fourElementTable.put(6,"banana");
		fourElementTable.put(1,"strawberry");
		fourElementTable.put(3,"kiwi");
		
		// setting up repeatedKeysTable, assuming 20 buckets
		repeatedKeysTable.put(4,"apple");
		repeatedKeysTable.put(3,"banana");
		repeatedKeysTable.put(44,"strawberry");
		repeatedKeysTable.put(23,"kiwi");		
	}
	
	@Test
	public void TestEmpty() {
		assertTrue(emptyTable.isEmpty());
		assertEquals(0,emptyTable.size());
	}
	
	@Test
	public void TestNonEmpty() {
		emptyTable.put(4,"apple");
		assertFalse(emptyTable.isEmpty());
		assertEquals(1,emptyTable.size());
	}
	
	@Test
	public void TestPutGetOneElement() {
		emptyTable.put(4,"apple");
		assertEquals("apple",emptyTable.get(4));
	}
	
	@Test
	public void TestGetFromEmpty() {
		assertNull(emptyTable.get(4));
	}
	
	@Test
	public void TestGet() {
		assertEquals("strawberry",fourElementTable.get(1));
		assertEquals("banana",fourElementTable.get(6));
	}	
	
	@Test
	public void TestGetRepeated() {
		assertEquals("apple",repeatedKeysTable.get(4));
		assertEquals("banana",repeatedKeysTable.get(3));
		assertEquals("strawberry",repeatedKeysTable.get(44));
		assertEquals("kiwi",repeatedKeysTable.get(23));
	}	
	
	@Test
	public void TestGetNotThere() {
		assertNull(fourElementTable.get(5));
	}	
	
	@Test (expected=NullPointerException.class)
	public void TestNullKey() {
		assertNull(fourElementTable.get(null));
	}
	
	@Test
	public void TestSize() {
		assertEquals(4,fourElementTable.size());
		assertEquals(4,repeatedKeysTable.size());
	}
	
	@Test
	public void TestClear() {
		fourElementTable.clear();
		assertTrue(fourElementTable.isEmpty());
		assertEquals(0,fourElementTable.size());
		assertNull(fourElementTable.get(4));
	}
	
	@Test
	public void TestClearRepeated() {
		repeatedKeysTable.clear();
		assertTrue(repeatedKeysTable.isEmpty());
		assertEquals(0,repeatedKeysTable.size());
		assertNull(repeatedKeysTable.get(4));
	}
}

/**
 * Hashtable interface for CSci 2101 Summer 2010
 * @author Elena Machkasova
 *
 * @param <K> - key type
 * @param <V> - value type
 */

public interface OurHashtable<K, V> {
	/**
	 * @return true if the table is empty, false otherwise
	 **/
	public boolean isEmpty();
	
	/**
	 * @return the number of elements in the table
	 **/
	public int size();
	/**
	 * Adds a given value indexed with a given key to the table according to the
	 * binary search structure
	 * 
	 * @param key
	 *            - the key of the given element
	 * @param value
	 *            - the value of the given element          
	 */
	public void put(K key, V value);

	/**
	 * returns a value associated with the given key in this table.
	 * If multiple values are associated with this key, any one may be returned.
	 * If there is no element associated with this key, null is returned.
	 * 
	 * @param key
	 *            - the key to search for.
	 * @return - a value to which the specified key is mapped, or null if this
	 *         table contains no mapping for the key
	 * @throws NullPointerException if the key is null        
	 */
	public V get(K key);
	
	/**
	 * Clears all elements from a given table.
	 * The resulting table is empty.
	 */
	public void clear();

}

import java.util.ArrayList;


public class HashtableSeparateChaining<K, V> implements OurHashtable<K,V> {
	private int numberBuckets; // the number of "buckets", default 20
	private int size = 0; // number of elements 
	private ArrayList<KVPair<K,V>> [] buckets;
	
	// default number of buckets is 20
	public HashtableSeparateChaining() {
		this.numberBuckets = 20;
		setup();
	}
	
	public HashtableSeparateChaining(int numberBuckets) {
		this.numberBuckets = numberBuckets;
		setup();
	}
	
	/**
	 * sets up initial empty arraylists based on the number of "buckets"
	 */
	private void setup() {
		buckets = new ArrayList[numberBuckets]; // must create an array 
												// of a "raw" type
		for (int i = 0; i < numberBuckets; ++i) {
			buckets[i] = new ArrayList<KVPair<K,V>>();
		}
	}
	
	@Override
	public void clear() {
		for (int i = 0; i < numberBuckets; ++i) {
			buckets[i] = new ArrayList<KVPair<K,V>>();
		}	
	}

	@Override
	public V get(K key) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isEmpty() {
		return (size == 0);
	}

	@Override
	public void put(K key, V value) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public int size() {
		return size;
	}
	
}

/**
 * A class for storing key-value pairs 
 * mypair.key gives the key, mypair.value gives the value
 * 
 * @author Elena Machkasova
 *
 * @param <K> - key type 
 * @param <V> - value type 
 */

public class KVPair<K, V> {
	final public K key;
	final public V value;
	
	public KVPair(K key, V value) {
		this.key = key;
		this.value = value;
	}
	
	public boolean equals(Object other) {
		if (! (other instanceof KVPair)) return false;
		KVPair<K,V> otherPair = (KVPair<K,V>) other;
		return (key.equals(otherPair.key) && value.equals(otherPair.value));
	}
}

CSci 2101 course web site.