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

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

(二)、二次探测再散列

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

通过某一个散列函数对表项的关键码 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 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

下载TCGA所有癌症的maf文件做signature分析

才sanger研究所已经做好了这个分析,但是值得我们重复一下,效果如下: ? TCGA所有癌症的mutation signature 首先TCGA所有癌症的ma...

55912
来自专栏wym

Educational Codeforces Round 44 (Rated for Div. 2) B. Switches and Lamps

You are given n switches and m lamps. The i-th switch turns on some subset of th...

782
来自专栏移动开发面面观

ProgressiveJpeg介绍与在Android中的使用

1734
来自专栏技术博客

一步一步学Linq to sql(八):继承与关系

1.首先定义的是Topic实体基类,然后两个子类的继承,NewTopic--主题帖,Reply--回复帖。 2.Topic类上的特性,下面先来看一下特性类

941
来自专栏吴小龙同學

android之获取手机信息

android获取手机信息(号码,内存,CPU,分辨率,MAC,IP,SD卡,IMEI,经纬度,信号强度等等) 1 2 3 4 5 6 7 8 9 10 11 ...

3927
来自专栏安恒网络空间安全讲武堂

ecshop3.X 命令执行漏洞分析

刷漏洞信息的时候看到有师傅分析了2.7最新版的命令执行,然后先知有师傅说3.x也有,但是要绕waf,于是弄来了3.6的源码进行复现。

5822
来自专栏ml

HDUOJ-------2149Public Sale

Public Sale Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

2758
来自专栏数据之美

关于 xargs 参数被截断,tar 文件被覆盖的问题

问题: 目录下共 2W+ 个小文件: $ find . -type f | wc -l   20083   如果我们这样打包,会爆出 "Arg...

1986
来自专栏wannshan(javaer,RPC)

ConcurrentHashMap 锁分段 源码分析

看ConcurrentHashMap下几个属性: /** * The default concurrency level for this table...

3506
来自专栏数据分析

使用Visual Studio 2010 一步一步创建Powershell Module 和 Cmdlet

之前写了一个C# 调用PowerShell方法, 那么怎么反过来操作呢,也就是怎么样用C#写一个powershell命令呢? 现在就用C#写一个超级简单的Mod...

3949

扫码关注云+社区