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

前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列

(二)、二次探测再散列

为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。

通过某一个散列函数对表项的关键码 x 进行计算,得到桶号,它是一个非负整数。 

若设表的长度为TableSize = 23,则在线性探测再散列 举的例子中利用二次探查法所得到的散列结果如图所示。

比如轮到放置Blum 的时候,本来应该是位置1,已经被Burke 占据,接着探测 H0 + 1 = 2,,发现被Broad 占据,接着探测 H0 - 1 = 

0,发现空位于是放进去,探测次数为3。

下面来看具体代码实现,跟前面讲过的线性探测再散列 差不多,只是探测的方法不同,但使用的数据结构也有点不一样,此外还实

现了开裂,如果装载因子 a > 1/2; 则建立新表,将旧表内容拷贝过去,所以hash_t 结构体需要再保存一个size 成员,同样的原因,

为了将旧表内容拷贝过去,hash_node_t 结构体需要再保存 *key 和 *value 的size。

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;
    unsigned int key_size; //在拷贝进新的哈希表时有用
    void *value;
    unsigned int value_size; //在拷贝进新的哈希表时有用
} hash_node_t;


struct hash
{
    unsigned int buckets;
    unsigned int size; //累加,如果size > buckets / 2 ,则需要开裂建立新表
    hashfunc_t hash_func;
    hash_node_t *nodes;
};

unsigned int next_prime(unsigned int n);
int is_prime(unsigned int n);

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);

    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;
    unsigned int j = i;
    int k  = 1;
    int odd = 1;

    while (hash->nodes[i].status == ACTIVE)
    {
        if (odd)
        {
            i = j + k * k;

            odd = 0;

            // i % hash->buckets;
            while (i >= hash->buckets)
            {
                i -= hash->buckets;
            }
        }
        else
        {
            i = j - k * k;
            odd = 1;

            while (i < 0)
            {
                i += hash->buckets;
            }

            ++k;
        }
    }

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

    if (++(hash->size) < hash->buckets / 2)
        return;


    //在搜索时可以不考虑表装满的情况;
    //但在插入时必须确保表的装填因子不超过0.5。
    //如果超出,必须将表长度扩充一倍,进行表的分裂。

    unsigned int old_buckets = hash->buckets;

    hash->buckets = next_prime(2 * old_buckets);

    hash_node_t *p = hash->nodes;
    unsigned int size;
    hash->size = 0;  //从0 开始计算
    size = sizeof(hash_node_t) * hash->buckets;
    hash->nodes = (hash_node_t *)malloc(size);
    memset(hash->nodes, 0, size);

    for (i = 0; i < old_buckets; i++)
    {
        if (p[i].status == ACTIVE)
        {
            hash_add_entry(hash, p[i].key, p[i].key_size, p[i].value, p[i].value_size);
        }
    }

    for (i = 0; i < old_buckets; i++)
    {
// active or deleted
        if (p[i].key)
        {
            free(p[i].key);
        }
        if (p[i].value)
        {
            free(p[i].value);
        }
    }

    free(p); //释放旧表

}

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 = 1;
    unsigned int pos = bucket;
    int odd = 1;
    unsigned int tmp = pos;
    while (hash->nodes[pos].status != EMPTY && memcmp(key, hash->nodes[pos].key, key_size) != 0)
    {
        if (odd)
        {
            pos = tmp + i * i;

            odd = 0;

            // pos % hash->buckets;
            while (pos >= hash->buckets)
            {
                pos -= hash->buckets;
            }
        }
        else
        {
            pos = tmp - i * i;
            odd = 1;

            while (pos < 0)
            {
                pos += hash->buckets;
            }

            i++;
        }

    }

    if (hash->nodes[pos].status == ACTIVE)
    {
        return &(hash->nodes[pos]);
    }

    // 如果运行到这里,说明pos为空位或者被逻辑删除

    // 可以证明,当表的长度hash->buckets为质数且表的装填因子不超过0.5时,
    // 新的表项 x 一定能够插入,而且任何一个位置不会被探查两次。
    // 因此,只要表中至少有一半空的,就不会有表满问题。

    return NULL;
}

unsigned int next_prime(unsigned int n)
{
    // 偶数不是质数
    if (n % 2 == 0)
    {
        n++;
    }

    for (; !is_prime(n); n += 2); // 不是质数,继续求
    return n;
}

int is_prime(unsigned int n)
{
    unsigned int i;
    for (i = 3; i * i <= n; i += 2)
    {
        if (n % i == 0)
        {
            // 不是,返回0
            return 0;
        }
    }

    // 是,返回1
    return 1;
}

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/quardratic_probing$ ./main  The hash table has allocate. 4568 BBBB 23 not found The hash table has free.

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

萌新刷题(十一)有效数字

题目 给定一个字符串,验证其是否为数字。 样例 "0" => true " 0.1 " => true "abc" => false "1 a" => ...

3287
来自专栏Python小屋

1000道Python题库系列分享15(1道代码改写题)

考虑到前面分享题库的时候,要等下一期才给出答案,不方便大家及时核对和学习。以后改为每期在文末直接给出答案,不明白的地方可以文末留言交流,提高学习效率。

665
来自专栏灯塔大数据

每周学点大数据 | No.43 相似连接的可扩展性

No.43期 相似连接的可扩展性 小可:那么具体是怎么做的呢? Mr. 王:我们先来看看求单元函数值是如何在 MapReduce 上实现的吧。 ? 图中有三...

3387
来自专栏PingCAP的专栏

SuRF: 一个优化的 Fast Succinct Tries

在前一篇文章中,我简单介绍了 Succinct Data Structure,这里我们继续介绍 SuRF。

2175
来自专栏Albert陈凯

MapReduce编程思想通俗理解

综述 Map(映射)与Reduce(化简)来源于LISP和其他函数式编程语言中的古老的映射和化简操作,MapReduce操作数据的最小单位是一个键值对。用户在使...

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

【答疑解惑第三十八讲】初学者做项目需要掌握哪些东西?

疑惑一 【答疑解惑】初学必须掌握的数据结构有哪些? 数据结构有很多,难以程度也不相同,初学者应该掌握哪些基本的数据结构呢?作为一个过来人,我觉得作为一个初学者应...

3408
来自专栏从流域到海域

How to Save an ARIMA Time Series Forecasting Model in Python (如何在Python中保存ARIMA时间序列预测模型)

How to Save an ARIMA Time Series Forecasting Model in Python 原文作者:Jason Brownlee...

25210
来自专栏GreenLeaves

SQL学习之汇总数据之聚集函数

一、 1、我们经常需要汇总数据而不用把他们实际检索出来,为此SQL提供了专门的函数,以便于分析数据和报表生成,这些函数的功能有: (1)确定表中行数(或者满足单...

1895
来自专栏岑玉海

hbase源码系列(一)Balancer 负载均衡

  看源码很久了,终于开始动手写博客了,为什么是先写负载均衡呢,因为一个室友入职新公司了,然后他们遇到这方面的问题,某些机器的硬盘使用明显比别的机器要多,每次用...

2978
来自专栏腾讯技术工程官方号的专栏

最强大脑,计算机中1+1=2的实现逻辑

在计算机硬件层面上,你知道1+1是如何实现的吗?本文先介绍了继电器的基本原理,然后从分析与或非等逻辑门电路入手,推导出异或门的实现,借助异或门从而实现1+1,并...

1.2K6

扫码关注云+社区