Chinaunix首页 | 论坛 | 博客
  • 博客访问: 628553
  • 博文数量: 262
  • 博客积分: 8433
  • 博客等级: 中将
  • 技术积分: 2141
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-31 09:37
文章分类

全部博文(262)

文章存档

2012年(1)

2011年(168)

2010年(92)

2009年(1)

分类: 项目管理

2010-12-15 09:36:00

最近我在做一个项目,其中要用到一个数据结构——Hash Table(哈希表),以前只有理论知识,现在实却发现很不简单,所以写下来和大家共分享。

我们知道,哈希表是一个固定大小的数组,数组的每个元素是一个链表(单向或双向)的头指针。如果Key一样,则在一起,如果Key不一样,则不在一 起。哈希表的查询是飞快的。因为它不需要从头搜索,它利用Key的“哈希算法”直接定位,查找非常快,各种数据库中的数据结构基本都是它。但带来的问题 是,哈希表的尺寸、哈希算法。

哈希表的数组是定长的,如果太大,则浪费,如果太小,体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数,最小的质数尺寸是17。

当然,根据不同的数据量,会有不同的哈希表的大小。对于数据量很时多时少的应用,最好的设计是使用动态可变尺寸的哈希表,那么如果你发现哈希表尺寸 太小了,比如其中的元素是哈希表尺寸的2倍时,我们就需要扩大哈希表尺寸,一般是扩大一倍。下面的数库是哈希表变化尺寸时尺寸大小的一个列表。

static int prime_array[] = {
   17,             /* 0 */
    37,             /* 1 */
    79,             /* 2 */
    163,            /* 3 */
    331,            /* 4 */
    673,            /* 5 */
    1361,           /* 6 */
    2729,           /* 7 */
    5471,           /* 8 */
    10949,          /* 9 */
    21911,          /* 10 */
    43853,          /* 11 */
    87719,          /* 12 */
    175447,         /* 13 */
    350899,         /* 14 */
    701819,         /* 15 */
    1403641,        /* 16 */
    2807303,        /* 17 */
    5614657,        /* 18 */
    11229331,       /* 19 */
    22458671,       /* 20 */
    44917381,       /* 21 */
    89834777,       /* 22 */
    179669557,      /* 23 */
    359339171,      /* 24 */
    718678369,      /* 25 */
    1437356741,     /* 26 */
    2147483647      /* 27 (largest signed int prime) */
};               
#define PRIME_ARRAY_SIZE  (28)
 

要使用哈希表,就一定要用一个哈希算法,来确定KEY值,这似乎是个很难的事,下面是一个哈希算法:
typedef struct _hTab{
    hLinks* link;    /* 一个链表 */
    int  num;     /* 成员个数 */
    int  size;    /* 表的尺寸 */
} hTab;
static unsigned int
getHashIndex(hTab *tabPtr, const char *key)
{
    unsigned int ha = 0;
  
    while (*key)
        ha = (ha * 128 + *key++) % tabPtr->size;
    return ha;
}
(其中key是一个字符串,hTab就是一个哈希表结构, tabPtr->size是哈希表数组的大小)
这个算法被实施证明是比较不错的。

字符串哈希函数

(著名的ELFhash算法)


int ELFhash(char *key)   

{ unsigned long h=0;   

while(*key)   

{ h=(h<<4)+*key++;   

unsigned long g=h&0Xf0000000L;   

if(g) h^=g>>24;   h&=~g;   }   

return h%MOD;   }


阅读(738) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~