个人相关：三年前我在公司做过短地址服务，现在上线运行。而这道题也是我目前招聘面试题中的必考题。本题可考点较多，可以比较全面地考查考生的技能。
最糟糕的答案 实现一个算法来将长地址转换为短地址。实现多空一一对应。然后执行其逆运算，将短地址转换回长地址。这个答案看起来很完美，然后候选人也会说时间短，如果你给我时间，我会找到这个算法来解决问题。但是稍微有点计算机或信息论常识的人会发现，这个算法就像永动机一样，永远找不到。即使我们将短地址定义为 100 位。那么它的变化是 62 的 100 次方。 62 = 10 个数字 + 26 个大写字母 + 26 个小写字母。不管这个数字有多大，它都不能大于世界上可能的长地址。因此，不可能做到一一对应。另一个要反驳的说法，如果有这样的算法和逆运算，那么现在的压缩软件基本上可以停产，世界上所有的信息都可以压缩到100个字符。这可能吗？
另一个不好的答案 和上面一样，找到一个将长地址转换为短地址的算法，但是没有逆运算。我们需要将短到长关系存储在数据库中。通过short检查长度时，我们需要检查DB。怎么说呢，本质不变。如果有这样的算法，难免会发生冲突，即多个长地址转换为同一个短地址。因为我们无法预测这个系统会输入什么样的长地址，所以不可能实现这样一个绝对无冲突的哈希函数。
不好回答，那我们用hash算法，我承认会碰撞，碰撞后我在后面加1、2、3。 ok，在这种情况下，用这个hash算法计算的时候，我们可能需要做btree-style大于或者小于或者like来找出我们现在应该在后面加1、2、3。这也可能是由于输入的地址过长。设定不确定性。生成短地址的时间不确定。同样糟糕的答案是随机生成一个短地址，看看是否被使用过，然后再次随机化，以此类推，直到随机找到一个未使用的短地址。
正确的原则以上是几个典型的错误答案。直接说正确的原理吧。正确的原则是使用编号策略给每一个过来的长地址发送一个编号，小系统可以直接使用mysql的自增索引。如果是大规模应用，可以考虑各种分布式键值系统作为号码发行者。只是不断增加。第一个使用这个服务的人得到一个短地址/0，第二个是u6.gg/1，第11个是u6.gg/a等等，相当于实现了一个十六进制的自增字段就足够了。
几个子问题
1. 十六进制如何使用数据库或KV存储？实际上，我们在存储中不需要使用 62 基，只需使用 10 基即可。比如第10000个长地址可以统计的短链接，我们给它的短地址对应的数字是9999。我们通过存储自增得到9999后，进行十进制到十六进制的转换，再转换为62。这个10-62的十六进制转换，完全可以自己实现。
2. 如何保证每次转出的短地址都是相同的长地址。也就是说，如果你用百度首页地址转，我给你一个u6.gg/abc你过一会再转，我也给你一个u6.gg/ xyz。这看起来很糟糕，但糟糕的地方在哪里？不好的是不是一一对应，而是一长一短。这不符合我们完美主义的基因，那有什么问题呢？有人说这是浪费空间，这是真的。对于同一个长地址，会产生多条短地址记录，这显然是在浪费空间。那么我们如何避免浪费空间，有人很快回答了我，只需建立一个多短KV存储。嗯，这听起来很合理，但是。 . 这种KV存储本身就是对空间的巨大浪费。所以我们是以空间换空间，看似以大空间换小空间。是不是真的值得吗？考虑这个问题。当然，也不是没有办法解决。我们不能真正做到一一对应可以统计的短链接，能不能打折？这个问题的答案太多了，各有各的方法，这里就不一一赘述了。 （因为太多人在纠结这个问题，请在底部查看我的更新）
3. 如何保证发送端的大并发和高可用上面的设计似乎有一个点，那就是发送端。如果是分布式的，那么这么多节点需要保持同步加1，同时写入多个点。嗯，根据CAP理论，是不可能真正做到的。其实这个问题的解决方法很简单。我们可以退一步考虑一下，是否可以实现两个数字发送器，一个用于订单号，一个用于双号，从而将单点变为多点？以此类推，我们可以实现1000个逻辑号码发送器，它们分别发送以0到999结尾的号码。每发出一个号码，每个号码发送器加1000而不是加1。这些发送器独立工作，互不干扰。而且在实现上，也可以先合乎逻辑，压力真大，再拆分成独立的物理机单元。 1000个节点，估计人类应该够用了。如果你真的想要更多，理论上是可以的。
4. 具体如何选择存储就不讨论了，各有千秋，主要考察对存储的理解。了解缓存原理，了解市场上数据库和缓存系统的可用性、并发性和一致性。
5. 跳跃是用301还是302也是一个有趣的话题。首先，当然要考察考生对 301 和 302 的理解。对浏览器缓存机制的理解。然后是对他的商业经验的审查。 301是永久重定向，302是临时重定向。短地址一旦生成就不会改变，所以使用 301 符合 http 语义。同时，服务器的压力也会在一定程度上减轻。但是如果使用301，我们就无法统计短地址的点击次数。而这个点击量对于大数据分析来说是一个非常有趣的数据源。可以分析的东西太多了。所以选择302会增加服务器压力，但我认为是更好的选择。
就是这样。
------端午节后更新-------- 来回答大家最纠结的几个问题，就是如何实现同一个长地址的多次转换，以及会出现相同的短地址。
我上面说过，这个方案最简单的方案就是创建一个long-to-short hashtable，相当于用空间换空间，同时换来一个设计优雅（真正的一对< @一）.
实际情况是有很多高性价比的折扣方案可供选择，这个方案的设计因人而异。然后我会告诉你我的计划。
我的解决方案是：使用键值存储来保存“最近”生成的长短对应关系。请注意，它是“最近的”，即我不保存全部的多空关系，而只保存最近的。比如用一小时过期机制来实现LRU淘汰。
这种情况下，long-to-short的过程变成如下： 1 查看这个“recent”表，看长地址是否有对应的短URL1.1 如果有，直接返回，并且把 key -value 对的过期时间延长到一小时。1.2 如果没有，则通过发送方生成一个短地址，在这个“最近”表中过期时间为1小时.
所以当一个地址被频繁使用时，它会一直在key-value表中，并且总是可以返回原来生成的短地址，不会出现重复的问题。如果不经常使用，长短键会过期，LRU机制会自动淘汰。
当然，这并不能保证 100% 的同一个长地址可以传输到同一个短地址。例如，如果你取一个稀有的 URL，每隔 1 小时传输一次，你会得到不同的短地址。但这真的重要吗？
