[solved]-Hashing Strings Storing Strings Hash Table Requires Little Bit Work Integers Good Hash Fun Q39036628

Hashing strings

Storing strings in a hash table requires a little bit more workthan integers, because good hash functions over stringsare a little more difficult to come up with. For this question, youwill implement a hash table of Strings, usingseparate chaining. That is, your hash table isactually an array of linked lists of table entries. All Stringswhich hash to the same value are stored in the same linked list.When a new item is added to a list, it is added at the front of thelist (the easy way to do it; no special cases are needed). To findan item in the table, the hash value specifies the location of thelinked list to be searched, and the list is traversed until theitem is found (or the list ends).

This type of hash table is commonly used as a symbol table incompilers. The same identifier may be used multiple times in aprogram, and all instances of a given identifier are found in thesame list. When the compiler searches for an identifier, it willfind the most recent occurrence of it, that is, it finds the mostrecent declaration of the identifier. This type of symbol tablenicely implements scoping rules for modern programminglanguages.

There are two main criteria for a good hashing algorithm. First,it should work well, providing a good distributionof the hash keys over the table entries. Secondly, it should workfast, since it will be called frequently.

The hash function you will implement is Dan Bernstein’s, overalla very effective hash function:

int value = 5381;for (int i = 0; i < key.length(); i++) { value = value * 33 + key.charAt(i);}value &= 0x7fffffff;value %= size;

The function as shown involves a multiplication inside the forloop. This multiplication can be replaced by two faster operations,a left-shift bitwise operation (the << operator in Java) andan addition. You should replace this multiplication with these twooperations to produce an equivalent function. (Hint: the left-shiftoperation has the same effect as multiplying by a power of 2.)There is also no concern about overflow, since overflow is assumedto occur during the manipulations and is corrected later (usinganother bitwise operation). Which operation ensures that thereturned hash value is not negative? (Hint: think of which bit isthe sign bit in a signed integer value.)

Part of the implementation is provided for you in the fileHashTable.java. Note that the constructor for this class takes aninteger size parameter. The actual size for the hash table ischosen from a list of prime numbers (the smallest value from thislist that is greater than or equal to the “suggested” size).

An instance variable probes (part of the free code) is used tocount the number of probes taken when finding an item in the table.Also add code to the find method to actually count probes. A publicmethod to reset this variable to zero, and another to return thenumber of probes is also part of the free code.

Your hash table will be tested using the file a4q2words.txt.This file contains 100,000 words, one word per line. Sample outputwill be provided.

class HashTableEntry{
private String theEntry;
private HashTableEntry link;
public HashTableEntry(String item, HashTableEntry next){
theEntry = item; link = next;
}
public String getEntry(){ return theEntry; }
public void setEntry(String item){ theEntry = item; }
public HashTableEntry getLink(){ return link; }
public void setLink(HashTableEntry next){ link = next; }
}// class HashTableEntry

public class HashTable{
// prime numbers for array sizes
private static int [] primes =
{101,199,307,401,503,601,701,809,907,1009,1201,1409,1601,
1801,2003,2503,3001,3511,4001,4507,5003,5501,6007,6491,
7001,7499,8009,8501,9001,9497,10007,12007,13999,16001,
18013,19997,24989,30011,34981,39989,45007,49999,59999,
70001,79999,90001,100003};
  
private HashTableEntry [] array;
private int probes;
  
public HashTable(int newSize){
probes = 0;
}
  
public int hash(String item){
return 0;
};
  
public int getProbes(){ return probes; }
public void resetProbes(){ probes = 0; }
  
public void insert(String item){
}// insert
  
public HashTableEntry find(String item){
return null;
}// find
  
}// class HashTable

Expert Answer

---

Answer to Hashing strings Storing strings in a hash table requires a little bit more work than integers, because good hash functio… . . .