场景
假设你现在要处理这样一个问题，你有一个网站并且拥有很多访客，每当有用户访问时，你想知道这个ip是不是第一次访问你的网站。
hashtable 可以么
一个显而易见的答案是将所有的 IP 用 hashtable 存起来，每次访问都去 hashtable 中取，然后判断即可。但是题目说了网站有很多访客，
假如有10亿个用户访问过，假设 IP 是 IPV4， 那么每个 IP 的长度是 4 byte，那么你一共需要4 * 1000000000 = 4000000000Bytes = 4G 。
如果是判断 URL 黑名单，由于每个 URL 会更长（可能远大于上面 IPV4 地址的 4 byte），那么需要的空间可能会远远大于你的期望。
bit
另一个稍微难想到的解法是bit， 我们知道bit有 0 和 1 两种状态，那么用来表示存在与不存在再合适不过了。
假如有 10 亿个 IP，就可以用 10 亿个 bit 来存储，那么你一共需要 1 * 1000000000 = (4000000000 / 8) Bytes = 128M, 变为原来的1/32, 如果是存储URL这种更长的字符串，效率会更高。 问题是，我们怎么把 IPV4 和 bit 的位置关联上呢？
比如192.168.1.1 应该是用第几位表示，10.18.1.1 应该是用第几位表示呢？ 答案是使用哈希函数。
基于这种想法&
最低0.47元/天 解锁文章
2875
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
