精华内容
下载资源
问答
  • 哈希冲突详解、拉链法、开地址法

    万次阅读 2015-10-29 23:33:12
    哈希冲突详解 我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。 什么是哈希冲突?比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。... 方法2:开地址法何为拉链法

    哈希冲突详解


    我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。


    1. 什么是哈希冲突?

    比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。这就是生活中实实在在的冲突问题。

    同样的当数据插入到哈希表时,不同key值产生的h(key)却是相等的,这个时候就产生了冲突。这个时候就要解决这个问题。

    • 怎么解决哈希冲突?

      方法1:拉链法
      方法2:开地址法

    • 何为拉链法?

      拉链法是解决哈希冲突的一种行之有效的方法,某些哈希地址可以被多个关键字值共享,这样可以针对每个哈希地址建立一个单链表。

      在拉链(单链表)的哈希表中搜索一个记录是容易的,首先计算哈希地址,然后搜索该地址的单链表。

      在插入时应保证表中不含有与该关键字值相同的记录,然后按在有序表中插入一个记录的方法进行。针对关键字值相同的情况,现行的处理方法是更新该关键字值中的内容。

      删除关键字值为k的记录,应先在该关键字值的哈希地址处的单链表中找到该记录,然后删除之。

    • 什么是开地址法?

      首先该方法并不建立链表。哈希表由M个元素组成,其地址从0到M-1。我们通过从空表开始,逐个向表中插入新记录的方式建立散列表。
      插入关键字值为key的新纪录的方法是:
      从h(key)开始,按照某种规定的次序探查插入新记录的空位置。h(key)被称为基位置。如果h(key)已经被占用,那么需要用一种解决冲突的策略来确定如何探查下一个空位置,所以这种方法又称为空缺编址法
      根据不同的解决冲突的策略,可以产生不同的需要被检查的位置序列,称为 探查序列
      根据生成的探查序列的不同规则,可以有 线性探查法伪随机探查法二次探查法双散列法等开址方法。

    • 线性探查法详解

      缺点:线性探查法在情况不好的时候导致许多记录在散列表中连成一片,从而使探查次数增加,影响搜索效率。这种现象称为基本聚集

      线性探查法是一种简单的开地址方法,它使用下列循环探查序列:

      h(key),h(key)+1,...,M-1,0,...,h(key)-1

      从基位h(key)开始探查该位置是否被占用,即是否为空位置
      如果被占用,则继续探查位置h(key)+1,若该位置也已占用,再根据探查序列中的规定继续检查下一个位置。
      因此,探查序列为:

      h(i) = (h(x)+i) % M (i=0,1,2,...,M-1)
    • 伪随机法详解

      伪随机法是为了消除线性探查的基本聚集而提出来的方法。其基本思想是建立一个伪随机数发生器。当发生冲突时,就利用伪随机数发生器计算下一个探查位置。伪随机数发生器有不同的构造。

      一个比较简单的伪随机数产生方法:

         
         y(0) = h(key)
         y(i+1) = (y(i)+p) % M  (i=0,1,2,...)
      式中,y(0)为伪随机数发生器的初值,M为哈希表的长度,
      P为与M接近的素数。
      
    • 二次探查法详解

      二次探查法也能够消除基本聚集,虽然伪随机数法和二次探查法都能够消除基本聚集。但是如果两个关键字值有相同的基本位置,那么它们就会有相同的探查序列。这是因为伪随机数法和二次探查产生的探查序列是基位置的函数,而不是原来关键字的函数,因此由产生了二次聚集的问题。

    • 双散列法详解

      使用双散列方法可以避免二级聚集。双散列法使用两个散列函数,第一个散列函数计算探针序列的起始值,第二个散列函数计算下一个位置的探查步长。

    展开全文
  • 哈希表之开地址法解决冲突

    千次阅读 2016-01-23 13:20:41
    这里我们介绍另一种方式:开地址法解决冲突。 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1仍然冲突,再以H0 为基础,产生另一个哈希地址H2 ,…,直到...

    在上一篇博文中,我们讲述了使用链地址法解决冲突的方法。这里我们介绍另一种方式:开地址法解决冲突。

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

    为基础,产生另一个哈希地址H2 ,…,直到找出一个不冲突的哈希地址Hi ,将相应元素存入其中。根据增量序列的取值方式不同,相应的再散列方式也不同。主要有以下四种


    线性探测再散列

    二次探测再散列

    伪随机探测再散列

    双散列法


    (一)线性探测再散列


    理解起来很简单,就是如果使用哈希函数映射的位置已经有数据,那么就依次顺序的向后查找,直到有一个位置还没有数据,将其放入。或者表已经满了。注意:表元素个数/表长<=1是基本要求(也就是 装填因子 )。

    堆积现象

    定义:用线性探测法处理冲突时,当表中i,i+1,i+2个位置上都有数据时,下一个散列地址如果是i,i+1,i+2和i+3都会要求填入i+3的位置,多个第一个散列地址不同的记录争夺同一个后继散列地址。

    若散列函数不好、或装填因子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;
    }
    输出:

    The hash table has allocate.
    4568 BBBB 23
    not found
    The hash table has free.
    (二)二次探测再散列

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

    可以证明:当表的长度>buckets为质数并且表的装填因子不超过0.5的时候,新的表项一定可以插入,而且任意一个位置不会被探查两次。

    具体代码实现,跟前面讲过的线性探测再散列 差不多,只是探测的方法不同,但使用的数据结构也有点不一样。此外还实现了开裂处理(也就是表的长度要扩充一倍,然后取比他大的最小的一个质数),如果装载因子 a > 1/2; 则建立新表,将旧表内容拷贝过去,所以hash_t 结构体需要再保存一个size 成员,同样的原因,为了将旧表内容拷贝过去,hash_node_t 结构体需要再保存 *key 和 *value 的size。

    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;
    }
    (三)伪随机探测再散列


    (四)双散列法


    下面是一定数据下各种方式的性能分析:


    我们可以得出一般性结论:

    处理冲突的方法最好采用链地址法,哈希函数使用除留余数法(其中哈希函数最好与关键码的特征关联性强一些)性能最佳。

    展开全文
  • 散列函数之冲突处理之开地址法

    千次阅读 2014-11-18 22:26:57
    二、开地址法 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1仍然冲突,再以H0 为基础,产生另一个哈希地址H2 ,…,直到找出一个不冲突的哈希地址Hi ...

    开地址法

    基本思想:当关键码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掉,再插入。


    二次探测再散列

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

    通过某一个散列函数对表项的关键码 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。


    转自:http://blog.csdn.net/jnu_simba/article/details/9668369


    展开全文
  • 一、开地址法 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1仍然冲突,再以H0 为基础,产生另一个哈希地址H2 ,…,直到找出一个不冲突的哈希地址Hi ,将...

    二、开地址法

    基本思想:当关键码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:

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #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:

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #ifndef _HASH_H_
    #define _HASH_H_

    typedef  struct hash hash_t;
    typedef  unsigned  int (*hashfunc_t)( unsigned  intvoid *);

    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:

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    #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:

     C++ Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    #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 产生哈希地址。


    展开全文
  • 前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列 (二)、二次探测再散列 为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。 ...
  • Open Hash Tables (Closed Addressing)(拉链) 优点: (1)拉链处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; (2)由于拉链中各链表上的结点空间是动态申请的,故它更适合于...
  • 开放地址法

    千次阅读 2019-05-03 15:28:02
    哈希表在压缩可选值后仍有冲突的可能,比如1和101,二者最后的取余仍为1,会导致冲突,解决这种冲突的一种方法就是开放地址法。 开放地址法:当冲突法生时,通过查找数组的一个空位,并将数据填入,而不再用哈希...
  • 下面我们来测试一下,可以看到,依然达到了效果,说明我们模拟的链地址法也生效了, 以上就是通过开发地址法和链地址法解决hash冲突的两种方式,希望对大家理解hashMap的底层原理有所帮助…感谢观看!
  • 哈希表的散列(拉链

    千次阅读 2018-03-01 21:56:28
    散列法又叫链地址法(链法)。 散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在...
  • 一、链地址法在等概率下查找成功和查找不成功的平均查找长度:将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功...
  • 1 开放地址法  这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:  H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,...
  • 给web服务器配置静态IP地址 WEB服务器的安装 1、打开服务管理器,点击“角色”,点击“添加角色” 2、点击“下一步” 3、勾选“WEB服务器(IIS)”,点击“下一步” 4、点击“下一步” 5、点击“下一步”(如果...
  • 基本定义散列技术是在记录的存储位置和它的关键字之间建立一个确定的...关键字对应的存储位置称为散列地址。散列技术最适合的求解问题是查找与给定值相等的记录。 如果碰到两个不同的关键字key1≠key2key_1 \neq key
  • Hash冲突之开放地址法

    万次阅读 2020-07-29 07:30:09
    所谓开放地址法就是发生冲突时在散列表(也就是数组里)里去寻找合适的位置存取对应的元素。 一、线性探测法 若当前位置冲突了,就去找相邻的下一个位置。 就拿放入元素举例吧,当你放入<a,101>到下标为2的...
  • 哈希表---解决哈希冲突

    千次阅读 2016-11-19 10:17:17
    上篇文章已经写过构造哈希表时用开放定址解决哈希冲突,这次我就来写写这个解决哈希冲突的问题! 一、结点定义 我们已经知道大概是一种什么结构了,(如果不知道,这里有讲哦点我点我)显而易见...
  • 哈希表(链地址法

    千次阅读 2018-10-26 11:31:57
    我前面说过哈希表的开放定址法,现在说说链地址法又称散列法,在利用毕散列时我们说到有哈希冲突,而散列法正好避开了哈希冲突,每个下标所在位置就是桶口,每个桶可以看做是一个链表,我们把哈希冲突的元素放在...
  • 构造哈希表之(哈希桶)

    千次阅读 2016-06-08 09:50:09
    上一篇博客中介绍了用闭散列的二次探测和构造哈希表的原理即实现方式。 构造哈希表的闭散列之二次探测地址:http://blog.csdn.net/xyzbaihaiping/article/details/51607770 这里简单描述一下哈希桶的...
  • (1)拉链处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; (2)由于拉链中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; (3)开放定址为减少冲突...
  • 哈希表-开放地址法之线性探测

    千次阅读 2017-12-19 21:34:57
    哈希表-开放地址法之线性探测
  • 一、链地址法 这种基本思想:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存在哈希表的第i个单元中,因而查找、 插入和删除主要在同义词链中进行。  该散列方法首先对关键码集合用某一...
  • 散列法,又叫链地址法 散列法:首先对关键码集合用散列函数计算出散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个无头结点的单链表连接起来,各链表的头结点...
  • C++链地址法实现哈希表

    千次阅读 2014-05-14 21:36:15
    哈希表,也叫散列表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个...冲突处理的方法主要有开放定址法和链地址法。本文主要实现了一个基本存放字符串的哈希表,冲
  • 地址法的基本思想是:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。  该散列方法首先对关键码集合用某一个...
  •  * 用开放地址法中的线性探查法解决冲突实现哈希表的运算。  */ public class MyHashSearch {  public static final int SIZE = 10;  public static final int NULLKEY = -1;  public sta
  • 算法与数据结构的一个题目,用链地址法和开放定址法,求等概率情况下查找成功时的平均查找长度 已知一组关键字(13,20,85,52,8),哈希函数为:H(key)=key MOD 6 1)用开放定址法处理冲突,选用线性探测再散列处理冲突...
  • Hash地址冲突解决之开放定址

    千次阅读 2019-05-28 22:48:04
    原文地址:《Hash地址冲突解决之开放定址》 1、什么是hash冲突 hash函数也被称为散列函数,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是散列值。 这种转换是一种压缩映射,散列值的空间...
  • 采用链地址法处理冲突构造哈希表

    千次阅读 2018-01-25 23:00:28
    printf("-----------------------------------------------\n请选择要进行的操作:\n1、打印采用链地址法得到的哈希表\n"); printf("2、进行关键字查找\n3、退出\n----------------------------------------------...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 150,460
精华内容 60,184
关键字:

开地址法