HashTables and HashCode

Instructions:

1. Record.java contains a class Record that contains two fields: a key string and some auxiliary data (a list of sequence positions). For hashing, you'll care only about the key string.

2. StringTable.java implements a hash table that maps key strings to records containing these strings.

You will need to fill in some of the methods in the StringTable class to get your hash table working. In particular, you'll have to implement

3. StringTable() to construct a new, empty hash table;

4. insert() to insert a new record into the table, unless another record with the same key string already exists;

5. find() to locate the record (if any) in the table with a specified key string;

6. remove() to find and remove the record (if any) in the table with a specified key string;

7. toIndex() to map the hashcode for a key string to an index in the table.

FINISH THESE METHODS!

Provided is a function stringToHashCode() that converts key strings to integer hashcodes. Read the comments in Record.java and StringTable.java to better understand what you need to implement.

This is the Record.java class:

import java.util.ArrayList;

public class Record {

public String key;

public ArrayList positions;

public Record(String s)

{

key = s;

positions = new ArrayList(1);

}

}

This is the StringTable.java class:

import java.util.Hashtable;

import java.util.LinkedList;

//

// STRINGTABLE.JAVA

// A hash table mapping Strings to their positions in the the pattern sequence

// You get to fill in the methods for this part.

//

public class StringTable {

private LinkedList[] buckets; // is this the linked list that is used for chaining?

private int nBuckets; // number of buckets that make up the table

//

// number of records currently stored in table --

// must be maintained by all operations

//

public int size;

//

// Create an empty table with nBuckets buckets

//

@SuppressWarnings("unchecked")

public StringTable(int nBuckets)

{

this.nBuckets = nBuckets;

buckets = new LinkedList[nBuckets];

this.size = 0;

// TODO - fill in the rest of this method to initialize your table

}

/**

* insert - inserts a record to the StringTable

*

* @param r

* @return true if the insertion was successful, or false if a

* record with the same key is already present in the table.

*/

public boolean insert(Record r)

{

// TODO - implement this method

if(buckets.equals(r)) {

return false;

}

else {

ht.put(r.key, r);

return true;

}

}

/**

* find - finds the record with a key matching the input.

*

* @param key

* @return the record matching this key, or null if it does not exist.

*/

public Record find(String key)

{

// TODO - implement this method

return null;

}

/**

* remove - finds a record in the StringTable with the given key

* and removes the record if it exists.

*

* @param key

*/

public void remove(String key)

{

// TODO - implement this method

}

/**

* toIndex - convert a string's hashcode to a table index

*

* As part of your hashing computation, you need to convert the

* hashcode of a key string (computed using the provided function

* stringToHashCode) to a bucket index in the hash table.

*

* You should use a multiplicative hashing strategy to convert

* hashcodes to indices. If you want to use the fixed-point

* computation with bit shifts, you may assume that nBuckets is a

* power of 2 and compute its log at construction time.

* Otherwise, you can use the floating-point computation.

*/

private int toIndex(int hashcode)

{

// Fill in your own hash function here

return 0;

}

/**

* stringToHashCode

* Converts a String key into an integer that serves as input to

* hash functions. This mapping is based on the idea of integer

* multiplicative hashing, where we do multiplies for successive

* characters of the key (adding in the position to distinguish

* permutations of the key from each other).

*

* @param string to hash

* @returns hashcode

*/

int stringToHashCode(String key)

{

int A = 1952786893;

int v = A;

for (int j = 0; j < key.length(); j++)

{

char c = key.charAt(j);

v = A * (v + (int) c + j) >> 16;

}

return v;

}

/**

* Use this function to print out your table for debugging

* purposes.

*/

public String toString()

{

StringBuilder sb = new StringBuilder();

for(int i = 0; i < nBuckets; i++)

{

sb.append(i+ " ");

if (buckets[i] == null)

{

sb.append(" ");

continue;

}

for (Record r : buckets[i])

{

sb.append(r.key + " ");

}

sb.append(" ");

}

return sb.toString();

}

}