详解散列表算法与其相关的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