java - 哈希三个整数集的最佳方法

Question

我正在尝试编写一个程序，可以快速查找与带有通配符和已知字母的字符串匹配的所有单词。例如，L*G 将返回 LOG、LAG、LEG。我正在寻找可以非常快速查找的东西，但我不关心创建树所需的时间。

我的想法是“三元组”的 HashMap 映射到字符串的ArrayList:基本上，是与特定索引、该索引处的字符和长度的条件相匹配的所有字符串的列表。

但我现在的问题是为这些“三元组”生成一个好的哈希函数，以便每个三元组都是唯一的。

这是我现在拥有的代码。

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);
    }
}
}

Answer 1

您必须覆盖 hashCode()以及您的 Tuple 类