你知道的越多，你不知道的越多。

[hakunamatata11]

大家都知道海量数据有很多的解法，方法不一定最优，不同的解法有不用的最佳适用场景。今天在这边我先分享其中一种解法：

Hashing

适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

基本原理及要点：

hash 函数选择，针对字符串，整数，排列，具体相应的 hash 方法。

碰撞处理，一种是 open hashing，也称为拉链法；另一种就是 closed hashing，也称开地址法，opened addressing。

扩展：

d-left hashing 中的 d 是多个的意思，我们先简化这个问题，看一看 2-left hashing。2-left hashing 指的是将一个哈希表分成长度相等的两半，分别叫做 T1 和 T2，给 T1 和 T2 分别配备一个哈希函数，h1 和 h2。在存储一个新的 key 时，同时用两个哈希函数进行计算，得出两个地址 h1[key]和 h2[key]。这时需要检查 T1 中的 h1[key]位置和 T2 中的 h2[key]位置，哪一个位置已经存储的（有碰撞的） key 比较多，然后将新 key 存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个 key，就把新 key 存储在左边的 T1 子表中，2-left 也由此而来。在查找一个 key 时，必须进行两次 hash，同时查找两个位置。

问题实例：

海量日志数据，提取出某日访问百度次数最多的那个 IP。IP 的数目还是有限的，最多 2^32 个，所以可以考虑使用 hash 将 ip 直接存入内存，然后进行统计。

---

除此之外，九章算法为正在准备明年春招的你赠送免费的《海量数据处理算法与面试题全集》，基础知识和刷题都覆盖到了~

这门原价$199 的课程，现在只要报名试听即可免费获得全系列课程！

参与方式：

戳我免费试听后，添加九章 Sunny 微信 jiuzhang15，回复 [ V2EX 海量数据] + 试听报名截图即可免费解锁海量数据全系列课程。