知识卡片

问题卡 · 4447

截断哈希必须处理碰撞

理解等级:高级

截取长哈希生成短码会丢失信息,不同长 URL 可能得到同一码。必须检查冲突并重试或采用其他消歧方式;数据库检测也有成本,布隆过滤只可辅助减少检查,不能充当最终唯一性约束。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 短链 · 查看原书依据

      Hash + collision resolution To shorten a long URL, we should implement a hash function that hashes a long URL to a 7-character string. A straightforward solution is to use well-known hash functions like CRC32, MD5, or SHA-1. The following table compares the hash results after applying different hash functions on this URL: https://en.wikipedia.org/wiki/Systems_design. As shown in Table 8-2, even the shortest hash value (from

    参考来源

    - 位置:《System Design Interview – An insiders guide, Second Edition》第08章《短链》(来源项目 book-sources;源文件:extracted/System Design Interview – An insiders guide, Second Edition/_epub-src/text/part0021_split_003.html) - 结论依据:原文在该位置给出所述对象、机制或比较,支持本卡的解释;原书未展开的实现不作为已证明结论,算式与一致性边界在正文明确限定。 - 原始内容:Hash + collision resolution To shorten a long URL, we should implement a hash function that hashes a long URL to a 7-character string. A straightforward solution is to use well-known hash functions like CRC32, MD5, or SHA-1. The following table compares the hash results after applying different hash functions on this URL: https://en.wikipedia.org/wiki/Systems_design. As shown in Table 8-2, even the shortest hash value (from