散列表(二):冲突处理的方法之链地址法的实现(哈希查找)

首先需要澄清的一点是,这里讲的是hash table/hash map ,即数据项所存储的表要用数组来实现。

一、链地址法

这种基本思想:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在

同义词链中进行。 

该散列方法首先对关键码集合用某一个散列函数计算它们的存放位置。

若设散列表地址空间的所有位置是从0到m-1,则关键码集合中的所有关键码被划分为m个子集,具有相同地址的关键码归于同一子集。我们称同一子集

中的关键码互为同义词。每一个子集称为一个桶。

通常各个桶中的表项通过一个链表链接起来,称之为同义词子表。所有桶号相同的表项都链接在同一个同义词子表中,各链表的表头结点

组成一个向量。

假设给出一组表项,它们的关键码为 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。采用的散列函数是:取其第一个字母在

字母表中的位置。 

hash (x) = ord (x) - ord (‘A’) 

这样,可得

hash (Burke) = 1hash (Ekers) = 4 hash (Broad) = 1hash (Blum) = 1 hash (Attlee) = 0hash (Hecht) = 7 hash (Alton) = 0hash (Ederly) = 4

1、通常,每个桶中的同义词子表都很短,设有n个关键码通过某一个散列函数,存放到散列表中的 m 个桶中。那么每一个桶中的同

义词子表的平均长度为 n / m。这样,以搜索平均长度为 n / m 的同义词子表代替了搜索长度为 n 的顺序表,搜索速度快得多(O(1))。

2、应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上,由于开地址法必须保持大量的空闲空间以确保搜索

效率,如二次探查法要求装填因子

,(a = n / m)而表项所占空间又比指针大得多,所以使用链地址法反而比开地址法节省存

储空间。

下面给出链地址法的实现,包括构造哈希表,释放哈希表,在哈希表中根据key查找一项,根据key 插入一项,根据key 删除一项等。链表节点用双向

链表实现。

common.h:

#ifndef _COMMON_H_
#define _COMMON_H_

#include <unistd.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>


#define ERR_EXIT(m) \
  do \
  { \
    perror(m); \
    exit(EXIT_FAILURE); \
  } \
  while (0)

#endif

hash_link.h:

#ifndef _HASH_LINK_H_
#define _HASH_LINK_H_
#include "common.h"

/* 给定关键码key,经过哈希函数计算得到的是关键码对应的数据项在数组中的存储下标index/bucket
 * 数据项所存储的表用数组实现,即hash table
 */

typedef struct hash hash_t;
typedef unsigned int (*hashfunc_t)(unsigned int, void *); // 第一个参数是桶的个数(地址范围),第二个参数是key值指针

hash_t *hash_alloc(unsigned int buckets, hashfunc_t hash_func); // 建立哈希表
void hash_free(hash_t *hash); // 释放哈希表
void *hash_lookup_entry(hash_t *hash, void *key, unsigned int key_size); //在哈希表中查找一项key
// 在哈希表中添加一条记录
void hash_add_entry(hash_t *hash, void *key, unsigned int key_size, void *value, unsigned int value_size);
void hash_free_entry(hash_t *hash, void *key, unsigned int key_size); // 在哈希表中删除一条记录


#endif

hash_link.c:

#include "hash_link.h"

typedef struct hash_node
{
    void *key; //无类型指针,故key可以是任意类型,value同
    void *value; // 有价值数据
    struct hash_node *prev; //前驱指针
    struct hash_node *next; // 后继指针
} hash_node_t;

struct hash
{
    unsigned int buckets; //桶的个数
    hashfunc_t hash_func; // 哈希函数
    hash_node_t **nodes; //指向哈希表数组的指针,数组放的是hash_node_t*
};


hash_node_t **hash_get_bucket(hash_t *hash, void *key);
hash_node_t *hash_get_node_by_key(hash_t *hash, void *key, unsigned int key_size);

hash_t *hash_alloc(unsigned int buckets, hashfunc_t hash_func)
{
    hash_t *hash = malloc(sizeof(hash_t));
    hash->buckets = buckets;
    hash->hash_func = hash_func;
    int size = buckets * sizeof(hash_node_t *); // 哈希表数组的大小
    hash->nodes = (hash_node_t **)malloc(size);
    memset(hash->nodes, 0, size); // 数组清0

    printf("The hash table has allocate.\n");

    return hash;

}

void hash_free(hash_t *hash)
{
    unsigned int buckets = hash->buckets;
    int i;
    for (i = 0; i < buckets; i++)
    {
        while (hash->nodes[i] != NULL)
        {
            hash_node_t *tmp = hash->nodes[i];
            hash->nodes[i] = tmp->next;
            if (tmp->next != NULL)  //也许只有一个节点
                tmp->next->prev = tmp->prev;
            free(tmp->value);
            free(tmp->key);
            free(tmp);
        }
    }

    free(hash->nodes);
    free(hash);
    printf("The hash table has free.\n");

}

void *hash_lookup_entry(hash_t *hash, void *key, unsigned int key_size)
{
    hash_node_t *node = hash_get_node_by_key(hash, key, key_size);
    if (node == NULL)
        return NULL;
    return node->value;
}


void hash_add_entry(hash_t *hash, void *key, unsigned int key_size, void *value, unsigned int value_size)
{
    if (hash_lookup_entry(hash, key, key_size))
    {
        // key 值已经存在,直接返回
        fprintf(stderr, "duplicate hash key\n");
        return ;
    }

    hash_node_t *node = malloc(sizeof(hash_node_t));
    node->prev = NULL;
    node->next = NULL;
    node->key = malloc(key_size);
    memcpy(node->key, key, key_size);
    node->value = malloc(value_size);
    memcpy(node->value, value, value_size);

    // 插入第一个结点
    hash_node_t **bucket = hash_get_bucket(hash, key);
    if (*bucket == NULL)
        *bucket = node;

    else   //将新结点插入链表头部
    {
        node->next = *bucket;
        (*bucket)->prev = node;
        *bucket = node;
    }
}


void hash_free_entry(hash_t *hash, void *key, unsigned int key_size)
{

    hash_node_t *node = hash_get_node_by_key(hash, key, key_size);
    if (node == NULL)
        return;

    free(node->key);
    free(node->value);

    // 双向链表的删除操作
    if (node->prev != NULL)
        node->prev->next = node->next;

    else
    {
        hash_node_t **bucket = hash_get_bucket(hash, key);
        *bucket = node->next;
    }

    if (node->next != NULL)
        node->next->prev = node->prev;

    free(node);
}


hash_node_t **hash_get_bucket(hash_t *hash, void *key)
{
    // 通过哈希函数返回地址
    unsigned int bucket = hash->hash_func(hash->buckets, key);
    if (bucket >= hash->buckets)
    {
        fprintf(stderr, "bad bucket lookup\n");
        exit(EXIT_FAILURE);
    }

    return &(hash->nodes[bucket]); //返回指向某个桶的指针

}


hash_node_t *hash_get_node_by_key(hash_t *hash, void *key, unsigned int key_size)
{
    hash_node_t **bucket = hash_get_bucket(hash, key);
    hash_node_t *node = *bucket;
    if (node == NULL)
    {
        return NULL;
    }

    while (node != NULL && memcmp(node->key, key, key_size) != 0)
    {
        // 通过链表头指针不断查询是否匹配
        node = node->next;
    }

    return node;
}

hash_link_main.c:

/*************************************************************************
    > File Name: hash_table_main.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Fri 22 Mar 2013 11:17:25 AM CST
 ************************************************************************/

#include "hash_link.h"

typedef struct stu
{

    char num[5];
    char name[32];
    int age;
} stu_t;

//使用学号来当作key进而产生hash index/bucket
//在这里学号是字符串,当然也可以将学号定义为int类型,此时要重新定义一个hash_int函数
unsigned int hash_str(unsigned int buckets, void *key)
{
    char *num = (char *)key;
    unsigned int index = 0;
    while (*num)
    {

        index = *num + 4 * index;
        num++;
    }

    return index % buckets;
}
//在这个例子中,key是学生学号,value是学生结构体
int main(void)
{
    stu_t stu_arr[] =
    {
        { "1234", "AAAA", 20 },
        { "6543", "BBBB", 23 },
        { "7657", "AAAA", 19 },
    };

    hash_t *hash = hash_alloc(256, hash_str);

    int size = sizeof(stu_arr) / sizeof(stu_arr[0]);
    int i;
    for (i = 0; i < size; i++)
    {

        hash_add_entry(hash, stu_arr[i].num, strlen(stu_arr[i].num),
                       &stu_arr[i], sizeof(stu_arr[i]));
    }

    stu_t *ptr = (stu_t *)hash_lookup_entry(hash, "6543", strlen("6543"));
    if (ptr)
        printf("%s %s %d\n", ptr->num, ptr->name, ptr->age);
    else
        printf("not found\n");


    hash_free_entry(hash, "1234", strlen("1234"));
    ptr = (stu_t *)hash_lookup_entry(hash, "1234", strlen("1234"));
    if (ptr)
        printf("%s %s %d\n", ptr->num, ptr->name, ptr->age);
    else
        printf("not found\n");

    hash_free(hash);

    return 0;
}

simba@ubuntu:~/Documents/code/struct_algorithm/search/hash_table/link_address$ ./hash_link_main 

The hash table has allocate. 6543 BBBB 23

not found

The hash table has free.

上述程序中key 是学号,使用key 产生哈希地址,即桶号,每个结点所带有的有价值数据value 是一个学生结构体。

哈希数组中每一项存放的是链表的头指针(如果存在,否则为NULL)。每个节点的key 和 value 成员都是指针,在

free整个节点之前,需要先free 两个指针。节点的另外两个成员是前驱和后继指针。实际上此时hash table也可以看作是hash map,pair就是{key, value}。如下图所示:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿凯的Excel

DataFrame的数据处理(Pandas读书笔记6)

本期和大家分享DataFrame数据的处理~ 一、提取想要的列 ? 第一种方法就是使用方法,略绕,使用.列名的方法可以提取对应的列! ? 第二张方法类似列表中提...

3495
来自专栏程序员互动联盟

【答疑解惑】C语言里面如何计算数据类型取值范围?

先看一个网友的问题: ? 初学者有不少会对数据类型的取值范围有疑问,数据类型的取值范围关系到定义合适的变量,尤其是在进行嵌入式开发时更要清楚。这里有必要介绍一下...

2516
来自专栏余林丰

2.比较排序之梳排序

  梳排序的知名度远没有其他排序算法那么高,它是在冒泡排序的基础上做的改进,引入类似“步长”以及“子序列”概念,这两个概念在后面的排序算法中会经常提及。   待...

1758
来自专栏性能与架构

算法中描述复杂度的大O是什么意思?

简介 算法是解决问题的方法,通常一个问题会有多种解决方法,就是有多种算法,那么我们如何决定哪个算法更好或者更高效呢? 为了描述一个算法的效率,就用到了这个大O,...

2915
来自专栏AI派

Numpy 修炼之道 (11)—— 掩码数组

有时候数据集中存在缺失、异常或者无效的数值,我们可以标记该元素为被屏蔽(无效)状态。

2524
来自专栏mathor

科学计算库Numpy

 genfromtxt函数里穿了三个参数,分别是 要打开的文档名称,分隔符,以什么类型存储  打印结果:

724
来自专栏小文博客

蓝桥杯C语言知识点补充——快速排序详解

1162
来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

3638
来自专栏数据结构与算法

Kosaraju算法详解

Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单: (1) 第一次对图G进行DFS遍历,并在...

3356
来自专栏简书专栏

基于Numpy的线性代数运算

numpy.matrix方法的参数可以为ndarray对象 numpy.matrix方法的参数也可以为字符串str,示例如下:

1003

扫码关注云+社区