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
	 *         tree 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 tree 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<Pair<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<Pair<K,V>>();
		}
	}
	
	@Override
	public void clear() {
		for (int i = 0; i < numberBuckets; ++i) {
			buckets[i] = new ArrayList<Pair<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 generated during
 * traversals of a Binary Search Tree
 * mypair.key gives the key, mypair.value gives the value
 * 
 * @author Elena Machkasova
 *
 * @param <K> - key type (must be comparable to itself)
 * @param <V> - value type 
 */

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

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.