短链的实现

问题的起因是这个: 这是我的刷题日志。当时是 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 的内存分配,有是一篇废话)。 当然除此之外,还有以下的几种解决思路。…