如何创建 URL 缩短器？

我想创建一个 URL 缩短服务，您可以在其中将长 URL 写入输入字段，然后该服务将 URL 缩短为 “ http://www.example.org/abcdef ”。

除了 “ abcdef ”，可以有其他六个字符串，包含az, AZ and 0-9字符串。这使得 56〜570 亿个字符串成为可能。

我的方法：

我有一个包含三列的数据库表：

id，整数，自动递增
long，字符串，用户输入的长 URL
简短的字符串，缩短的 URL（或仅六个字符）

然后，我将长网址插入表中。然后，我将为 “ id ” 选择自动增量值，并为其构建一个哈希值。然后应将此散列插入为 “ short ”。但是我应该建立什么样的哈希值呢？像 MD5 这样的哈希算法创建的字符串太长。我认为我不使用这些算法。自建算法也将起作用。

我的想法：

对于 “ http://www.google.de/ ”，我得到了自动增量 ID 239472 。然后，我执行以下步骤：

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

可以重复进行直到该数字不再可除。您认为这是一个好方法吗？你有更好的主意吗？

_{由于对该主题的持续关注，我为 GitHub 发布了一种有效的解决方案，其中包含JavaScript ， PHP ， Python和Java 的实现。如果您喜欢，请添加您的解决方案:)}

algorithm url

答案

我将继续您的 “将数字转换为字符串” 的方法。但是，您将意识到，如果您的 ID 为质数且大于 52，则建议的算法将失败。

理论背景

您需要一个双射函数f 。这是必要的，以便您可以为f（123）='abc'函数找到反函数 g（'abc'）= 123。这表示：

必须没有x1，x2（x1≠x2）会使f（x1）= f（x2） ，
并且对于每个y，您都必须能够找到x，以便f（x）= y 。

如何将 ID 转换为缩短的 URL

想一想我们要使用的字母。您的情况是[a-zA-Z0-9] 。它包含62 个字母。
以自动生成的唯一数字键（例如，MySQL 表id
对于此示例，我将使用 125 ₁₀ （125 以 10 为底）。
现在您必须将 125 ₁₀转换为 X _{62（以 62 为}基数）。
125 ₁₀ = 2×62 ¹ + 1×62 ⁰ = [2,1]
这需要使用整数除法和取模。伪代码示例：
```
digits = []

while num > 0
  remainder = modulo(num, 62)
  digits.push(remainder)
  num = divide(num, 62)

digits = digits.reverse
```
现在将索引 2 和 1映射到您的字母。这就是您的映射（例如带有数组）的样子：
```
0  → a
1  → b
...
25 → z
...
52 → 0
61 → 9
```
使用 2→c 和 1→b，您将收到 cb ₆₂作为缩短的 URL。
```
http://shor.ty/cb
```

如何将缩短的 URL 解析为初始 ID

反之则更容易。您只需要对字母进行反向查找。

e9a ₆₂将解析为 “字母表中的第 4、61 和 0 个字母”。
e9a ₆₂ = [4,61,0] = 4×62 ² + 61×62 ¹ + 0×62 ⁰ = 19158 ₁₀
WHERE id = 19158数据库记录，并进行重定向。

示例实现（由评论者提供）

您为什么要使用哈希？

您可以使用自动增量值到字母数字值的简单转换。通过使用一些基本转换，您可以轻松地做到这一点。假设您的字符空间（AZ，az，0-9 等）有 62 个字符，将 id 转换为以 40 为底的数字，然后将这些字符用作数字。

public class UrlShortener {
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int    BASE     = ALPHABET.length();

    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();   
    }

    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }   
}