Browsed by
分类:hash

[MARK]各种字符串hash算法

[MARK]各种字符串hash算法

 

hash 算法基础

hash 算法基础

首先来看一下什么是hash

hash 实际上就是一个映射函数 ,使得把某一个不满足条件的量(可能难于存储 可能没法表示)映射到一个满足条件的量上 举个简单的例子理解一下 : 某学校要对2014级新生进行入学成绩统计 要用数组来存储学生的信息 而大家的学号都是 2014**** 这样的形式且每人的学号唯一确定  那么如果开一个数组大小为  20150000肯定是足够我们使用了 ,不过 在这个大数组里 ,最多只用了 10000个值,所以我们考虑用一个后四位作为存储的数组下标而不是整个学号 这其实就是一个hash的思想  我们相当于建立了一个hash函数 f(x)=x%10000 这样的话我们节省了空间 同样也使效率变得高

最简单的hash思想 桶排序 参见 HDU 的 1425题 (排序复杂度可以简化到 n)

冲突

我们通过上面学生的例子 能够发现,一个理想的hash函数应该是个一一映射的函数 即仅存在唯一一组y,x使得f(x)=y 但是 ,实际使用的时候 ,hash函数的这个性质很难保证甚至根本不能保证 举个例子 :把1000000个数映射到100个hash表上 (hash表就是指存hash映射关系的那个数组) 那么 一定会有多个不同值映射到了一个地址上 ,这样的现象叫做 冲突(collision)   那么如何解决冲突就成为了很重要的问题 我们在这里介绍几个方式 主要介绍第一个方式 线性探测再散列

线性探测再散列

这个方法的思想就是 如果遇到了冲突,那么就去查找它的下一个地址处是否已经有值,一直走下去 (走到头的话就回到数组首端) 直到遇到没有值的地方或者是又再次回到了f(k)处 结束循环 成功找到的话把值放进去 ,否则hash散列失败 举个例子如下

我们对这六个数字进行散列操作 有

23%7=2 46%7=4 19%7=5 55%7=6 38%7=3 233%7=2 我们会发现 在地址2处产生了冲突,因此我们使用线性探测再散列 按照由左到右的顺序来执行hash 在处理233之前的结果为下图

这时 由于f(233)=2但是 2处已经有值 所以 执行下面操作 :逐次循环后移直到找到hash表内值为空的地方再放入233 结果就是 :

这就是线性探测再散列法处理冲突

代码如下

 

其它方式处理冲突

除了线性探测 我们还有

  1. 平方探测再散列 如果冲突则查看 addr+-1 +-4 +-9 …直到找到空位置为止
  2. 随机探测再散列 如果冲突则查看 addr+-一伪随机整数 直到找到空位置位置
  3. 再哈希法 顾名思义 再次对这个地址值用一个hash函数来处理
  4. 链地址法 把hash值相同的元素都存在同一个链表中
  5. 公共溢出区 ,这个是很实际中应用广泛的实用的方式,建立一个二维表,原理与链地址法相通,不过,这个是有限长度,那么为了处理个别的超出长度的量,建立一个溢出区来处理
以上是我对hash的一点理解和解读 请大神们看了多多批评指正  _(・ω・」 ∠)__(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_ _(・ω・」 ∠)_爬呀爬_(・ω・」 ∠)_ _(・ω・」 ∠)_ 我们中出了两个叛徒!

 

 

HDU 1496 Equations 数值hash

HDU 1496 Equations 数值hash

题目:

Equations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5612    Accepted Submission(s): 2228

Problem Description

Consider equations having the following form:

a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0.

It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}.

Determine how many solutions satisfy the given equation.

Input
The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.
End of file.
Output
For each test case, output a single line containing the number of the solutions.
Sample Input
1 2 3 -4
1 1 1 1
Sample Output
39088 0
这个题目,如果直接去暴力枚举三重循环的话 ,会导致超时,因此 不能简单枚举来做, 想到另一个方法 我们可以把式子变为

这样之后 ,我们可以先枚举 x1 x2求出 a*x1*x1+b*x2*x2的所有可能值出现的次数 并把次数存在数组里 num[a*x1*x1+b*x2*x2]=次数 然后 再用另一个二重循环枚举x3 x4 来看 c*x3*x3+d*x4*x4里有多少个值和之前重复且异号,然后 就可以直接将次数加上 不过 注意写好 由判断正负性来决定的存储在哪个数组的函数

本题开了两个数组 一个 hashpos存 正的结果 hashneg存负的结果,那么在循环 枚举x3x4的时候 ,就要判断好 什么时候域hashneg对应 什么时候与hashpos对应 我就是因为这个问题错了好几次  在我的这个代码下 应该是 当算出 c*x3^2+d*x4^2<0时 与hashpos对应 而 >=0与hashneg对应 这千万不要搞错!

AC代码如下

改进策略 线性探测再散列+小数组

这个代码能够 AC 不过还有可以继续用hash改进的地方 因为数组开的很大的时候 需要初始化数组的时间也很长,而 两个数字枚举最多产生10000种不同的结果 所以考虑开小数组来节省空间并且用线性探测再散列技术(linear-re hash detection 不知道这么翻译标准么 有待确定) 来处理冲突 那么就有下面的代码了

其中 用了两个数组,一个数组来存储hash映射关系 另一个存 hash(k)出现的次数  注意写好线性探测的循环条件 这个hash是通过一个函数既能查找到已有的映射关系又能建立新的映射关系,具体的代码说明见文章 hash算法基础(超链接)  这代码当时我写了好久然后发现样例不对,找了半天没找到问题后来发现是在散列函数里if后自己多写了个else = = SB了 改了就过了 时间由 1404MS->93MS 内存8988K->1566K hash大法好啊                 _(・ω・」 ∠)_