Hashids原理及简略实现

Hashids的原理及简略实现

Hashids是一个将数字转化为长度较短、唯一且不连续的值的库。特点是：

对非负整数都可以生成唯一短id；
可以设置不同的盐，具有保密性；
递增的输入产生的输出无法预测；
代码较短，且不依赖于第三方库。

那么Hashids的原理是什么？Hashids的机制类似于十进制数字转换为16进制的映射，但是做了一点改动：

没有使用16进制，而是62进制（26个字母大小写+10个数字）；
这个「62进制」的映射通过加盐而做了扰动。

首先我们可以实现第一步：

public class Hashids {

    private static final String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";

    public static String hash(long input, String alphabet) {
        StringBuilder hash = new StringBuilder();
        int alphabetLen = alphabet.length();

        do {
            int index = (int) (input % alphabetLen);
            if (index >= 0 && index < alphabet.length()) {
                hash.insert(0, alphabet.charAt(index));
            }
            input /= alphabetLen;
        } while (input > 0);

        return hash.toString();
    }
}

仅有映射显然不足以提供安全性，因此还需要加以扰动。对映射表洗牌可以改变输出值，那么我们如何能够可重放的洗牌，使得每次产生相同的结果呢？Hashids使用了Fisher–Yates洗牌算法的变种。

// Fisher–Yates洗牌算法
private static String shuffle(String alphabet) {
    char[] shuffle = alphabet.toCharArray();
    for (int i = shuffle.length - 1; i >= 1; i--) {
        int j = new Random().nextInt(i+1);
        char tmp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = tmp;
    }
    return new String(shuffle);
}

Hashids使用Fisher–Yates洗牌算法基本思路：每次选择一个数字交换到剩下的数字的最后一位。但每次选择数字是通过盐来选择的，将原算法改进为：

private static String consistentShuffle(String alphabet, String salt) {
    char[] shuffle = alphabet.toCharArray();
    for (int i = shuffle.length - 1, v = 0, p = 0; i >= 1; i--, v++) {
        v = v % salt.length();
        int integer = salt.charAt(v);
        p += integer;
        int j = (integer + v + p) % i;

        char tmp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = tmp;
    }
    return new String(shuffle);
}

输出结果

1 2	salt=sheep -> alphabet=K1RNlAYFWTeX8DEL720Iia9bcfjnBPm4sSCopgUuqz6rQH5xhtOv3ZMGJwdkyV salt=sleep -> alphabet=zROjCepudWwIQYxfKc5vTLmZ9qXEBy4lkns706r1PaMH8ibJtF2D3gUSNAhoGV

Hashids也可以将多个数字生成为1个id，方法是从映射表中选取一些字符作为分隔符。这些分隔符不用于编码，只用于分隔其它编码后的字符。

private static String seps = "cfhistuCFHISTU";

private static String encode(long[] numbers, String alphabet, String salt) {
    StringBuilder result = new StringBuilder();
    int sepsIndex;
    for (int i = 0; i < numbers.length; i++) {
        long num = numbers[i];

        alphabet = consistentShuffle(alphabet, salt);
        String last = hash(num, alphabet);

        result.append(last);

        if (i < numbers.length - 1) {
            if (last.length() > 0) {
                num %= (last.charAt(0) + i);
                sepsIndex = (int) (num % seps.length());
            } else {
                sepsIndex = 0;
            }
            result.append(seps.charAt(sepsIndex));
        }
    }
    return result.toString();
}

输出结果：

1           -> R
1,2         -> RfP
1,2,3       -> RfPht
1,2,3,4     -> RfPhti4
1,2,3,4,5   -> RfPhti4s4
1,2,3,4,5,6 -> RfPhti4s4tE

参考资料：