认识达内从这里开始

认真做教育专心促就业

如何高效的处理亿万级数据？（4）

发布：青岛达内
来源：青岛达内
时间：2019-03-20 14:00

青岛达内的小编总结，海量日志数据，提取出某日访问百度次数最多的那个IP
无非分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，后统计，最后排序
分而治之/hash映射
针对数据太大，内存受限，只能把大文件化成（取模映射）小文件
HashMap统计：当大文件转化了小文件，便可以采用常规的HashMap（ip,value）进行频率统计
堆/快速排序
统计完了之后，进行排序（可采取堆排序），得到次数最多的IP
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。
注意到IP是32位的，最多有个2^32个IP.同样可以采用映射的方法，比如%1000,把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用HashMap对那1000个文件中的所有IP进行频率统计，然后依次找出各个文件中频率最大的那个IP）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP,即为所求。
还有几个问题

Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中的情况，即这里采用的是mod 1000算法，那么相同的IP在hash取模后，只可能落在同一个文件中，不可能被分散

青岛达内

那到底什么是hash映射呢？
简单来说，就是为了便于计算机在有限的内存中处理大数据，从而通过一种映射散列的方式让数据均匀分布在对应的内存位置（如大数据通过取余的方式映射成小树存放在内存中，或大文件映射成多个小文件），而这个映射散列方式便是我们通常所说的hash函数，好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发生了变化而已
堆
概念
堆是一种特殊的二叉树，具备以下两种性质
每个节点的值都大于（或者都小于，即最小堆）其子节点的值
树完全平衡的，并且最后一层的树叶都在最左边
这样就定义了一个最大堆
数组表示堆
二叉堆
一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个二叉堆
最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢
假设要在这个二叉堆里入队一个单元，键值为2,那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο（logn）的操作，二叉堆还是二叉堆。
以上就是青岛达内给大家做的内容详解，更多关于UI的学习，请继续关注青岛达内

< 上一篇：如何高效的处理亿万级数据？（3）

下一篇：如何高效的处理亿万级数据？（5） >