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

首先需要澄清的一点是,这里讲的是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 条评论
登录 后参与评论

相关文章

来自专栏wannshan(javaer,RPC)

dubbo序列化过程源码分析

先看下dubbo在serialize层的类设计方案 序列化方案的入口,是接口Serialization的实现类。 /** * Serialization. ...

6889
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

3128
来自专栏芋道源码1024

数据库中间件 Sharding-JDBC 源码分析 —— 结果归并

本文主要基于 Sharding-JDBC 1.5.0 正式版 1. 概述 2. MergeEngine 2.2.1 AbstractStreamResultSe...

3418
来自专栏三丰SanFeng

算法学堂 - 二分查找及其变形

C语言中可以用bsearch()实现二分查找。同qsort()一样,bsearch()也包含在glibc库中,且同样要自定义比较函数。其原型如下: void *...

2036
来自专栏chenssy

【死磕 Spring】—– IOC 之构造函数实例化 bean

createBeanInstance() 用于实例化 bean,它会根据不同情况选择不同的实例化策略来完成 bean 的初始化,主要包括:

974
来自专栏王硕

原 pg查询树的简单解读

35213
来自专栏深度学习计算机视觉

蓝桥杯试题算法学习笔记一题目

题目 1、熊怪吃核桃 森林里有一只熊怪,很爱吃核桃。不过它有个习惯,每次都把找到的核桃分成相等的两份,吃掉一份,留一份。如果不能等分,熊怪就会扔掉一个核桃再分。...

4696
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(2)《Kotlin极简教程》正式上架:

在上面的代码中,我们通过向注解类添加元注解(meta-annotation)的方法来指定其他属性:

1272
来自专栏coding...

C语言基础 - 实现单向链表

1323
来自专栏Code_iOS

数据结构:链表

工程代码 Github: Data_Structures_C_Implemention -- Link List

1201

扫码关注云+社区