Java prog (Hashing and Binary Search Trees). Create a class Word, representing a

Question

Java prog (Hashing and Binary Search Trees).

Create a class Word, representing a word. Two words should be considered equal if they consist of the same sequence of letters and we consider upper case and lower case as equal. For example hello, Hello and HELLO are considered to be equal. The methods equals and hashCode define the meaning of "equality". Thus, the class Word should look like the following.

public class Word implements Comparable {

private String word; public Word(String str) { ... }

public String toString() { return word; }

/* Override Object methods */ public int hashCode() { ... compute a hash value for word }

public boolean equals(Object other) { ... true if two words are equal }

/* Implement Comparable */

public int compareTo(Word w) { ... compares two words lexicographically }

}

Note: If you want, you can add more methods. The methods mentioned above are the minimum requirement.

Explanation / Answer

public class
{
String[] dictionary = new String[DICT_SIZE];
dictionary[h("a".hashCode(), DICT_SIZE)].add("Hello");
dictionary[h("b".hashCode(), DICT_SIZE)].add("world");
System.out.println(dictionary[h("a".hashCode(), DICT_SIZE)].get(0));
for (int i = 0; i <= DICT_SIZE; i++)
{
    dictionary[h(i, DICT_SIZE)] = " ";
}

List<Pair<String,String>>[] dictionary = List<Pair<String,String>>[DICT_SIZE];

public void put(String key, String value) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex == null) {
        listAtIndex = new LinkedList<Pair<Integer,String>>();
        dictionary[arrayIndex] = listAtIndex;
    }

    for (Pair<String,String> previouslyAdded : listAtIndex) {
        if (previouslyAdded.getValue().equals(value)) {
            return;
        }
    }

    listAtIndex.add(new Pair<String,String>(key, value));
}

public String get(String key) {
    int hashCode = key.hashCode();
    int arrayIndex = h(hashCode, DICT_SIZE);

    List<Pair<String,String>> listAtIndex = dictionary[arrayIndex];
    if (listAtIndex != null) {
        for (Pair<String,String> previouslyAdded : listAtIndex) {
            if (previouslyAdded.getKey().equals(key)) {
                return previouslyAdded.getValue(); // entry found!
            }
        }
    }

    return null;
}

we actually need two comparison operations: the hashCode method to find the list in the array if hashCode() and an equals90 method which we need when going through the list.Naturally, this approach is not limited to Strings, it works for all kinds of objects, since the methods hashCode() and equals are members of the top-level class java.lang.Object and all other classes inherit from that one. it doesn't really matter if two distinct objects return the same value in their hashCode() method.

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.