Best way to hash sets of three integers

Question

I'm trying to write a program that quickly finds all words that match a string with wildcards and known letters. For example, L*G would return LOG, LAG, LEG. I'm looking for something that would give me very fast lookup, but I don't care about time it takes to create the tree in the first place.

My idea is a Hashmap of "Triples" mapping to an ArrayList of Strings: basically, a list of all Strings that match the criteria for a certain index, character at that index, and length.

But my issue now is generating a good hash function for these "Triples" such that every triplet is unique.

Here's my code for what I have right now.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class CWSolutionT {
HashMap<Triple, ArrayList<String>> tripleMap = new HashMap<Triple, ArrayList<String>>();

public CWSolutionT(List<String> allWords) {
    for (String word : allWords) {
        for (int letter = 0; letter < word.length(); letter++) {
            ArrayList<String> tempList = new ArrayList<String>();
            Triple key = new Triple(letter, word.charAt(letter),
                    word.length());
            if (tripleMap.get(key) == null) {
                tempList.add(word);
                tripleMap.put(key, tempList);
            } else {
                tempList = tripleMap.get(key);
                tempList.add(word);
                tripleMap.put(key, tempList);
            }
        }
    }
}

public List<String> solutions(String pattern, int maxRequired) {
    List<String> sol = new ArrayList<String>();
    List<List<String>> solList = new ArrayList<List<String>>();
    int length = pattern.length();
    for (int i = 0; i < length; i++) {
        if (pattern.charAt(i) != '*') {
            Triple key = new Triple(i, pattern.charAt(i), pattern.length());
            solList.add(tripleMap.get(key));
        }
    }
    if (solList.size() == 0) {
        // implement later
    }

    if (solList.size() == 1)
        return solList.get(0);

    for (List<String> list : solList) {
        sol.retainAll(list);
    }
    return sol;
}

private class Triple {
    public final int index;
    public final char letter;
    public final int length;

    public Triple(int ind, char let, int len) {
        index = ind;
        letter = let;
        length = len;
    }

    public boolean equals(Object o) {
        if (o == null)
            return false;
        if (o == this)
            return true;
        if (!(o instanceof Triple)) {
            return false;
        }
        Triple comp = (Triple) o;
        if (this.hashCode() == comp.hashCode())
            return true;
        return false;
    }

    public String toString() {
        return "(" + index + ", " + letter + ", " + length + ")";
    }

    public int hashCode() {
        return (int) (.5 * (index + letter + length)
                * (index + letter + length + 1) + letter + length);
    }
}
}

Please build a [SSCCE](http://sscce.org) to demonstrate the issue — Sage, Dec 11 '13 at 21:12
If you're writing a word game, you should look up Directed Acyclic Word Graph. — Jim Mischel, Dec 12 '13 at 15:04

score 4 · Answer 1 · answered Dec 11 '13 at 21:03

4

You have to overrride hashCode() as well in your Tuple class

answered Dec 11 '13 at 21:03

Kai Huppmann

10,705
6
47
78

since your tuple is dealing with to objects use their hashCodes and a cantor pairing to calculate a unique hashCode from those: http://en.wikipedia.org/wiki/Cantor%5Fpairing%5Ffunction#Cantor_pairing_function – Kai Huppmann Dec 11 '13 at 21:16
@Kai Huppmann: Cantor pairing stops working whenever an overflow occurs. Actually, for a limited domain there's no reason to try. – maaartinus Dec 12 '13 at 00:13
@maartinus Don't know what you mean. Sure with big original hash codes you'll get out of int-range, but the contract for hashCode() and equals() will still be fulfilled. What does 'for a limited domain there's no reason to try' mean? What's your alternative? – Kai Huppmann Dec 12 '13 at 09:56

score 0 · Answer 2 · edited May 23 '17 at 11:49

HashMap requires an implementation of equals and hashCode and you haven't overridden either of them. Right now your map is basically only checking object identify (someOldObject == someNewObject).

It looks like you've attempted to implement an equals method but the signature is wrong, Object#equals takes an Object as a parameter and yours takes a Tuple so it is instead overloaded. Answers for this question have some tips for implementing equals and hashCode: What issues should be considered when overriding equals and hashCode in Java?.

score 0 · Answer 3 · answered Dec 12 '13 at 00:34

In general, it's impossible to squeze two ints into a single one. Cantor pairing function works for an infinite domain, but transferring it to ints leads nowhere.

Your input is a triple (int, char, int), which theoretically accounts for 2**32 * 2**16 * 2**32 = 2**80 possibilities, which obviously can't be injectively mapped onto a set containing 2**32 elements only.

With the help of some knowledge about the input values you can do better, but possibly not good enough. For example, you know that both index and length are non-negative, which makes your domain four times smaller... but that's nothing.

If you knew that both index and length are less than 256, you could do the mapping via

public int hashCode() {
    return index + 256 * length + 256 * 256 * letter;
}

This expression can be written more efficiently as

index + (length << 8) + (letter << 16)

but you can leave it to the JIT compiler.

It's well possible that you can't reduce the domain sufficiently and then I'd suggest to let it be. Just compare the fields... you could try to fit it in a long, but isn't it all the root of all evil?

Note that your

public int hashCode() {
    return (int) (.5 * (index + letter + length)
            * (index + letter + length + 1) + letter + length);
}

is too bad.... you're using a pairing of three things! The tuples (0, 'A', 1) and (0, 'B', 0) have the same hashCode and thus your equals return true. You're actually Cantor-pairing index and letter + length while you'd have to use two pairings.

Best way to hash sets of three integers

3 Answers3