algorithm - 如果我对唯一的字符串使用简单的替换算法，输出是否总是唯一的？

Question

这有点像散列，但更简单。像这样的东西:

function getUniqueId(input) {
    var map = {
            A: 'Q', B: 'W', C: 'E',
            D: 'R', E: 'T', F: 'Y',
            G: 'U', H: 'I', I: 'O',
            J: 'P', K: 'A', L: 'S',
            M: 'D', N: 'F', O: 'G',
            P: 'H', Q: 'J', R: 'K',
            S: 'L', T: 'Z', U: 'X',
            V: 'C', W: 'V', X: 'B',
            Y: 'N', Z: 'M',
            a: 'q', b: 'w', c: 'e',
            d: 'r', e: 't', f: 'y',
            g: 'u', h: 'i', i: 'o',
            j: 'p', k: 'a', l: 's',
            m: 'd', n: 'f', o: 'g',
            p: 'h', q: 'j', r: 'k',
            s: 'l', t: 'z', u: 'x',
            v: 'c', w: 'v', x: 'b',
            y: 'n', z: 'm',
            0: '3', 1: '4', 2: '5',
            3: '6', 4: '7', 5: '8',
            6: '9', 7: '0', 8: '1',
            9: '2',
        },
        output = "";

    for (var i = 0; i < input.length; i++) {
        if (map[input[i]] !== undefined){
            output += map[input[i]];
        }
    }
    return output;
}

我只编码/散列/替换 A-Z、a-z 和 0-9。

如果输入字符串始终是唯一的，那么输出字符串是否也将始终是唯一的？

Answer 1

如果通过对唯一字符串的每个字符应用相同的替换函数来创建散列，则可以确保仅当替换函数为 injective 时输出字符串始终是唯一的.此属性保留唯一性，这是防止唯一性所需要的。

要验证此属性，需要证明:a ≠ b，则 f(a) ≠ f(b)。对于您的 map - 对于数字，它很明显，对于字母，它可能会令人困惑，但可以使用一个简单的 bash 脚本进行检查，该脚本收集所有目标值以查看是否没有出现两次:

echo "A: Q, B: W, C: E, D: R, E: T, F: Y, G: U, H: I, I: O, J: P,  G, P: H, Q: J, R: K, S: L, T: Z, U: X, V: C, W: V, X: B, Y: N, Z: M" | tr ',' '\n' | cut -d':' -f2 | sort | tr -d ' \n'

确实输出

ABCDEFGHIJKLMNOPQRSTUVWXYZ

因为您的函数不会改变字符的位置并且每个字符都受到这种一对一映射的影响，所以唯一的输入将始终产生唯一的输出。

这当然只有当你确定输入的字符串在域A-Z、a-z、0-9中时才成立，否则它不会起作用("@A"=>"Q","A"=>"Q").