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

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

相关文章

来自专栏博岩Java大讲堂

Java集合--非阻塞队列(ConcurrentLinkedQueue实现原理)

4847
来自专栏Janti

HashMap 学习心得

1.构造 HashMap 底层数据结构线性数组,HashMap有一个静态内部类Entry,Entry有四个属性,key,value,next,hash ? En...

3546
来自专栏来自地球男人的部落格

[LeetCode] 216. Combination Sum III

【原题】 Find all possible combinations of k numbers that add up to a number n, giv...

1936
来自专栏闵开慧

java概念2

1 文件操作 public class FileTest { public static void main(String[] args) throw...

3248
来自专栏用户2442861的专栏

异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

982
来自专栏一英里广度一英寸深度的学习

Leetcode 第一题 《两数之和》

711
来自专栏Java Edge

网易17校招编程笔试题Java解法赏析(更新至第9题)1 合唱团(动态规划)编程实现 3Fibonacci数列4数字反转5下厨房67喜欢的数字8买苹果9

4616
来自专栏有趣的Python

7-玩转数据结构-集合与映射

上一章我们详细的介绍了二分搜索树的底层实现。这章我们介绍两个高层的数据结构,集合和映射。这种高层的数据结构,更像是我们定义好了使用接口规则,但是具体的底层实现可...

1471
来自专栏各种机器学习基础算法

PHP SPL(PHP 标准库)

一、什么是spl库? SPL是用于解决典型问题(standard problems)的一组接口与类的集合。 此扩展只能在php 5.0以后使用,从PHP 5...

2786
来自专栏编程之旅

数据结构——链表(C语言实现)

提起链表,我们每个人都不会陌生,不管对数据结构的掌握如何,都或多或少的听过与用过链表这样的常见的数据结构。链表是线性表的一种,最基础的线性表,在插入与删除数据时...

883

扫码关注云+社区