问题的起因是这个:
这是我的刷题日志。当时是 2017.3.4 号，做了这道题之后，一直想写下是否有更好的解题思路。但是一直没(lan)有(lan)时(lan)间(lan)。
正巧今天在复习数据结构的时候看到了 LZW 压缩器。这就可以拉出来好好扯一下了。
其实现在流行的，或者网上的标准操作套路都是使用 hash 的方式，将其对应到几个短的链接上，但是因为毕竟这个属于 hash 映射，在长度变短的情况下，始终会有冲突的危险。所以也就带来了 rehash(cpu 开销和内存开销) 和 hash 表最坏情况(退化为链表结构，查找效率退化成 O(n))的风险。
比如常见的，使用 md5 摘要一把，然后将结果存到一个 hash 表中，这个 hash 表是个抽象的概念，他可以使具象化的数据库，Key-Value Store，或者仅仅的文件存储，或者内存数据。
但是，以上真的是个很烂的解法。具体的原因如下：
- 世界上并不存在不会碰撞的 hash 算法。只要使用 hash 必然就会带来冲突风险。这个风险就会造成之前提到的 rehash 和 退化 问题。为了解决这个引入的问题，往往就会加大系统的复杂性。所以可以从源头开始解决。
- 这样存贮之后，并不利于系统 (加入后台使用 DB) 查询效率的优化。查询的关键字为短链的值 — 字符串。这就带来了字符串索引的问题。这个就是在数据库优化中讨论的问题了。
不过，也是有优点的。因为是自己选定的 hash 函数，所以长度可控。比如我就要 32 位 hash 结果，那么最后得到的值的期待长度固定，方便进行自造轮子的存储系统或者说特别利于 redis 的发挥(redis 对等长数据的存储非常赞，几乎不会造成内存碎片的问题，如果这边展开讲 redis 的内存分配，有是一篇废话)。
当然除此之外，还有以下的几种解决思路。
- 压缩
- 发号
压缩这个很好理解，比如常用的 LZW 压缩算法和 zip 等使用的商业化压缩算法结合起来。通常情况下 LZW 的压缩算法的压缩比在 1.8 左右（数据较大的情况）而商业化的 Zip 工具压缩比则要更高。
但是，在这个业务场景中，他并不适用。
- LZW 的压缩结果包含两个部分，一个是压缩串，一个是数对字典。压缩串很短，但是数对字典的存储空间占用则会远远大于压缩串(如果你需要针对每一个 URL 进行 LZW 压缩，则这个必不可少。不过可以针对相同的 host 进行字典的共用，不过这不是自己找麻烦么)。
- 针对 URL 的缩短，数据通常在 100B ~ 1000B 之间，在这个范围内，我自己写的 LZW 压缩比是大于 1 的。也就是说，最后的结果，会超出原有的数值(不过，发给用户的压缩串就短了很多，不过这就带来了数对字典存服务器，之后还会有状态保存的问题)。
之后就是发号的思路了。其实这个也挺有意思的。他和秒杀的库存数是类似的。要求并发条件下不会出现发重号或者突然挂掉的问题。并发条件下不发重号。这个就是和分布式数据库的自增 id 生成业务类似，可以参考这个的实现思路（这个还挺多的，有用 redis 的，有自建服务的）。
然后，发号之后，可以使用 array 或者 hashmap 进行存储。不过，有一个小的优化的地方，自增 id 假设是从 0 开始的整数，那似乎交给用户的结果为纯数字，似乎是有点 low。不过不要紧，可以自己写一个 62 (26+26+10) 的进制转换器，分别映射到 [0-9|a-z|A-Z] 这么 62 个数，这样，看起来就很高端大气了。
总的来说，Leetcode 的这道面试题其实挺有意思的。估计面试官也是想考察这个人的思路的广阔性和思考的深度。而且针对其不同的业务场景和企业的发展期，做出不同的技术选型。同时也能考察这个人的沟通能力。不得不说真的好玩。
没有永远的银弹，只有恰到好处的击杀。这就是编程的魅力啊。
学习了