我想创建一个URL缩短服务，你可以写一个长URL到输入字段和服务缩短URL为“http://www.example.org/abcdef”。
可以用包含a-z, a-z和0-9的6个字符的字符串代替"abcdef"。这样就有560 ~ 570亿个可能的字符串。
我的方法:
我有一个有三列的数据库表:
Id，整数，自动递增
long, string，用户输入的长URL
短，字符串，缩短的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的实现。如果你喜欢，添加你的解决方案:)
这是我最初的想法，可以做更多的思考，或者做一些模拟，看看是否有效或需要改进:
我的答案是记住数据库中的长URL，并使用ID 0到999999999999999999(或所需的任意大的数字)。
但是ID 0到999999999999999999可能是个问题，因为
如果我们使用十六进制，甚至base62或base64，它可以更短。(base64就像YouTube使用A-Z A-Z 0-9 _和-)
如果它从0均匀地增加到999999999999999999，那么黑客就可以按照这个顺序访问它们，并知道人们相互发送的url，所以这可能是一个隐私问题
我们可以这样做:
have one server allocate 0 to 999 to one server, Server A, so now Server A has 1000 of such IDs. So if there are 20 or 200 servers constantly wanting new IDs, it doesn't have to keep asking for each new ID, but rather asking once for 1000 IDs
for the ID 1, for example, reverse the bits. So 000...00000001 becomes 10000...000, so that when converted to base64, it will be non-uniformly increasing IDs each time.
use XOR to flip the bits for the final IDs. For example, XOR with 0xD5AA96...2373 (like a secret key), and the some bits will be flipped. (whenever the secret key has the 1 bit on, it will flip the bit of the ID). This will make the IDs even harder to guess and appear more random
按照这种方案，分配id的单个服务器可以组成id，请求分配id的20或200个服务器也可以组成id。分配服务器必须使用锁/信号量来防止两个请求服务器获得相同的批处理(或者如果它一次接受一个连接，这已经解决了问题)。因此，我们不希望等待分配的队列太长。所以这就是为什么一次分配1000或10000个可以解决问题。
我将继续您的“将数字转换为字符串”方法。但是，如果您的ID是质数且大于52，您将意识到您提出的算法将失败。
理论背景
你需要一个双射函数f。这是必要的，这样你就可以为你的f(123) = 'abc'函数找到一个逆函数g('abc') = 123。这意味着:
一定不存在x1 x2 (x1≠x2)使得f(x1) = f(x2)
对于每一个y，你必须能找到一个x，使f(x) = y。
如何将ID转换为缩短的URL
Think of an alphabet we want to use. In your case, that's [a-zA-Z0-9]. It contains 62 letters.
Take an auto-generated, unique numerical key (the auto-incremented id of a MySQL table for example).
For this example, I will use 12510 (125 with a base of 10).
Now you have to convert 12510 to X62 (base 62).
12510 = 2×621 + 1×620 = [2,1]
This requires the use of integer division and modulo. A pseudo-code example:
digits = []
while num > 0
remainder = modulo(num, 62)
digits.push(remainder)
num = divide(num, 62)
digits = digits.reverse
Now map the indices 2 and 1 to your alphabet. This is how your mapping (with an array for example) could look like:
0 → a
1 → b
...
25 → z
...
52 → 0
61 → 9
With 2 → c and 1 → b, you will receive cb62 as the shortened URL.
http://shor.ty/cb
如何将缩短的URL解析为初始ID
反过来就更容易了。你只需要在字母表中反向查找。
E9a62将被解析为“字母表中的第4、61和0个字母”。
E9a62 = [4,61,0] = 4×622 + 61×621 + 0×620 = 1915810
现在找到WHERE id = 19158的数据库记录并执行重定向。
示例实现(由评论者提供)
c++
Python
Ruby
Haskell
c#
CoffeeScript
Perl
这是我所使用的:
# Generate a [0-9a-zA-Z] string
ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91))
def encode_id(id_number, alphabet=ALPHABET):
"""Convert an integer to a string."""
if id_number == 0:
return alphabet[0]
alphabet_len = len(alphabet) # Cache
result = ''
while id_number > 0:
id_number, mod = divmod(id_number, alphabet_len)
result = alphabet[mod] + result
return result
def decode_id(id_string, alphabet=ALPHABET):
"""Convert a string to an integer."""
alphabet_len = len(alphabet) # Cache
return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))])
它非常快，可以取很长的整数。
