4.10 Lab: Different Hash Functions

In this lab, you will implement three hash functions that have been discussed in this text. Below are the pseudocodes of these methods. Please note that for the mid-square hash, LowBitsToRemove = (32 - R)/2. Check the Hashtable351.java to see what variables are provided: hash size (N), LowBitsToRemove (32 -R)/2, an initial value and hash multiplier (both for the multiplicative hash function).

HashRemainder(int key) { return key % N } HashMidSquare(int key) { squaredKey = key * key extractedBits = squaredKey >> LowBitsToRemove extractedBits = extractedBits & (0xFFFFFFFF >> (32-R)) return extractedBits % N } HashMutliplicative(string key) { stringHash = InitialValue for (each character strChar in key) { stringHash = (stringHash * HashMultiplier) + strChar } return stringHash % N } 

Example Input for numeric hash functions

309 -1 

Example output

Enter a key to generate a hashcode (-1 as key to end) Using Remainder the hashcode is:109 Using Midsquare hash function the hashcode is: 23 Enter a key to generate a hashcode (-1 as key to end) 

Example input for string hash function

Phoenix -1 

Example output

Enter a key to generate a hashcode (-1 as key to end) Using Multiplicative hash the hashcode is: 150 Using JAVA's hashcode: 1068910959 Enter a key to generate a hashcode (-1 as key to end)

Hashtable351.java

public class Hashtable351 { private static final int HASH_SIZE = 200; private Node[] hashTable = new Node[200];

Charprivate int R = 8; private int INITIAL_VALUE = 19; private int HASH_MULTIPLIER = 1;

public int HashRemainder(int key) { // Implement this method }

public int HashMidSquare(int key) { // Implement this method }

public int HashMultiplicative(String key) { // Implement this method }

} }

Hashtabletest.java

import java.util.Scanner;

public class HashtableTest { public static void main(String[] args){ Hashtable351 hTable = new Hashtable351(); //System.out.println("Hashing Functions:"); Scanner input = new Scanner(System.in); while(true){ System.out.println("Enter a key to generate a hashcode (-1 as key to end)"); String key = input.next(); // String value = input.next(); if(isNum(key)){ int keyInt = Integer.parseInt(key); if (keyInt == - 1) break; System.out.println("Using Remainder the hashcode is:" + hTable.HashRemainder(keyInt)); System.out.println("Using Midsquare hash function the hashcode is: " + hTable.HashMidSquare(keyInt)); } else{ System.out.println("Using Multiplicative hash the hashcode is: " + hTable.HashMultiplicative(key)); System.out.println("Using JAVA's hashcode: " + key.hashCode()); } } } public static boolean isNum(String strNum) { boolean ret = true; try {

Double.parseDouble(strNum);

}catch (NumberFormatException e) { ret = false; } return ret; }

} Node.java

public class Node{ private int data; private Node next; private Node prev; public Node(int data){ this.setData(data); setNext(setPrev(null)); }

public Node getNext() { return next; }

public void setNext(Node next) { this.next = next; }

public Node getPrev() { return prev; }

public Node setPrev(Node prev) { this.prev = prev; return prev; }

public int getData() { return data; }

public void setData(int data) { this.data = data; } }

Keep these expected inputs and outputs in mind, as other solutions on Chegg for this problem don't take them into account and produce errors for one or more of them:

Expected Input 1:

CS351 -1

Expected Output 1:

Enter a key to generate a hashcode (-1 as key to end)

Using Multiplicative hash the hashcode is: 122 Using JAVA's hashcode: 64399263 Enter a key to generate a hashcode (-1 as key to end)

Expected Input 2:

200 -1

Expected Output 2:

Enter a key to generate a hashcode (-1 as key to end) Using Remainder the hashcode is:0 Using Midsquare hash function the hashcode is: 9 Enter a key to generate a hashcode (-1 as key to end)

Expected Input 3:

234 -1

Expected Output 3:

Using Remainder the hashcode is:34 Using Midsquare hash function the hashcode is: 13 Enter a key to generate a hashcode (-1 as key to end)