左（6）hash，大数据，位运算-创新互联

前言

仅记录学习笔记，如有错误欢迎指正。

建网站原本是网站策划师、网络程序员、网页设计师等，应用各种网络程序开发技术和网页设计技术配合操作的协同工作。成都创新互联专业提供做网站、网站制作,网页设计,网站制作(企业站、响应式网站设计、电商门户网站)等服务,从网站深度策划、搜索引擎友好度优化到用户体验的提升,我们力求做到极致!一、哈希函数和哈希表：

hash()：
(1) 输入是无限的，输出有限！
(2)相同的输入，相同的输出（无随机因子）
(3)不同的输入，也可能相同的输出 (hash碰撞，概率极低)
(4)不同的输入，但是分布具有均匀性

一致性哈希原理：

key的选择：尽量种类多

在这里插入图片描述
因为一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，只有部分缓存会失效，不至于将所有压力都在同一时间集中到后端服务器上，具有较好的容错性和可扩展性。（增减机器数据迁移工作量大大减少）

问题1：如果机器数据少，怎么把环均分？问题2：增减机器怎么负载均衡？解决方案：虚拟节点

一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点，一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。

题目：

一个大文件，文件中都是无符号的整数（0-2^32），40亿个数字，
1g内存，返回出现次数最多的数字！

思路：

对于每一个数做hash运算，取模100，得到100个文件夹分别存模后的数据，
因为均匀性，所以文件中的数字数量基本一致，相同的数字肯定都在一个文件中，
之后在对每个文件找出现次数最多数字，100个文件找出100个数字，再取出现最多的数字！

布隆过滤器:（通过hash计算值的）就是bitmap实现的！

布隆过滤器优缺点 :
下图hash1(key)=1，那么在第2个格子将0变为1(数组是从0开始计数的)，hash2(key)=7，那么将第8个格子置位1，依次类推。

在这里插入图片描述

怎么判断数据是否存在？

只要把这个数据的hash值找出来，去看value是不是1，不是1就肯定不存在，是1就可能存在，还有可能是其他数据。

优点：优点很明显，二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。
缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。

BitMap：

占用空间1B，很小
用int类型表示bit类型
在这里插入图片描述

二、大数据类型题目：

在这里插入图片描述

题目1.

在这里插入图片描述

思路：

法一：
利用磁频统计数量来定位没出现的数字，如果只有3kb，约等于512B,用40亿除512=x
然后遍历40亿数字，用每个数字/x 出来的范围++，肯定有某个范围小于x的数量。
然后在当前范围内用bitmap，存在置为1，再次遍历为0的数字就是不存在的数据
法二：
或者利用0~40亿二分，最多遍历32次，把数字所在区间找出来、
然后在当前范围内用bitmap，存在置为1，再次遍历为0的数字就是不存在的数据

题目2：

在这里插入图片描述
法一：把大文件hash后取模为小文件，之后去小文件中统计重复的url，汇总
法二：利用布隆过滤器，每次插入的数据的时候先去查询是否已经存在，存在则保存。（有一定误判率）