12306网站建设超30亿,设计专业大学排名,北京做网站的,陕西建设银行网站缘起 写这篇文章#xff0c;源于这么一个问题#xff1a;假设目前有一千万个URL访问记录#xff0c;请统计最热门的10个查询串。(见此文)。见到这个问题的第一想法使用hash解决#xff0c;没考虑hash冲突解决的问题(其实就没想比较URL#xff0c;不比较URL无法判断冲突与否… 缘起 写这篇文章源于这么一个问题假设目前有一千万个URL访问记录请统计最热门的10个查询串。(见此文)。见到这个问题的第一想法使用hash解决没考虑hash冲突解决的问题(其实就没想比较URL不比较URL无法判断冲突与否)。后来意识到hash解法在内存受限情况下存在致命缺陷才有写这个blog的想法。 散列/散列函数 Hash一般翻译做“散列”也音译为哈希就是把任意长度的输入又叫做预映射 pre-image通过散列算法(散列函数)变换成固定(或不定)长度的输出该输出就是散列值。这种转换是一种压缩映射也就是散列值的空间通常远小于输入的空间不同的输入可能会散列成相同的输出而不可能从散列值来唯一的确定输入值。散列函数或散列算法Hash Function是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合重新创建一个叫做散列值的指纹。 作为特征值的散列 散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。密码学上的 Hash 又被称为消息摘要(message digest)。简言之“指纹”、“信息摘要”本质就是数据的特征值即散列函数可用于提取数据的特征值。在模式识别中由于处理原始数据比较困难经常通过提取数据的多维特征值来简化数据处理。 最佳的特征值是能完全表征数据的特征值实际当中很难找到不管是一维还是多维的特征值。完美散列就是希望能够找到能唯一表征原始数据的散列函数。 散列函数有一个基本特性输出不同原始数据必然不同输出相同原始数据可能不同。将无限定义域映射成有限值域必然存在冲突。加密散列函数是很不错的散列函数其输出是一个很大的整数值域很大故冲突较少。 因为散列值无法唯一表征原始数据故冲突判断只能通过比较原始数据方能得知。作为特征值的哈希值非常适合用于判断原始数据是否不同比如文件、图片等。 MPQ散列函数 MPQ使用文件名哈希表来跟踪内部的所有文件。算法使用了3种不同的哈希一个用于哈希表的下标两个用于验证。这两个验证哈希替代了实际文件名。其本质就是使用3个哈希值来表征文件当然mpq无法解决散列冲突问题即相同的3个哈希值对应两个不用的文件。 容忍冲突的散列(什么场合冲突可容忍) 原始问题 假设目前有一千万个记录这些查询串的重复度比较高虽然总数是1千万但如果除去重复后不超过3百万个。一个查询串的重复度越高说明查询它的用户越多也就是越热门。请你统计最热门的10个查询串要求使用的内存不能超过1G。 问题1将记录规模扩大1000倍即几十亿的记录内存几十G。 问题2将记录规模扩大1000倍即几十亿的记录内存几G。即在内存受限的情况下如何处理数据。(内存读写比硬盘快100倍以上随机读写估计在1w倍以上直接以磁盘空间代替内存空间的做法就不用提了) 对于问题1想过一个算法元数据存于内存URL存磁盘。元数据URL哈希值、访问计数文件偏移量所有的URL均存在磁盘中。这个算法有个前提忽略冲突将URL哈希值作为URL的唯一表征。元数据量不大((888)*1G24G)可全部在内存中存放处理很快比较URL哈希值远比直接比较URL快URL采用追加方式写入磁盘效率也不是问题。但是忽略冲突却是一个致命的缺陷。 当然可以采取一些措施来减少哈希冲突如采用128为哈希值采用多维特征值(URL长度双哈希值(可直接使用中间哈希值和最终哈希值))但这些都无法保证无冲突即不可能采用有限的特征来表示无限的URL空间 分布式方案mapreduce 元问题如果不能直接使用内存来处理所有的数据那么问题1和2就退化成同样的问题如何在内存受限的情况下处理大规模的数据 这样的问题有通用解法map-reduce。即先对数据分类(独立的类别)再分别处理最终归并结果。 1) 将原始记录通过hash分别记录到不同的N个文件(同一个URL只出现在一个文件中) 2) 分别对N个文件做统计处理排序输出 3) 采用最小堆挑出最热门的m个记录。 经过这么分类之后这个算法本质上是可并行处理的很容易在分布式集群中实现。“分而治之”的办法真的很实用(怎么分很重要)。Mapraduce的思想也很通用。 参考文献 从头到尾彻底解析Hash 表算法 wiki散列 wiki散列函数 本文转自 zhenjing 博客园博客原文链接 http://www.cnblogs.com/zhenjing/archive/2011/06/09/hash.html 如需转载请自行联系原作者
