Computer Science/61b/Homework/hw6/dict/HashTableChained.java - Revision history

Lensovet: Lensovet moved page CS/61b/Homework/hw6/dict/HashTableChained.java to Computer Science/61b/Homework/hw6/dict/HashTableChained.java

2023-02-20T03:51:35Z

Lensovet moved page CS/61b/Homework/hw6/dict/HashTableChained.java to Computer Science/61b/Homework/hw6/dict/HashTableChained.java

Lensovet: moved CS 61b/Homework/hw6/dict/HashTableChained.java to CS/61b/Homework/hw6/dict/HashTableChained.java: fix cs 61b hierarchy

2010-11-14T06:00:20Z

moved CS 61b/Homework/hw6/dict/HashTableChained.java to CS/61b/Homework/hw6/dict/HashTableChained.java: fix cs 61b hierarchy

Lensovet: spacing + a comment

2007-09-22T05:59:08Z

spacing + a comment

Lensovet at 08:39, 11 December 2006

2006-12-11T08:39:11Z

New page

{{code}}
/* HashTableChained.java */

package dict;

/**
* HashTableChained implements a Dictionary as a hash table with chaining.
* All objects used as keys must have a valid hashCode() method, which is
* used to determine which bucket of the hash table an entry is stored in.
* Each object's hashCode() is presumed to return an int between
* Integer.MIN_VALUE and Integer.MAX_VALUE. The HashTableChained class
* implements only the compression function, which maps the hash code to
* a bucket in the table's range.
*
* DO NOT CHANGE ANY PROTOTYPES IN THIS FILE.
**/

public class HashTableChained implements Dictionary {

/**
* Place any data fields here.
**/

list.DList[] table;
int tablesize;

/**
* Construct a new empty hash table intended to hold roughly sizeEstimate
* entries. (The precise number of buckets is up to you, but we recommend
* you use a prime number, and shoot for a load factor between 0.5 and 1.)
**/

public HashTableChained(int sizeEstimate) {
int targetsize = (int) Math.round(sizeEstimate); // originally this actually gave a load factor of ~1.25
table = new list.DList[targetsize];
}

/**
* Construct a new empty hash table with a default size. Say, a prime in
* the neighborhood of 100.
**/

public HashTableChained() {
table = new list.DList[101];
}

/**
* Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE
* to a value in the range 0...(size of hash table) - 1.
*
* This function should have package protection (so we can test it), and
* should be used by insert, find, and remove.
**/

int compFunction(int code) {
/* int returnval = (((6*code + 11) % 536870911) % table.length);
if (returnval < 0) {
returnval = returnval + table.length;
} */
int returnval = Math.abs((((6*code + 11) % 67108865) % table.length));
return returnval;
}

/**
* Returns the number of entries stored in the dictionary. Entries with
* the same key (or even the same key and value) each still count as
* a separate entry.
* @return number of entries in the dictionary.
**/

public int size() {
return tablesize;
}

/**
* Tests if the dictionary is empty.
*
* @return true if the dictionary has no entries; false otherwise.
**/

public boolean isEmpty() {
if (tablesize == 0) {
return true;
} else {
return false;
}
}

/**
* Create a new Entry object referencing the input key and associated value,
* and insert the entry into the dictionary. Return a reference to the new
* entry. Multiple entries with the same key (or even the same key and
* value) can coexist in the dictionary.
*
* This method should run in O(1) time if the number of collisions is small.
*
* @param key the key by which the entry can be retrieved.
* @param value an arbitrary object.
* @return an entry containing the key and value.
**/

public Entry insert(Object key, Object value) {
Entry insertion = new Entry();
insertion.key = key;
insertion.value = value;
int targetindex = compFunction(key.hashCode());
if (table[targetindex] == null) {
list.DList newlist = new list.DList();
newlist.insertFront(insertion);
table[targetindex] = newlist;
} else {
table[targetindex].insertFront(insertion);
} tablesize++;
return insertion;
}

/**
* Search for an entry with the specified key. If such an entry is found,
* return it; otherwise return null. If several entries have the specified
* key, choose one arbitrarily and return it.
*
* This method should run in O(1) time if the number of collisions is small.
*
* @param key the search key.
* @return an entry containing the key and an associated value, or null if
* no entry contains the specified key.
**/

public Entry find(Object key) {
int targetindex = compFunction(key.hashCode());
list.DList targetlist = table[targetindex];
if (targetlist != null) {
list.ListNode curnode = null;
try { // since we're using a DList implementation that throws exceptions, this is required
curnode = targetlist.front();
while (!((Entry) curnode.item()).key().equals(key)) { // if the current key is not equals() to the one we're looking for, look in the next node
curnode = curnode.next();
} return (Entry) curnode.item(); // found a match w/out throwing exceptions
} catch (list.InvalidNodeException e) { // no match for key in the list
return null;
}
} else {
return null;
}
}

/**
* Remove an entry with the specified key. If such an entry is found,
* remove it from the table and return it; otherwise return null.
* If several entries have the specified key, choose one arbitrarily, then
* remove and return it.
*
* This method should run in O(1) time if the number of collisions is small.
*
* @param key the search key.
* @return an entry containing the key and an associated value, or null if
* no entry contains the specified key.
*/

public Entry remove(Object key) {
int targetindex = compFunction(key.hashCode());
list.DList targetlist = table[targetindex];
if (targetlist != null) {
list.ListNode curnode = null;
try { // since we're using a DList implementation that throws exceptions, this is required
curnode = targetlist.front();
while (!((Entry) curnode.item()).key().equals(key)) { // if the current key is not equals() to the one we're looking for, look in the next node
curnode = curnode.next();
}
Entry returned = (Entry) curnode.item(); // found a match w/out throwing exceptions
curnode.remove();
tablesize--;
return returned;
} catch (list.InvalidNodeException e) { // no match for key in the list
return null;
}
} else {
return null;
}
}

/**
* Remove all entries from the dictionary.
*/
public void makeEmpty() {
int targetsize = table.length - 1;
table = new list.DList[targetsize];
tablesize = 0;
}

public void printHistogram() {
String histog = "";
int cols = 0;
for (int i=0; i<table.length; i++) {
if (table[i] == null) {
histog = histog + " 0";
} else {
histog = histog + " " + table[i].length();
cols = cols + table[i].length() - 1;
}
}
System.out.println(histog);
System.out.println("Number of collisions is " + cols + " and table size is " + table.length);
}
}

← Older revision	Revision as of 03:51, 20 February 2023
(No difference)

← Older revision	Revision as of 06:00, 14 November 2010
(No difference)

@@ Line 46: / Line 46: @@
   	/**
- 	*  Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE
+ 	 *  Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE
   	 *  to a value in the range 0...(size of hash table) - 1.
+  	 *
@@ Line 54: / Line 54: @@
   	int compFunction(int code) {
- /*		int returnval = (((6*code + 11) % 536870911) % table.length);
+ 	 	/* int returnval = (((6*code + 11) % 536870911) % table.length);
   		if (returnval < 0) {
   			returnval = returnval + table.length;
@@ Line 88: / Line 88: @@
   	/**
- 	*  Create a new Entry object referencing the input key and associated value,
+ 	 *  Create a new Entry object referencing the input key and associated value,
   	 *  and insert the entry into the dictionary.  Return a reference to the new
   	 *  entry.  Multiple entries with the same key (or even the same key and
@@ Line 111: / Line 111: @@
   		} else {
   			table[targetindex].insertFront(insertion);
   		} tablesize++;
   		return insertion;
+  	}
@@ Line 136: / Line 137: @@
   				while (!((Entry) curnode.item()).key().equals(key)) { // if the current key is not equals() to the one we're looking for, look in the next node
   					curnode = curnode.next();
   				} return (Entry) curnode.item(); // found a match w/out throwing exceptions
   			} catch (list.InvalidNodeException e) { // no match for key in the list
   				return null;
@@ Line 181: / Line 183: @@
   	/**
- 	*  Remove all entries from the dictionary.
+ 	 *  Remove all entries from the dictionary.
   	 */
   	public void makeEmpty() {
@@ Line 189: / Line 191: @@
+  	}
   	public void printHistogram() {
   		String histog = "";