编程科技探索
秒查字典的哈希表
哈希表能让电脑在几亿数据里瞬间找到你要的，怎么做到的？
7-10岁6分钟编程 · 数据结构 · 哈希
查字典时，你不会一页页翻，而是按拼音或部首直接翻到那页，几秒就找到。电脑查数据也一样：如果一条条翻，几亿条要翻好久。可有一种叫“哈希表”的数据结构，能让电脑几乎“瞬间”找到任何一条数据，怎么做到的？秘密就在一个叫“哈希函数”的小魔法。
你知道吗
你知道吗？哈希表平均查找速度跟数据量没关系——不管存 100 条还是 1 亿条，查找时间都差不多。这就是它神奇的地方。
哈希函数的小魔法
哈希表靠“哈希函数”把“钥匙”变成“地址”。比如存电话簿：把每个人的名字输给哈希函数，它算出一个数字当抽屉号，把信息放那个抽屉。查的时候，输入名字，函数算出同一个抽屉号，直接去那个抽屉拿——不用一个抽屉一个抽屉翻！只要函数算得快，查找就瞬间完成。
理想情况下，每个钥匙算出不同的抽屉号。但抽屉有限，难免有两个钥匙算出同一个号，这叫“冲突”。解决办法：那个抽屉里放一个小链表，把冲突的几条都串起来。查找时去抽屉里再顺着链表找一下，还是很快。所以哈希表即使有冲突，也比对所有数据挨个找快得多。
- 哈希函数把钥匙变成抽屉号
- 查的时候算号直接去抽屉拿
- 冲突：两个钥匙算出同一号
- 冲突用链表串起来解决
- 密码、缓存、数据库索引都用哈希
哈希表无处不在。你登录网站，密码就是用哈希函数加密存的；网上的缓存、数据库的索引、区块链的区块，都用哈希。它的核心思想是“用计算换时间”：多算一步哈希，省下大把查找时间。这也是为什么同样的数据，有的程序快、有的慢——数据结构选对了，速度天差地别。
动手试试
动手玩：准备 10 个小盒子当“抽屉”。写一个简单哈希函数：把名字每个字的笔画数加起来，除以 10 取余数当抽屉号。把家人朋友的名字按这个函数放进对应盒子。然后查一个名字：先算号，再去那个盒子找，体会“秒查”。如果有冲突（两个名字同号），在那个盒子里放一张小纸条列出来。把你的哈希表画下来。
算一算，省下千次找。——编程小语
