专题：hash -- IT技术博客大学习 -- 共学习共进步！

对于海量数据处理业务，我们通常需要一个索引数据结构，用来帮助查询，快速判断数据记录是否存在，这种数据结构通常又叫过滤器(filter)。考虑这样一个场景，上网的时候需要在浏览器上输入URL，这时浏览器需要去判断这是否一个恶意的网站，它将对本地缓存的成千上万的URL索引进行过滤，如果不存在，就放行，如果（可能）存在，则向远程服务端发起验证请求，并回馈客户端给出警告。索引的存储又分为有序和无序，前者使用关联式容器，比如B树，后者使用哈希算法。这两类算法各有优劣：比如，关联式容器时间复杂度稳定O(logN)，且支持范围查询；又比如哈希算法的查询、增删都比较快O(1)，但这是在理想状态下的情形，遇到碰撞严重的情况，哈希算法的时间复杂度会退化到O(n)。因此，选择一个好的哈希算法是很重要的。

HashMap解决hash冲突的方法

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法时，系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。

Ubuntu 下Hash校验和不符问题的解决

在Ubuntu 下有一个问题经常会困扰大家，就是运行 apt-get update 是出现 Hash校验和不符的提示。

无锁HashMap的原理与实现

HashMap主要有插入、删除、查找以及ReHash四种基本操作。一个典型的HashMap实现，会用到一个数组，数组的每项元素为一个节点的链表。对于此链表，我们可以利用文中提到的操作方法，执行插入、删除以及查找操作，但对于ReHash操作则比较困难。

MinHash原理与应用

MinHash首先它是一种基于 Jaccard Index 相似度的算法，也是一种LSH的降维的方法，应用于大数据集的相似度检索、推荐系统。下边按我的理解介绍下MinHash。举例A，B 两个集合： A = {s1, s3, s6, s8, s9} B = {s3, s4, s7, s8, s10} 根据Jaccard Index公式，A,B的相似度 S(A,B) = |A∩B|/|A∪B| = 2/8 = 0.25，用图表示如下：当然直接计算两个集合的交集与并集，是很耗计算资源的，特别是在海量数据场景下不可行。假如，我们随机从两个集合中各挑选一个元素s(A)、s(B)，刚好这两个无素相同的概率是多少呢？

LVS hash size解决4096个并发的问题

LVS 有个 connection hash table ，默认的 size 为 4096，可以通过以下命令得到：# ipvsadm -lnIP Virtual Server version 1.0.12 (size=4096)简单地说，这个hash table 用于记录每个进来的连接及路由去向的信息。面对庞大的连接时，这个4096是远远不够的，这时就会产生冲突，然后hash table 就不断置换table 中的数据，系统的负荷就这样上来了。所以，很多调优文章都说，要把这个值调大。至于如何调大呢，好像必须重编译内核了。。。

基于hash计算的多层实验流量切分的实现

背景介绍站点新功能或者是站内新策略开发完毕之后，在全流量上线之前要评估新功能或者新策略的优劣，常用的评估方法是A-B测试，做法是在全量中抽样出两份小流量，分别走新策略分支和旧策略分支，通过对比这两份流量下的各指标的差异，我们可以评估出新策略的优劣，进而决定新策略是否全流量。上文中提到的抽样是指按照某种确定的随机化方法，对线上流量进行划分。抽样可以指这种划分的方法，也可以指划分得到的一个流量子集。抽样是一种特殊的小流量，要求对流量的划分必须保证均匀性和随机性，并且可以根据需求过滤掉不符合规范的部分，我们把抽样的过程分为流量切分和流量筛选两个步骤，流量切分是指把全流量进行均匀的打散，提取出其中固定的流量比例，流量筛选是对流量切分的辅助，筛选过程就是从切分好的流量中过滤掉不符合规范的部分，本文主要涉及的是流量切分的实现。

Java Hash Algorithm Collision Practice （JAVA哈希算法冲突实践）

制造Hash冲突可引发Hashtable数据结构退化为低效链表，常用于DoS攻击。背景及几句废话 2012年的第一篇blog，想想还是写点技术相关的。最近安全圈比较热的话题是hash algorithm collision dos attack. 截止到本文发布之时，比较优雅解决这一问题的厂商依然只是少数。为了促进这一问题得到尽快解决，我认为有必要在更大的范围内普及这一攻击的基础知识。本文主要思路以代码方式提供。如果不能保证独立运行以下代码，请绕道；如果对代码可读性有疑问，那是我故意的。

关于memcache分布式一致性hash

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出，目前在 cache 系统中应用越来越广泛； 1 基本场景比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N 个 cache 上呢，你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到到 N 个 cache ； hash(object)%N 一切都运行正常，再考虑如下的两种情况；

Nginx过滤hash ddos攻击

这事可能都过气了，不过还是贴出我使用的方式吧，用的着的可以参考. 上段时间的各语言hash绝对印象深刻吧，做网站的几乎都在此类，不论你是用的是php，python还是ruby都不同程度受到影响, PHP尤其明显，因为PHP用的人也多嘛，攻击方式简直简单到不行，有兴趣的可以找我索取此测试脚本，一个终端随便搞挂一台有次漏洞的PHP站点. 我们http请求都是通过nginx反向代理，所以优势是可以在nginx这一层对请求做很多逻辑,此次防hash dos就是这个架构.

通过调用Hash冲突实现各种语言的拒绝服务攻击漏洞

上周的时候Dmitry突然在5.4发布在即的时候, 引入了一个新的配置项: Added max_input_vars directive to prevent attacks based on hash collisions 这个预防的攻击, 就是\"通过调用Hash冲突实现各种语言的拒绝服务攻击漏洞\"(multiple implementations denial-of-service via hash algorithm collision).

PHP数组的Hash冲突实例

上一篇文章, 我介绍了一个利用Hash冲突(碰撞)来对各种语言(包括,PHP, Java, Ruby等等)实施拒绝服务攻击的可能, 但是没有给出实例, 文章发出后, @Ferrari同学给出了一个另外一篇文章Supercolliding a PHP array, 文章中作者介绍了一种基于PHP的冲突实例, 以及带来的性能恶化对比. 我就借花献佛, 翻译给大家看看. 你知道不知道, 插入65536个经过构造的键值的元素到PHP数组, 会需要耗时30秒以上? 而一般的这个过程仅仅需要...

谈谈近期的安全事件

微博发了一道安全常识题，从反馈看，搞不太清楚的人还是蛮多的。有意思的是，搞不清楚的人多数认为是我搞错了。微博就144个字，也说不开，挪这里详细说说。很多网站都有用户系统，有用户系统就有密码存放，通常，密码都是加密传输的，为了安全，通常是单向散列加密，或者说，不可逆加密，一个简单的判断是，你通过密码找回功能操作，如果让你重设密码的，基本上是不可逆加密的，直接给你密码的，都是明文或可逆加密的，这种...

hash攻击的几点想法

最近关于hash的攻击很火，这个问题存在的时间很久了。有几点想法，写出来和大家分享一下。 hash的好处是查找速度快，但是通过特殊的输入，会造成冲突链过长，查找会退化成一个链表遍历操作。对于hash来说，有几个重要的参数 1)hash table size，也就是hash的映射空间，很显然，hash表越大，映射的冲突几率就越小。 2)hash function，冲突取决于几个因素，一是输入源，二是hash function。好的hash function可以把非随机的输入源映...

redis源代码分析 - hash table

hashtable的实现有很多，redis的dict.c 是其中之一。 dict 包含了2个dictht hashtable ht[0], ht[1]。 client版本的dict是没有dictht的概念。加入dictht的概念存在2个ht的目的是为了在rehash的时候可以平滑的迁移bucket里的数据，而不像client的dict要把老的hash table里的一次性的全部数据迁移到新的hash table，这在造成一个密集型的操作，在业务高峰期不可取。 ht是hashtable的简称，实际上是一个指针数组，数组的个数由dictht-...

Hopscotch Hashing

这是一种开放地址HASH，主要目的是为了提高查询速度。提高查询速度常用的思路是在插入的时候对数据作调整，让数据更紧凑。常用的方法在HASH表比较满的情况下，复杂度都很难保证。这个方法的特点是，它可以保证最坏情况下，查询的复杂度也是个常数。元素X算HASH后，应该存在I节点，则允许它存在【I，I+H)之间第一个空闲的节点，H一般去32，一是H比较小，用一个INT作BITMAP就可以表示它后面哪些元素是HASH到这里的。二是，H太...

Oracle hash join

hash join是oracle里面一个非常强悍的功能，当做hash join时，oracle会选择一个表作为驱动表，先根据过滤条件排除不必要的数据，然后将结果集做成hash表，放入进程的hash area，接着扫描第二张表，将行的键值做hash运算，到内存的hash表里面去探测，如果探测成功，就返回数据，否则这行就丢弃掉这个是最基本的解释，实际情况中，考虑到单个进程PGA的大小，oracle不会让进程任意的消耗OS内存，hash area是有一定限制的，所以在oracl...

HMAC-*算法集合

HMAC-SHA1、HMAC-MD5等算法，在PHP5.1.X之后，可直接使用如下形式来计算 echo hash_hmac(\'sha1\',$data,$key); 如果加载了MHASH扩展，也可直接使用mhash来进行运算 echo bin2hex(mhash(MHASH_SHA1, $data, $key)); 如果PHP版本低于5.1.X或者没有加载Mhash、或HMAC扩展，可使用如下的通用方法来进行相应运算下载:

当使用 Nginx 做 Hash 时对动态文件和静态文件的处理

nginx 做 url 的 hash 时，做动态和静态的 hash 时需要多多注意。因为动态和静态的文件表现出来的不一样。静态文件 Nginx 的 Hash 处理静态的文件的源网站的，特点文件静态，大小基本是几种类型...

思考mysql内核之初级系列7---innodb的hash表实现