记--大日志文件如何查询每个搜索关键字出现的次数

hash算法有还哪些用途? hash算法得到的hash值不可逆的哦 1、安全加密 2、唯一性校验 3、数据验证 4、散列函数 5、负载均衡 6、数据分片 7、分布式存储         问题     负载均衡:     在nginx中有负载均衡的算法,有随机、轮巡、加权、源地址hash法(通过hash算法实现,得到机器编号)     数据分片:   1、如何统计“搜索关键词”出现的次数? 主要用到了hash算法 通过hash算法得到一个哈希值,通过对某个值进行取模得到最终结果     假如我们有 1T 的日志文件,这里面记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数,该怎么做呢?我们来分析一下。这个问题有两个难点,第一个是搜索日志很大,没办法放到一台机器的内存中。第二个难点是,如果只用一台机器来处理这么巨大的数据,处理时间会很长。

针对这两个难点,我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理 速度。具体的思路是这样的:为了提高处理的速度,我们用 n 台机器并行处理。我们从搜 索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。这样,哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说,同一个搜索关键词,会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。

 

2、如何判断一个图片是否在图库中?

  

假设现在我们的图库中有 1 亿张图片,很显然,在单台机器上构建散列表是行不通的。因 为单台机器的内存有限,而 1 亿张图片构建散列表显然远远超过了单台机器的内存上限。

 

我们同样可以对数据进行分片,然后采用多机处理。我们准备 n 台机器,让每台机器只维 护某一部分图片对应的散列表。我们每次从图库中读取一个图片,计算唯一标识,然后与机 器个数 n 求余取模,得到的值就对应要分配的机器编号,然后将这个图片的唯一标识和图 片路径发往对应的机器构建散列表。

当我们要判断一个图片是否在图库中的时候,我们通过同样的哈希算法,计算这个图片的唯 一标识,然后与机器个数 n 求余取模。假设得到的值是 k,那就去编号 k 的机器构建的散 列表中查找。

现在,我们来估算一下,给这 1 亿张图片构建散列表大约需要多少台机器。

散列表中每个数据单元包含两个信息,哈希值和图片文件的路径。假设我们通过 MD5 来计 算哈希值,那长度就是 128 比特,也就是 16 字节。文件路径长度的上限是 256 字节,我 们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突,那还需要存储指针,指 针只占用 8 字节。所以,散列表中每个数据单元就占用 152 字节(这里只是估算,并不准 确)。

假设一台机器的内存大小为 2GB,散列表的装载因子为 0.75,那一台机器可以给大约 1000 万(2GB*0.75/152)张图片构建散列表。所以,如果要对 1 亿张图片构建索引,需 要大约十几台机器。在工程中,这种估算还是很重要的,能让我们事先对需要投入的资源、 资金有个大概的了解,能更好地评估解决方案的可行性。

实际上,针对这种海量数据的处理问题,我们都可以采用多机分布式处理。借助这种分片的 思路,可以突破单机内存、CPU 等资源的限制。

 

 

 

 

 

 

 

 

上一篇:Java安全学习笔记--反序列化利用链HashMap类源码简单分析


下一篇:nginx配置详解