散列表(三):冲突处理的方法之开地址法(线性探测再散列的实现)

二、开地址法

基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1仍然冲突,再以H0

为基础,产生另一个哈希地址H2 ,…,直到找出一个不冲突的哈希地址Hi ,将相应元素存入其中。这种方法有一个通用的再散列函

数形式: 

其中H0 为hash(key) ,m为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下四种:

线性探测再散列 二次探测再散列 伪随机探测再散列 双散列法

(一)、线性探测再散列

假设给出一组表项,它们的关键码为 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

又设散列表为HT[26],m = 26。采用线性探查法处理溢出,则上述关键码在散列表中散列位置如图所示。红色括号内的数字表示找

到空桶时的探测次数。比如轮到放置Blum 的时候,探测位置1,被占据,接着向下探测位置2还是不行,最后放置在位置3,总的探

测次数是3。

堆积现象

散列地址不同的结点争夺同一个后继散列地址的现象称为堆积(Clustering),比如ALton 本来位置是0,直到探测了6次才找到合适位

置5。这将造成不是同义词的结点也处在同一个探测序列中,从而增加了探测序列长度,即增加了查找时间。若散列函数不好、或装

填因子a 过大,都会使堆积现象加剧。

下面给出具体的实现代码,大体跟前面讲过的链地址法差异不大,只是利用的结构不同,如下:

status 保存状态,有EMPTY, DELETED, ACTIVE,删除的时候只是逻辑删除,即将状态置为DELETED,当插入新的key 时,只要不

是ACTIVE 的位置都是可以放入,如果是DELETED位置,需要将原来元素先释放free掉,再插入。

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.h:

#ifndef _HASH_H_
#define _HASH_H_

typedef struct hash hash_t;
typedef unsigned int (*hashfunc_t)(unsigned int, void *);

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);
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_H_ */

hash.c:

#include "hash.h"
#include "common.h"
#include <assert.h>


typedef enum entry_status
{
    EMPTY,
    ACTIVE,
    DELETED
} entry_status_t;

typedef struct hash_node
{
    enum entry_status status;
    void *key;
    void *value;
} hash_node_t;


struct hash
{
    unsigned int buckets;
    hashfunc_t hash_func;
    hash_node_t *nodes;
};

unsigned int 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 = (hash_t *)malloc(sizeof(hash_t));
    //assert(hash != NULL);
    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);
    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++)
    {
        if (hash->nodes[i].status != EMPTY)
        {
            free(hash->nodes[i].key);
            free(hash->nodes[i].value);
        }
    }

    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))
    {
        fprintf(stderr, "duplicate hash key\n");
        return;
    }

    unsigned int bucket = hash_get_bucket(hash, key);
    unsigned int i = bucket;
    // 找到的位置已经有人存活,向下探测
    while (hash->nodes[i].status == ACTIVE)
    {
        i = (i + 1) % hash->buckets;
        if (i == bucket)
        {
            // 没找到,并且表满
            return;
        }
    }

    hash->nodes[i].status = ACTIVE;
    if (hash->nodes[i].key) //释放原来被逻辑删除的项的内存
    {
        free(hash->nodes[i].key);
    }
    hash->nodes[i].key = malloc(key_size);
    memcpy(hash->nodes[i].key, key, key_size);
    if (hash->nodes[i].value) //释放原来被逻辑删除的项的内存
    {
        free(hash->nodes[i].value);
    }
    hash->nodes[i].value = malloc(value_size);
    memcpy(hash->nodes[i].value, value, value_size);

}

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;

    // 逻辑删除,置标志位
    node->status = DELETED;
}

unsigned int 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 bucket;
}

hash_node_t *hash_get_node_by_key(hash_t *hash, void *key, unsigned int key_size)
{
    unsigned int bucket = hash_get_bucket(hash, key);
    unsigned int i = bucket;
    while (hash->nodes[i].status != EMPTY && memcmp(key, hash->nodes[i].key, key_size) != 0)
    {
        i = (i + 1) % hash->buckets;
        if (i == bucket)        // 探测了一圈
        {
            // 没找到,并且表满
            return NULL;
        }
    }
    // 比对正确,还得确认是否还存活
    if (hash->nodes[i].status == ACTIVE)
    {
        return &(hash->nodes[i]);
    }

    // 如果运行到这里,说明i为空位或已被删除

    return NULL;
}

main.c:

#include "hash.h"
#include "common.h"

typedef struct stu
{
    char sno[5];
    char name[32];
    int age;
} stu_t;

typedef struct stu2
{
    int sno;
    char name[32];
    int age;
} stu2_t;


unsigned int hash_str(unsigned int buckets, void *key)
{
    char *sno = (char *)key;
    unsigned int index = 0;

    while (*sno)
    {
        index = *sno + 4 * index;
        sno++;
    }

    return index % buckets;
}

unsigned int hash_int(unsigned int buckets, void *key)
{
    int *sno = (int *)key;
    return (*sno) % buckets;
}

int main(void)
{

    stu2_t stu_arr[] =
    {
        { 1234, "AAAA", 20 },
        { 4568, "BBBB", 23 },
        { 6729, "AAAA", 19 }
    };

    hash_t *hash = hash_alloc(256, hash_int);

    int size = sizeof(stu_arr) / sizeof(stu_arr[0]);
    int i;
    for (i = 0; i < size; i++)
    {
        hash_add_entry(hash, &(stu_arr[i].sno), sizeof(stu_arr[i].sno),
                       &stu_arr[i], sizeof(stu_arr[i]));
    }

    int sno = 4568;
    stu2_t *s = (stu2_t *)hash_lookup_entry(hash, &sno, sizeof(sno));
    if (s)
    {
        printf("%d %s %d\n", s->sno, s->name, s->age);
    }
    else
    {
        printf("not found\n");
    }

    sno = 1234;
    hash_free_entry(hash, &sno, sizeof(sno));
    s = (stu2_t *)hash_lookup_entry(hash, &sno, sizeof(sno));
    if (s)
    {
        printf("%d %s %d\n", s->sno, s->name, s->age);
    }
    else
    {
        printf("not found\n");
    }

    hash_free(hash);

    return 0;
}

simba@ubuntu:~/Documents/code/struct_algorithm/search/hash_table/linear_probing$ ./main  The hash table has allocate. 4568 BBBB 23 not found The hash table has free.

链地址法 示例还有一点不同,就是key 使用的是int 类型,所以必须再实现一个hash_int 哈希函数,根据key 产生哈希地址。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏美团技术团队

美团点评SQL优化工具SQLAdvisor开源

介绍 在数据库运维过程中,优化 SQL 是 DBA 团队的日常任务。例行 SQL 优化,不仅可以提升程序性能,还能够降低线上故障的概率。 目前常用的 SQL 优...

3176
来自专栏PHP技术

MongoDB数据结构设计中6条重要的经验法则

很多初学者认为在MongoDB中针对一对多建模唯一的方案就是在父文档中内嵌一个数组子文档,但是这是不准确的。因为你可以在MongoDB内嵌一个文档不代表你就必须...

2847
来自专栏沃趣科技

ASM 翻译系列第三十九弹:物理元数据AT表

原作者:Bane Radulovic 译者: 魏兴华 审核: 魏兴华 DBGeeK联合出品 原文链接:http://asmsupportguy.bl...

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

洛谷P1337 [JSOI2004]平衡点 / 吊打XXX(模拟退火)

1140
来自专栏枕边书

小时到分钟 - 一步步优化巨量关键词的匹配

问题由来 前些天工作中遇到一个问题: 有 60万 条短消息记录日志,每条约 50 字,5万 关键词,长度 2-8 字,绝大部分为中文。要求将这 60万 条记录中...

1726
来自专栏数据库新发现

Statspack报告主要参数指标简要说明

全文链接:         http://www.eygle.com/more/statspack_list.htm

681
来自专栏开发与安全

散列表(四):冲突处理的方法之开地址法(二次探测再散列的实现)

前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列 (二)、二次探测再散列 为改善“堆积”问题,减少为完成搜索所需...

1890
来自专栏大数据架构

Spark SQL / Catalyst 内部原理 与 RBO

从上图可见,无论是直接使用 SQL 语句还是使用 DataFrame,都会经过如下步骤转换成 DAG 对 RDD 的操作

1126
来自专栏祝威廉

CarbonData实践(一)

CarbonData 拥有不错的明细查询能力,比如简单的where条件过滤,性能大概是Parquet的20倍。数据的聚合分析方面,如果有不错的where过滤,则...

1035
来自专栏数据和云

Oracle 12.2 的连接消除特性

编辑手记:在12.1及以前的版本中,当祖父,父,子表之间有明显的主键和引用完整性约束,只有加入的主键是单个列键时,才能进行连接消除; 但在12.2多列主键也允许...

3406

扫码关注云+社区