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

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

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

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

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

     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

运行结果

开放寻址法
在开放寻址法(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

画图如下:

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

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

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

(0)

相关推荐

  • 算法学习入门之使用C语言实现各大基本的排序算法

    首先来看一下排序算法的一些相关概念: 1.稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的.反之,就是非稳定的. 比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面.假如变成a1,a4,a2,a3,a5就不是稳定的了. 2.内排序和外排序 在排序过程中,所有需要排序的数都在内存,

  • C语言字符串快速压缩算法代码

    通过键盘输入一串小写字母(a~z)组成的字符串. 请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串. 压缩规则: 1.仅压缩连续重复出现的字符.比如字符串"abcbc"由于无连续重复字符,压缩后的字符串还是"abcbc". 2.压缩字段的格式为"字符重复的次数+字符".例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz". 示例 输入:"cccddec

  • 字符串的组合算法问题的C语言实现攻略

    基本字符串组合问题 题目:输入一个字符串,输出该字符串中字符的所有组合.举个例子,如果输入abc,它的组合有a.b.c.ab.ac.bc.abc. 上面我们详细讨论了如何用递归的思路求字符串的排列.同样,本题也可以用递归的思路来求字符串的组合. 假设我们想在长度为n的字符串中求m个字符的组合.我们先从头扫描字符串的第一个字符.针对第一个字符,我们有两种选择:第一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符:第二是不把这个字符放到组合中去,接下来我们需要在剩下的n

  • 贪心算法的C语言实现与运用详解

    贪心算法 所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解.贪心算法的基本思路如下: 1.建立数学模型来描述问题. 2.把求解的问题分成若干个子问题. 3.对每一子问题求解,得到子问题的局部最优解. 4.把子问题的解局部最优解合成原来解问题的一个解. 实现该算法的过程: 从问题的某一初始解出发:

  • C语言经典算法例题求100-999之间的“水仙花数

    题目:打印出所有的 "水仙花数 ",所谓 "水仙花数 "是指一个三位数,其各位数字立方和等于该数本身. 例如:153是一个 "水仙花数 ",因为153=1的三次方+5的三次方+3的三次方. 实现代码如下 #include <iostream> #include <Cmath> using namespace std; /* 求100-999之间的水仙花数 */ int main() { int number,hun,ten

  • 用C语言举例讲解数据结构中的算法复杂度结与顺序表

    数据结构算法复杂度 1.影响算法效率的主要因素 (1)算法采用的策略和方法: (2)问题的输入规模: (3)编译器所产生的代码: (4)计算机执行速度. 2.时间复杂度 // 时间复杂度:2n + 5 long sum1(int n) { long ret = 0; \\1 int* array = (int*)malloc(n * sizeof(int)); \\1 int i = 0; \\1 for(i=0; i<n; i++) \\n { array[i] = i + 1; } for(

  • C语言中压缩字符串的简单算法小结

    应用中,经常需要将字符串压缩成一个整数,即字符串散列.比如下面这些问题: (1)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节.请找出最热门的10个检索串. (2)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M.返回频数最高的100个词. (3)有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复.要求你按照query的频度排序. (4)给定a.b两个文件

  • C语言字符串原地压缩实现方法

    本文实例讲述了C语言字符串原地压缩的实现方法,对于学习字符串操作的算法设计有不错的借鉴价值.分享给大家供大家参考.具体方法如下: 字符串原地压缩示例: "eeeeeaaaff"压缩为"e5a3f2" 具体功能代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <

  • C语言的冒泡排序和快速排序算法使用实例

    冒泡排序法 题目描述: 用一维数组存储学号和成绩,然后,按成绩排序输出. 输入: 输入第一行包括一个整数N(1<=N<=100),代表学生的个数.     接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩. 输出: 按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来.     如果学生的成绩相同,则按照学号的大小进行从小到大排序. 样例输入: 3     1 90     2 87     3 92 样例输出: 2 87     1 90     3 92 代码: #

  • 详解约瑟夫环问题及其相关的C语言算法实现

    约瑟夫环问题 N个人围成一圈顺序编号,从1号开始按1.2.3......顺序报数,报p者退出圈外,其余的人再从1.2.3开始报数,报p的人再退出圈外,以此类推.   请按退出顺序输出每个退出人的原序号 算法思想 用数学归纳法递推. 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),若nm非常大,无法在短时间内计算出结果.我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程.因此如果要追求效率,就要打破常规,实

随机推荐