java - 在Java中完美哈希三个字母小写字符串的最佳方法？

我当前的解决方案使用多维数组，是否存在更简单的解决方案？
我想在O(1)时间内访问散列对象，并希望充分利用内存空间，因此需要完美的散列。

public final class PerfectHash {

private Object[][][] hashtable = new Object[26][26][26];

public void storeObjectAgainst3letterStringKey(Object o, String s){

    int[] coord = stringToCoord(s);
    hashtable[coord[0]][coord[1]][coord[2]] = o;

}

public Object get(String s){
    int[] coord = stringToCoord(s);
    return hashtable[coord[0]][coord[1]][coord[2]];
}

private int[] stringToCoord(String s){
    if (!s.matches("[a-z][a-z][a-z]")){
        throw new IllegalStateException("invalid input, expecting 3 alphabet letters");
    }
    // 1-26
    // 1-26
    // 1-26
    String lowercase = s.toLowerCase();

    // 97-122 integers for lower case ascii
    int[] coord = new int[3];
    for (int i=0;i<lowercase.length();++i){
        int ascii = (int)lowercase.charAt(i);
        int alpha = ascii - 97; // 0-25
        coord[i] = alpha;
    }
    return coord;
}
}

最佳答案

您甚至不需要先转换String。如果您的三个字符是小写字母，则可以执行此操作。

public static int hashFor(String s) {
    assert s.length() == 3 && isLower(s.charAt(0)) && isLower(s.charAt(1)) && isLower(s.charAt(2));

    return ((s.charAt(0) - 'a') * 26 + s.charAt(1) - 'a') * 26 + s.charAt(2) - 'a';
}

// check a-z not all lowercase letters.
public static boolean isLower(char ch) {
    return ch >= 'a' && ch <= 'z';
}

更优化的版本是

public static int hashFor(String s) {
    return s.charAt(0) * (26 * 26) + s.charAt(1) * 26 + s.charAt(2) - ('a' * (26*26+26+1));
}

只有数字的计算将由编译器优化。

顺便说一句，使用matches()可能比其他所有方法慢100倍。 ;)

如果您已经确定必须使用小写字母，则无需转换为小写字母。

关于java - 在Java中完美哈希三个字母小写字符串的最佳方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24428029/