Question

0. Introduction.

This involves designing a perfect hash function for a small set of strings. It demonstrates that if the set of possible keys is small, then a perfect hash function need not be hard to design, or hard to understand.

1. Theory.

A hash table is an array that associates keys with values. A hash function takes a key as its argument, and returns an index in the array. The object that appears at the index is the key’s value. A hash function may return the same index for two different keys. This is called a collision. A collision is undesirable if two keys with the same index have different values. A hash function that has no collisions for a set of keys is said to be perfect for that set. It may be perfect for some sets of keys, but not for others.
      Most modern programming languages use a small set of reserved names as operators, punctuation, and syntactic markers. Reserved names are also sometimes called reserved words or keywords. For example, Java is said to use 55 keywords, like if, private, while, etc. A compiler for a programming language must be able to test if each name in a program is reserved. The program may be hundreds or thousands of pages long, and may include thousands or millions of names, so the test must be done efficiently. It might be implemented using a hash table and a perfect hash function.
      Here’s how the test works. Suppose that the hash table T is an array of strings. Each time the compiler reads a name N, it calls a perfect hash function h to compute an index h(N). If h(N) is a legal index for T, and T[h(N)] = N, then the name is reserved, otherwise it is not. If there are unused elements in T, then they are empty strings "", because an empty string can’t be a keyword. If we measure the efficiency of a test by the number of string comparisons it performs, then the test requires only O(1) comparisons. Of course this works only if h is perfect for the set of reserved names.

2. Example.

Imagine that there is a very simple programming language which uses the following twelve reserved names.

and	else	or
begin	end	return
define	if	then
do	not	while

We might define a perfect hash function for these reserved names like this. We get one or more characters from each name. Then we convert each character to an integer—this is easy, because characters are already represented as small nonnegative integers. In the ASCII and Unicode character sets, the characters 'a' through 'z' are represented as the integers 97 through 122, without gaps. Finally, we do arithmetic on the integers to obtain an index into the hash table. We can choose the characters, and the arithmetic operations, so that no two reserved names result in the same index. For example, if we define the hash function h to add the first and second characters of each name, then we get the following indexes.

h("and")	=	207
h("begin")	=	199
h("define")	=	201
h("do")	=	211
h("else")	=	209
h("end")	=	211
h("if")	=	207
h("not")	=	221
h("or")	=	225
h("return")	=	215
h("then")	=	220
h("while")	=	223

This definition for h does not result in a perfect hash function, because it has collisions. For example, the strings "and" and "if" result in the index 207. Similarly, the strings "do" and "end" result in the index 211. We either didn’t choose the right characters from each string, or we didn’t choose the right operations, or both. Unfortunately, there is no good theory about how to define h. The best we can do is try various definitions, by trial and error, until we find one that is perfect.

3. Implementation.

For this project, you must design a perfect hash function for the reserved names shown in the previous section. To do that, write a small test class Hasher, and run it with various definitions for the function hash. The class’s main method calls hash for each reserved name, and writes indexes to standard output. For full credit, no two reserved names can have the same index.

class Hasher  
{  
  private static final String [] reserved =  
   { "and",  
     "begin",  
     "define",  
     "do",  
     "else",  
     "end",  
     "if",  
     "not",  
     "or",  
     "return",  
     "then",  
     "while" };  
  
  private static int hash(String name)  
  {  
    //  Your code goes here.  
  }  
  
  public static void main(String [] args)  
  {  
    for (int index = 0; index < reserved.length ; index += 1)  
    {  
      System.out.print("h(\"" + reserved[index] + "\") = ");  
      System.out.print(hash(reserved[index]));  
      System.out.println();  
    }  
  }  
}

Your method hash must work in O(1) time, without loops or recursions. It must not use if’s, switch’es, or extra arrays. It must not call the Java method hashCode, because that uses a loop. It must not return negative integers, because they can’t be array indexes.
      Here are some some things to try when defining hash. Try using characters at the same indexes from each name. Try linear combinations of the characters: that is, multiplying them by small constants, then adding or subtracting the results. Try the operator ‘%’. Try a mixture of these. Reject any definition of hash that is not perfect: one that returns the same index for two different names.
      Here are some hints about how to write the code for hash. Characters in Java String’s are indexed starting from 0, and ending with the length of the string minus 1. The character at index k in name is obtained by name.charAt(k). For example, the first character from name is returned by name.charAt(0), the second character by name.charAt(1), and the last character byname.charAt(name.length() - 1). If you use a character where an integer is expected, then the character turns into its integer code. For example, name.charAt(0) + 1 adds one to the code for the first character in name, and returns an integer.
      Don’t worry if there are gaps between the indexes: your hash function need not be minimal. Try to keep the returned indexes small: they shouldn’t exceed 2000. For example, there is a perfect hash function for the reserved words in this assignment whose indexes range from 1177 to 1413. It was found after about ten minutes of trial-and-error search.

Answer 1

public class Program
{
static int index[]=new int[2000];
private static final String [] reserved =
{ "and",
"begin",
"define",
"do",
"else",
"end",
"if",
"not",
"or",
"return",
"then",
"while" };
  
private static int hash(String name)
{ int num=0;
int len=name.length();
for(int i=0;i<len;i++)
{
num+=name.charAt(i)+0; //hash logic:add all the ascii values of each char in string...Its perfect for a given set...

}
if(index[num-1]==0)
{
index[num-1]=num;
return index[num-1];
}
System.out.println("hash function failed");
return -1;
}
  
public static void main(String[] args)
{
for (int index = 0; index < reserved.length ; index += 1)
{
System.out.print("h(\"" + reserved[index] + "\") = ");
System.out.print(hash(reserved[index]));
System.out.println();
}
}
}

//output:

h("and") = 307 h("begin") = 517 h("define") = 619 h("do") = 211 h("else") = 425 h("end") = 311 h("if") = 207 h("not") = 337 h("or") = 225 h("return") = 672 h("then") = 431 h("while") = 537