HASH查找的程序实现及性能分析

发布时间:2013-9-11

本文导语: 1 HASH查找基本原理在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为K，根据建表时设定的哈希函数H，计算出哈希地址H(K)，若表中该地址对应的空间未被占用，则查找失败，否则将该地址中的结点与给定...

1 HASH查找基本原理

在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为K，根据建表时设定的哈希函数H，计算出哈希地址H(K)，若表中该地址对应的空间未被占用，则查找失败，否则将该地址中的结点与给定值K比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。

2 查找算法演示

著名的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;
}

开放寻址法：

HashTable InitializeTable( int TableSize )
{
    HashTable H;
    int i;
    /* 为散列表分配空间。 */
    /* 有些编译器不支持为 struct HashTable 分配空间，声称这是一个不完全的结构， */
    /* 可使用一个指向 HashTable 的指针为之分配空间。 */
    /* 如：sizeof( Probe )，Probe 作为 HashTable 在 typedef 定义的指针。 */
    H = malloc( sizeof( struct HashTable ) );
    /* 散列表大小为一个质数。 */
    H->TableSize = Prime;
    /* 分配表所有地址的空间。 */
    H->Cells = malloc( sizeof( Cell )  * H->TableSize );
    /* 地址初始为空。 */
    for( i = 0; i < H->TableSize; i++ )
        H->Cells[i].info = Empty;
    return H;
}

查找空单元并插入：

Position Find( ElementType Key, HashTable H )
{
    Position Current;
    int CollisionNum;
    /* 碰撞次数初始为0。 */
    /* 通过表的大小对关键字进行处理。 */
    CollisionNum = 0;
    Current = Hash( Key, H->TableSezi );
    /* 不为空时进行查找。 */
    while( H->Cells[Current].info != Empty &&
        H->Cells[Current].Element != Key )
    {
        Current = ++CollosionNum * ++CollisionNum;
        /* 向下查找超过表范围时回到表开头。 */
        if( Current >= H->TableSize )
            Current -= H->TableSize;
    }
    return Current;
}

3 性能分析

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

(1)散列函数是否均匀；

(2)处理冲突的方法；

(3)散列表的载荷因子。

您可能感兴趣的文章:

本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载,整理或搜集自网络.欢迎任何形式的转载，转载请注明出处.
转载请注明：文章转载自:[169IT-IT技术资讯]
本文标题:HASH查找的程序实现及性能分析

相关文章推荐: