535. [字符串]TinyURL的加密与解密

SuPhXLiN 2021-08-14 原文

535. TinyURL 的加密与解密

方法一：使用内置函数hashcode

我们可以使用Java中内置的hashCode() 来为每个url产生加密结果。同样的，映射结果保存在HashMap以供解码。

一个String对象的hash code的计算方法是这样的：

\[hashcode_{String} = s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + … + s[n-1]
\]

其中，\(s[0]\)是字符串的第\(i\)个字符，\(n\)是字符串的长度。

// 执行用时： 10 ms , 在所有 Java 提交中击败了 20.16% 的用户 
// 内存消耗： 39.2 MB , 在所有 Java 提交中击败了 14.51% 的用户
public class Codec {
    Map<Integer, String> map = new HashMap<>();
    
    public String encode(String longUrl){
        map.put(longUrl.hashCode(), longUrl);
        return "http://tinyurl.com/" + longUrl.hashCode();
    }
    
    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com", "")));
    }
}

使用表现分析：

可加密 URL 的数目由 \(int\) 决定，因为使用整数运算。
加密后 URL 的平均长度与 \(longURL\) 的长度没有直接关联。
\(hashCode()\) 对于不同的字符串不一定产生独一无二的加密后 URL。像这样对于不同输入产生相同输出的过程叫做冲突。因此，如果加密字符串的数目增加，冲突的概率也会增加，最终导致算法失效。
下图展示了不同对象映射到相同的 hashcode，以及对象越多冲突概率越大。

方法二：随机固定长度加密

使用数字和字母表集合来为 URL 生成加密结果。这种方法中，加密后的长度固定是 6 位。如果产生出来的加密结果与之前产生的结果一样，就换一个新的加密结果。

// 执行用时： 7 ms , 在所有 Java 提交中击败了 45.28% 的用户 
// 内存消耗： 39.1 MB , 在所有 Java 提交中击败了 20.98% 的用户

public class Codec {
    String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    HashMap<String, String> map = new HashMap<>();
    Random rand = new Random();
    String key = getRand();

    public String getRand() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.append(alphabet.charAt(rand.nextInt(62)));
        }
        return sb.toString();
    }

    public String encode(String longUrl) {
        while (map.containsKey(key)) {
            key = getRand();
        }
        map.put(key, longUrl);
        return "http://tinyurl.com/" + key;
    }

    public String decode(String shortUrl) {
        return map.get(shortUrl.replace("http://tinyurl.com/", ""));
    }
}

使用表现分析：