亲宝软件园·资讯

展开

散列表算法与其C语言实现 详解散列表算法与其相关的C语言实现

zinss26914 人气:0
想了解详解散列表算法与其相关的C语言实现的相关内容吗,zinss26914在本文为您仔细讲解散列表算法与其C语言实现的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:散列表,C,下面大家一起来学习吧。

散列表(也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时不需要进行一系列和关键字(关键字是数据元素中某个数据项的值,用以标识一个数据元素)的比较操作。

    散列表算法希望能尽量做到不经过任何比较,通过一次存取就能得到所查找的数据元素,因而必须要在数据元素的存储位置和它的关键字(可用key表示)之间建立一个确定的对应关系,使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时,只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用h(key)表示)。

    根据设定的散列函数h(key)和处理冲突的方法将一组关键字key映像到一个有限的连续的地址区间上,并以关键字在地址区间中的像作为数据元素在表中的存储位置,这种表便被称为散列表,这一映像过程称为散列,所得存储位置称为散列地址。

    关键字、散列函数以及散列表的关系如下图所示:

201581193721542.jpg (401×270)

     1、散列函数

    散列函数是从关键字到地址区间的映像。

    好的散列函数能够使得关键字经过散列后得到一个随机的地址,以便使一组关键字的散列地址均匀地分布在整个地址区间中,从而减少冲突。

    常用的构造散列函数的方法有:

    (1)、直接定址法

    取关键字或关键字的某个线性函数值为散列地址,即:

    h(key) = key   或 h(key) = a * key + b

    其中a和b为常数。

    (2)、数字分析法

    (3)、平方取值法

    取关键字平方后的中间几位为散列地址。

    (4)、折叠法

    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为散列地址。

    (5)、除留余数法

    取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址,即:

    h(key) = key MOD p    p ≤ m

    (6)、随机数法

    选择一个随机函数,取关键字的随机函数值为它的散列地址,即:

    h(key) = random(key)

    其中random为随机函数。

    2、处理冲突

    对不同的关键字可能得到同一散列地址,即key1 ≠ key2,而h(key1)= h(key2),这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词。

    在一般情况下,散列函数是一个压缩映像,这就不可避免地会产生冲突,因此,在创建散列表时不仅要设定一个好的散列函数,而且还要设定一种处理冲突的方法。

    常用的处理冲突的方法有:

    (1)、开放定址法

    hi =(h(key) + di) MOD m     i =1,2,…,k(k ≤ m-1)

    其中,h(key)为散列函数,m为散列表表长,di为增量序列,可有下列三种取法:

    1)、di = 1,2,3,…,m-1,称线性探测再散列;

    2)、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2),称二次探测再散列;

    3)、di = 伪随机数序列,称伪随机探测再散列。

    (2)、再散列法

    hi = rhi(key)   i = 1,2,…,k

    rhi均是不同的散列函数。

    (3)、链地址法

    将所有关键字为同义词的数据元素存储在同一线性链表中。假设某散列函数产生的散列地址在区间[0,m-1]上,则设立一个指针型向量void *vec[m],其每个分量的初始状态都是空指针。凡散列地址为i的数据元素都插入到头指针为vec[i]的链表中。在链表中的插入位置可以在表头或表尾,也可以在表的中间,以保持同义词在同一线性链表中按关键字有序排列。

    (4)、建立一个公共溢出区


相关的C语言解释

hash.h
哈希表数据结构&&接口定义头文件

 

  #ifndef HASH_H 
  #define HASH_H 
   
  #define HASH_TABLE_INIT_SIZE 7 
   
  #define SUCCESS 1 
  #define FAILED 0 
   
   
  /** 
   * 哈希表槽的数据结构 
   */ 
  typedef struct Bucket { 
    char *key; 
    void *value; 
    struct Bucket *next; 
  } Bucket; 
   
  /** 
   * 哈希表数据结构 
   */ 
  typedef struct HashTable { 
    int size;  // 哈希表大小 
    int elem_num;  // 哈希表已经保存的数据元素个数 
    Bucket **buckets; 
  } HashTable; 
   
  int hashIndex(HashTable *ht, char *key); 
  int hashInit(HashTable *ht); 
  int hashLookup(HashTable *ht, char *key, void **result); 
  int hashInsert(HashTable *ht, char *key, void *value); 
  int hashRemove(HashTable *ht, char *key); 
  int hashDestory(HashTable *ht); 
  #endif 


hash.c
哈希表操作函数具体实现

  #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
  #include "hash.h" 
   
  /** 
   * 初始化哈希表 
   * 
   * T = O(1) 
   * 
   */ 
  int hashInit(HashTable *ht) 
  { 
    ht->size = HASH_TABLE_INIT_SIZE; 
    ht->elem_num = 0; 
    ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *)); 
   
    if (ht->buckets == NULL) 
      return FAILED; 
    else 
      return SUCCESS; 
  } 
   
  /** 
   * 散列函数 
   * 
   * T = O(n) 
   * 
   */ 
  int hashIndex(HashTable *ht, char *key) 
  { 
    int hash = 0; 
   
    while (*key != '\0') { 
      hash += (int)*key; 
      key ++; 
    } 
   
    return hash % ht->size; 
  } 
   
  /** 
   * 哈希查找函数 
   * 
   * T = O(n) 
   * 
   */ 
  int hashLookup(HashTable *ht, char *key, void **result) 
  { 
    int index = hashIndex(ht, key); 
   
    Bucket *bucket = ht->buckets[index]; 
   
    while (bucket) { 
      if (strcmp(bucket->key, key) == 0) { 
        *result = bucket->value; 
        return SUCCESS; 
      } 
      bucket = bucket->next; 
    } 
   
    return FAILED; 
  } 
   
   
  /** 
   * 哈希表插入操作 
   * 
   * T = O(1) 
   * 
   */ 
  int hashInsert(HashTable *ht, char *key, void *value) 
  { 
    int index = hashIndex(ht, key); 
   
    Bucket *org_bucket, *tmp_bucket; 
    org_bucket = tmp_bucket = ht->buckets[index]; 
   
    // 检查key是否已经存在于hash表中 
    while (tmp_bucket) { 
      if (strcmp(tmp_bucket->key, key) == 0) { 
        tmp_bucket->value = value; 
        return SUCCESS; 
      } 
      tmp_bucket = tmp_bucket->next; 
    } 
   
    Bucket *new = (Bucket *)malloc(sizeof(Bucket)); 
     
    if (new == NULL)  return FAILED; 
   
    new->key = key; 
    new->value = value; 
    new->next = NULL; 
   
    ht->elem_num += 1; 
   
    // 头插法 
    if (org_bucket) { 
      new->next = org_bucket; 
    } 
   
    ht->buckets[index] = new; 
   
    return SUCCESS;  
  } 
   
  /** 
   * 哈希删除函数 
   * 
   * T = O(n) 
   * 
   */ 
  int hashRemove(HashTable *ht, char *key) 
  { 
    int index = hashIndex(ht, key); 
   
    Bucket *pre, *cur, *post; 
   
    pre = NULL; 
    cur = ht->buckets[index]; 
   
    while (cur) { 
      if (strcmp(cur->key, key) == 0) { 
        post = cur->next; 
         
        if (pre == NULL) { 
          ht->buckets[index] = post; 
        } else { 
          pre->next = post; 
        } 
   
        free(cur); 
   
        return SUCCESS; 
      } 
   
      pre = cur; 
      cur = cur->next; 
    } 
   
    return FAILED; 
  } 
   
  /** 
   * 哈希表销毁函数 
   * 
   * T = O(n) 
   */ 
  int hashDestory(HashTable *ht) 
  { 
    int i; 
    Bucket *cur, *tmp; 
   
    cur = tmp = NULL; 
   
    for (i = 0; i < ht->size; i ++) { 
      cur = ht->buckets[i]; 
   
      while (cur) { 
        tmp = cur->next; 
        free(cur); 
        cur = tmp; 
      } 
    } 
   
    free(ht->buckets); 
   
    return SUCCESS; 
  } 


test.c
单元测试文件

  #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
  #include <assert.h> 
  #include "hash.h" 
   
  int main(int argc, char **argv) 
  { 
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable)); 
    int result = hashInit(ht); 
   
    assert(result == SUCCESS); 
   
    /* Data */ 
    int int1 = 10; 
    int int2 = 20; 
    char str1[] = "Hello World!"; 
    char str2[] = "Value"; 
    char str3[] = "Hello New World!"; 
   
    /* to find data container */ 
    int *j = NULL; 
    char *find_str = NULL; 
   
    /* Test Key Insert */ 
    printf("Key Insert:\n"); 
    hashInsert(ht, "FirInt", &int1); 
    hashInsert(ht, "FirStr", str1); 
    hashInsert(ht, "SecStr", str2); 
    printf("Pass Insert\n"); 
   
    /* Test Key Lookup*/ 
    printf("Key Lookup:\n"); 
    result = hashLookup(ht, "FirStr", &find_str); 
    assert(result == SUCCESS); 
    printf("pass lookup, the value is %s\n", find_str); 
   
    /* Test Update */ 
    printf("Key Update:\n"); 
    hashInsert(ht, "FirStr", str3); 
    result = hashLookup(ht, "FirStr", &find_str); 
    assert(result == SUCCESS); 
    printf("pass update, the value is %s\n", find_str); 
   
    return 0; 
  } 


编译方法

gcc -Wall -g -o main test.c hash.c

运行结果

201581194105153.png (590×141)

开放寻址法
在开放寻址法(open addressing)中,所有的元素都存放在散列表里。亦即,每个表项或包含动态集合的一个元素,或包含NIL。当查找一个元素时,要检查所有的表项,直到找到所需的元素,或者最终发现该元素不在表中。不像在链接法中,这没有链表,也没有元素存放在散列表外。在这种方法中,散列表可能会被填满,以致于不能插入任何新的元素,但装载因子a是绝对不会超过1的

线性探测法
第一次冲突移动1个单位,再次冲突时,移动2个,再次冲突,移动3个单位,依此类推

它的散列函数是:H(x) = (Hash(x) + F(i)) mod TableSize, 且F(0) = 0

举例(腾讯面试题目)

已知一个线性表(38, 25, 74, 63, 52, 48),假定采用散列函数 h(key) = key % 7 计算散列地址,并散列存储在散列表 A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均长度为 ?

下边模拟线性探测:

    38 % 7 == 3,  无冲突, ok
    25 % 7 == 4, 无冲突, ok
    74 % 7 == 4, 冲突, (4 + 1)% 7 == 5, 无冲突,ok
    63 % 7 == 0, 无冲突, ok
    52 % 7 == 3, 冲突, (3 + 1) % 7 == 4. 冲突, (4 + 1) % 7 == 5, 冲突, (5 + 1)%7 == 6,无冲突,ok
    48 % 7 == 6, 冲突, (6 + 1) % 7 == 0, 冲突,  (0 + 1) % 7 == 1,无冲突,ok


画图如下:

201581194134572.jpg (466×117)

平均查找长度 = (1 + 3 + 1 + 1 + 2 + 3) % 6 = 2

线性探测方法比较容易实现,但它却存在一个问题,称为一次群集(primary clustering).随着时间的推移,连续被占用的槽不断增加,平均查找时间也随着不断增加。集群现象很容易出现,这是因为当一个空槽前有i个满的槽时,该空槽为下一个将被占用的槽的概率是 (i + 1) / n.连续占用的槽的序列会变得越来越长,因而平均查找时间也会随之增加

平方探测
为了避免上面提到的一个群集的问题:第一次冲突时移动1(1的平方)个单位,再次冲突时,移动4(2的平方)个单位,还冲突,移动9个单位,依此类推。F(i) = i * i

加载全部内容

相关教程
猜你喜欢
用户评论