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));
}
}
public abstract class OpenAddressHashtable<K,V> implements OurHashtable<K,V> {
protected int tableSize = 101;
private int size = 0; // number of elements
private KVPair<K,V> [] elements;
private int collisionCounter = 0; // incremented every time there is a collision
public OpenAddressHashtable() {
elements = new KVPair[tableSize];
}
/**
* @return true if the table is empty, false otherwise
**/
public boolean isEmpty() {
return true;
}
/**
* @return the number of elements in the table
**/
public int size() {
return 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) {
// call getNextIndex(key, 0) to get the first spot
// if the spot is null, add the element there
// if it's not null, increment collision counter
// and call getNextIndex again
// repeat until a spot is found
// if tried for 'tableSize' times, throw an exception
// indicating that no spot is available
}
// implemented in subclasses, returns an index based on the key and a probe number
abstract protected int getNextIndex(K key, int probeNumber);
public int getCollisionCounter() {
return collisionCounter;
}
/**
* 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) {
return null;
}
/**
* Clears all elements from a given table.
* The resulting table is empty.
*/
public void clear() {
}
}
public class LinearProbingHashtable<K,V> extends OpenAddressHashtable<K,V> {
@Override
protected int getNextIndex(K key, int probeNumber) {
// TODO Auto-generated method stub
return 0;
}
}