Hash算法的使用

标签: 默认分类 | 发表时间:2011-08-06 06:35 | 作者:GliderX khsing
出处:http://hi.baidu.com/gliderx

在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数。以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的。

首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了。具体算法请参考:http://blog.csdn.net/eaglewood2005/article/details/4394583。

但很遗憾,这种算法对于一个文本有数百万条记录的情况处理不够理想。首先,预先分配的Table数量是有限的,我分配0x3ffffff大小,再大就很容易分配失败了。其次,正是由于他不用链表处理冲突,当越来越多的加入进来时,处理冲突地方就需要不断往下轮询空余的Table下标,当积累到一定的时候,大概是200万条记录的时候,效率就开始急剧下降,降将到我无法接受,进度条很久都不会动,最后没耐心等下去了。

 

第二个选择的算法是一个很常见的OpenSSL里的算法

unsigned long lh_strhash(char *str)
{
    int i,l;
    unsigned long ret=0;
    unsigned short *s;

    if (str == NULL)
        return(0);
    l=(strlen(str)+1)/2;
    s=(unsigned short *)str;
    for (i=0; i<l; i++)
        ret^=(s[i]<<(i&0x0f));
    return(ret);
}

很简单吧,不过这个算法也仅在一个数量范围内比较好用,对于大记录的hash效果不好,我对328万条记录的结果,bucket利用率仅仅只有 2.14%,最大的冲突长度高达147。 其实这个算法也让程序在20分钟内统计完成。

 

不过感觉2.14%的利用率实在太低,有必要选择一个更好的算法。于是找到了php的hash算法,这个zend公司的算法也是time33的一种,而且有独到的地方,比如他的hash值不是从0开始,而是从5381开始,5381这个数字有什么意义呢?

Magic Constant 5381:
  1. odd number
  2. prime number
  3. deficient number
  4. 001/010/100/000/101 b

算法我就不列了,大家可以很容易找到。这个算法非常有效,程序运行速度翻倍,只要10分钟就可以统计好一个4GB的语料库,而且更加惊人的是在相同的测试条件下,他的bucket利用率高达33.16%,最大冲突长度只有14。

 

最后借用一个前辈的说法“算法的力量很强”。

阅读全文
类别:默认分类 查看评论

相关 [hash 算法] 推荐:

Hash算法的使用

- khsing - Glider&#39;s home
在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数. 以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的. 首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法( consistent hashing ). consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出,目前在cache 系统中应用越来越广泛;. 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;.

一致性Hash算法背景(转)

- - 开源软件 - ITeye博客
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似. 一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用.   但现在一致性hash算法在分布式系统中也得到了广泛应用,研究过memcached缓存数据库的人都知道,memcached服务器端本身不提供分布式cache的一致性,而是由客户端来提供,具体在计算一致性hash时采用如下步骤:.

一致性hash算法测试

- - Java - 编程语言 - ITeye博客
package com.xll; //服务器对象 public class Server {. private void init() { // 初始化一致性hash环. for (int i = 0; i != servers.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点.

[转][转]memcache的一致性hash算法使用

- - heiyeluren的Blog
来源: http://blog.csdn.net/kongqz/article/details/6695417.   1、我们的memcache客户端(这里我看的spymemcache的源码),使用了一致性hash算法ketama进行数据存储节点的选择. 与常规的hash算法思路不同,只是对我们要存储数据的key进行hash计算,分配到不同节点存储.

从头到尾彻底解析Hash表算法

- - 博客园_知识库
  作者:July、wuliming、pkuoliver.   说明:本文分为三部分内容, 第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法.    第一部分:Top K 算法详解.   问题描述(百度面试题):.   搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.

一致性hash算法在memcached中的使用

- - CSDN博客推荐文章
  1、我们的memcache客户端(这里我看的spymemcache的源码),使用了一致性hash算法ketama进行数据存储节点的选择. 与常规的hash算法思路不同,只是对我们要存储数据的key进行hash计算,分配到不同节点存储. 一致性hash算法是对我们要存储数据的服务器进行hash计算,进而确认每个key的存储位置.

【转】一致性hash算法与server列表维护

- - 编程语言 - ITeye博客
考虑到不用重复造轮子,特此转载好文,出处http://shift-alt-ctrl.iteye.com/blog/1963244.     普通的hash算法有个很大的问题:当hash的"模数"发生变化时,整个hash数据结构就需要重新hash,重新hash之后的数据分布一定会和hash之前的不同;在很多场景下,"模数"的变化时必然的,但是这种"数据分布"的巨大变化却会带来一些麻烦.所以,就有了"一致性hash",当然学术界对"一致性hash"的阐述,还远远不止这些..

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%).