数据结构与算法之大数据相干标题

一，哈希函数


特性：
1.输入阈无穷，输出阈有限
2.类似的输入参数，一定返回类似的值
3.不同的输入，有可能会导致类似的输出（哈希碰撞）
4均匀性，离散性（假设有一个输入聚集a，通过哈希函数f得到一个均匀分布的数据聚集b，b再模m，那么就会得到一组在0~m-1上均匀分布的数）

例题1：

假设有一个大文件，大文件中都是无符号整数，值范围是0~2的32次方-1，如许的数有40亿个，如果只有1G内存，返回出现次数最多的数是哪个数。

 如果将这一个文件放到一个哈希表中谁人需要的最大内存是32G（最坏的情况下所有数都不一样，（key 4B+value4B）*40亿），以是将文件分割成100个文件（统计完一个文件内存释放掉），将m1 =3那么将a1放到3号文件中，根据哈希函数的性质，0到99号文件含有不同种数的数量是差不多的， 每个文件中都会有一个出现最多的数，一共有100个，100个次数中最多的就是最后返回值
二.哈希表的实现

 哈希表最大的特点是在使用的时间查询时间复杂度可以认为是O（1），如果链表长度太长那么肯定不符合，以是需要扩容。最主要的是不让链表长度太长，那么扩容代价怎么算？假设有N个字符串，那么最坏的情况下需要扩容logN次（可以假设每个链表长度不高出2），每次扩容需要的代价是O（n）因为每个格子（桶）都要重新计算哈希值和挂链表，总的扩容代价是O（n*logN）。那么单次一个扩容的代价是N*logN/N =logN水平，实际设计的时间可以将n设置的很大，又因为logN是一个小常数，以是最后复杂度无限接近O（1）。这是经典哈希表实现。不同语言都有区别
例题2：

默认哈希表在使用的时间是O（1），准备两个哈希表 map1 （str->index） map2（index->str)

t如果没有删除活动，调用系统随机函数得到一个数，再根据index得到对应的字符串。
假设现在要删除D，用最后一个数（size-1）填补
三.布隆过滤器

应用：黑名单

 误杀的失误率很低
位图：比特类型的数组

  

 如何得到178位置比特的状态？

可以得到bit位置
 

 第178位的信息跑到最右侧位置，然后跟1与得到其信息

实现：

向布隆过滤器添加操作：将url通过k个hash%m，描黑变成q
查询：某个url通过上边类似操作，如果有一个不是1，那么肯定不在里边。
 那么其实变量就是m和K

 

 四.划一性hash原理


将哈希值的返追念象成环

 当一个哀求进来的时间，通过hash函数算出的值打到环中，放到离这个数迩来的呆板上
那么如何实现？当哀求打到逻辑服务端的时间，各个服务端维护一个呆板hash值的有序数组，通过二分查找即可
缺点：呆板数量少的时间容易出现数据倾斜问题，一旦增长或者减少会更加不均分
好处：数据迁徙的代价只是部门范围的数据

那么如何解决数据迁徙问题？假造节点技术
每个呆板都分配一定数量的假造节点去抢环

五.大数据例题技巧

一般大数据标题有如下技巧：

 这个标题可以直接用hash分流或者布隆过滤器，关于增补是另外一种方法堆的头脑。
先通过hash分流到各个小文件里去，根据hash函数的特性一种重复的url只会出现在一个小文件里，在小文件中统计词频可以包管内存不会爆掉，如许就可以得到每个小文件的每天的前100个高词频，将每个大根堆的堆顶组成一个总堆，将总堆的堆顶弹出，然后看总堆刚才弹出来的的堆顶属于哪个大根堆，找到这个数将它从这个大根堆顶删掉，然后将新的堆顶加到总堆里去，周而复始，知道总堆弹出100个

 

使用500m内存的位图可以描述所有（原问题）
增补进阶：将3kb内存转换为最大的int【】 3k/4 约等于 往下接近迩来的2的N次方也就是准备一个长度512的数组 ，那么将范围0-2的32次方均分为512份，也就是说 数组中每个位置可以表现2的32次方/512范围的数

便利40亿个数，设此时x/8388608一定在数组下标中，如果出现过将arr【x】+1 .一共有40亿个数，但是范围最大有42亿，以是一定有一个词频统计他的数值不够8388608，那么可以确定这个数所在的大范围，然后按照这个方法渐渐缩小范围。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。