Java Minimal Perfect Hash Table Implementation Using Cichelli’s Method

import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.Stack;

 

import javax.swing.text.html.HTMLDocument.Iterator;

 

public class Driver {

public static ArrayList<String> words = new ArrayList<>();

public static HashMap<String, Integer> wordsValuesMap = new HashMap<>();

public static HashMap<String, Integer> testValuesMap = new HashMap<>();

public static HashMap<Character, Integer> letterValuesMap = new HashMap<>();

public static HashMap<Character, Integer> gValuesMap = new HashMap<>();

 

// g is the value associated with a given letter. The value ranges between 0 and

// some maximum value. The max value is one of the inputs to the Cichelli

// Algorithm.

public static int g = 0;

public static int max = 0;

 

public static void main(String[] args) {

 

CountLetters();

 

System.out.println(“Letters Values Map ” + letterValuesMap.toString());

System.out.println(“————————————————————–“);

System.out.println(“Words Values Map ” + wordsValuesMap.toString());

System.out.println(“————————————————————–“);

System.out.println(“G Values Map ” + gValuesMap.toString());

 

}

 

public static int h(String word) {

char first = word.charAt(0);

char last = word.charAt(word.charAt(word.length() – 1));

return (word.length() + (g * first) + (g * last)) % words.size();

}

 

public static void CountLetters() {

 

String[] str = { “alabama”, “maine”, “montana”, “nevada”, “idaho” };

for (int i = 0; i < str.length; i++) {

char first = str[i].charAt(0);

char last = str[i].charAt(str[i].length() – 1);

 

// first = Character.toLowerCase(first);

if (!letterValuesMap.containsKey(first)) {

letterValuesMap.put(first, 1);

} else {

letterValuesMap.put(first, letterValuesMap.get(first) + 1);

}

 

if (!letterValuesMap.containsKey(last)) {

letterValuesMap.put(last, 1);

} else {

letterValuesMap.put(last, letterValuesMap.get(last) + 1);

}

 

} // end of for loop

// sort the list … highest values first

letterValuesMap = sortByValues(letterValuesMap);

 

// calculate the first+last word value

for (int i = 0; i < str.length; i++) {

char first = str[i].charAt(0);

char last = str[i].charAt(str[i].length() – 1);

int sum = letterValuesMap.get(first) + letterValuesMap.get(last);

wordsValuesMap.put(str[i], sum);

}

wordsValuesMap = sortByValues(wordsValuesMap);

 

// pick max value (max occurrence of a letter/2)

max = letterValuesMap.get(letterValuesMap.keySet().iterator().next()) / 2;

 

}

 

public static boolean cichelli(Stack wordStack) {

initGValues();

while (!wordStack.isEmpty()) {

String word = (String) wordStack.pop();

char first = word.charAt(0);

char last = word.charAt(word.length() – 1);

int wordLength = word.length();

 

if (!letterValuesMap.containsKey(first) && !letterValuesMap.containsKey(first)) {

 

}

 

}

 

return false;

 

}

 

public static void initGValues() {

// init g map

for (char c : letterValuesMap.keySet()) {

gValuesMap.put(c, 0);

}

 

for (String word : wordsValuesMap.keySet()) {

testValuesMap.put(word, h(word));

 

}

 

}

 

private static HashMap sortByValues(HashMap map) {

List<?> list = new LinkedList(map.entrySet());

// Defined Custom Comparator here

Collections.sort(list, new Comparator() {

public int compare(Object o1, Object o2) {

return ((Comparable) ((Map.Entry) (o2)).getValue()).compareTo(((Map.Entry) (o1)).getValue());

}

});

 

// Here I am copying the sorted list in HashMap

// using LinkedHashMap to preserve the insertion order

HashMap sortedHashMap = new LinkedHashMap();

for (java.util.Iterator it = list.iterator(); ((java.util.Iterator) it).hasNext();) {

Map.Entry entry = (Map.Entry) it.next();

sortedHashMap.put(entry.getKey(), entry.getValue());

}

return sortedHashMap;

}

 

public static void readFile() {

String file = “data.txt”;

BufferedReader br = null;

String line = “”;

 

try {

 

br = new BufferedReader(new FileReader(file));

 

while ((line = br.readLine()) != null) {

String[] studentData = line.split(“,”);

 

// addStudent(Long.parseLong(studentData[0].trim()), studentData[1].trim(),

// studentData[2].trim());

 

} // end of while

 

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

} finally {

if (br != null) {

try {

br.close();

} catch (IOException e) {

e.printStackTrace();

}

} // end of if

}

 

}// end of read file

 

}

 

Do you need a similar assignment done for you from scratch? Order now!
Use Discount Code "Newclient" for a 15% Discount!