精华内容
下载资源
问答
  • 哈希表之开地址法解决冲突

    千次阅读 2016-01-23 13:20:41
    在上一篇博文中,我们讲述了使用链地址法解决冲突的方法。这里我们介绍另一种方式:开地址法解决冲突。 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1...

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

    基本思想:当关键码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;
    }
    (三)伪随机探测再散列


    (四)双散列法


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


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

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

    展开全文
  • 例如,有80个记录,关键字为8位十进制整数d1d2d3…d7d8,如哈希表长取100,则哈希表的地址空间为:00~99。假设经过分析,各关键字中 d4和d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3…d7d8)=d4d7。例如,h...

    1. 数字分析法

      如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。例如,有80个记录,关键字为8位十进制整数d1d2d3…d7d8,如哈希表长取100,则哈希表的地址空间为:00~99。假设经过分析,各关键字中 d4和d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3…d7d8)=d4d7。例如,h(81346532)=43,h(81301367)=06。相反,假设经过分析,各关键字中 d1和d8的取值分布极不均匀, d1 都等于5,d8 都等于2,此时,如果哈希函数为:h(key)=h(d1d2d3…d7d8)=d1d8,则所有关键字的地址码都是52,显然不可取。
    

    2. 平方取中法

    当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。

    3. 分段叠加法

      这种方法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加,折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。例如:key=12360324711202065,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为105和907,
    

    4. 除留余数法

    假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为

    h(k)=k % p ,其中%为模p取余运算。

    例如,已知待散列元素为(18,75,60,43,54,90,46),表长m=10,p=7,则有

    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   
    
    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   
    
    h(46)=46 % 7=4
    

    此时冲突较多。为减少冲突,可取较大的m值和p值,如m=p=13,结果如下:

    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    
    
    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   
    
    h(46)=46 % 13=7
    

    处理冲突的方法:

    1.     开放定址法
      

    这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

          Hi=(H(key)+di)% m   i=1,2,…,n
    
    其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:
    

    l 线性探测再散列

    dii=1,2,3,…,m-1
    

    这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

    l 二次探测再散列

    di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 )
    
    这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。
    

    l 伪随机探测再散列

    di=伪随机数序列。
    

    具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

    例如,已知哈希表长度m=11,哈希函数为:H(key)= key % 11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元,参图8.26 (a)。如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元,参图8.26 (b)。如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,………,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元

    1.     再哈希法
      

      这种方法是同时构造多个不同的哈希函数:

      Hi=RH1(key) i=1,2,…,k

    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    1.     链地址法
      

      这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    4、建立公共溢出区

    这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

    展开全文
  • 哈希表及哈希冲突解决办法

    千次阅读 2019-07-17 22:04:11
    哈希表及哈希冲突解决办法 目录 什么是哈希表哈希表的数据结构 哈希冲突 哈希冲突解决办法 1. 什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而...

    哈希表及哈希冲突解决办法


    目录

    1. 什么是哈希表?

    2. 哈希表的数据结构

    3. 哈希冲突

    4. 哈希冲突解决办法


    1. 什么是哈希表?

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    hash就是找到一种数据内容和数据存放地址之间的映射关系。

    当使用哈希表hashtable(key,value) 进行查询的时候,就是使用哈希函数将关键码key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。


    2. 哈希表的数据结构

    数组的特点是:寻址容易,插入和删除困难;
    而链表的特点是:寻址困难,插入和删除容易。

    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:在这里插入图片描述

    左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。


    3. 哈希冲突

    1. 哈希冲突:即不同key值产生相同的地址,即发生了哈希冲突。一般来说,哈希冲突是无法避免的,所以就有了解决方案。

    4. 哈希冲突解决办法

    (一)链地址法

    1. HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:
      1. 插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

      2. 查询操作:和插入操作一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

      3. 删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

    在这里插入图片描述

    1. 与开放定址法相比,拉链法有如下几个优点:
      ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

      ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

      ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

      ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

    2. 拉链法的缺点

      指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

      使用例子:HashMap

    (二)开发地址法

    开发地址法的做法是,当冲突发生时,使用某种探测算法在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。按照探测序列的方法,一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。

    这里为了更好的展示三种方法的效果,我们用以一个模为8的哈希表为例,采用除留余数法,往表中插入三个关键字分别为26,35,36的记录,分别除8取模后,在表中的位置如下:
    在这里插入图片描述
    这个时候插入42,那么正常应该在地址为2的位置里,但因为关键字26已经占据了位置,所以就需要解决这个地址冲突的情况,接下来就介绍三种探测方法的原理,并展示效果图。

    1) 线性探查法:

    fi=(f(key)+i) % m ,0 ≤ i ≤ m-1

    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到有空余的地址或者到 T[d-1]为止。

    插入42时,探查到地址2的位置已经被占据,接着下一个地址3,地址4,直到空位置的地址5,所以42应放入地址为5的位置。
    在这里插入图片描述

    缺点:需要不断处理冲突,无论是存入还是査找效率都会大大降低。

    2) 二次探查法

    fi=(f(key)+di) % m,0 ≤ i ≤ m-1

    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+di],di 为增量序列1^2 , -1^2, 2^2, -2^2,……, q^2, -q^2 且q≤1/2 (m-1) ,直到探查到 有空余地址或者到 T[d-1]为止。

    缺点:无法探查到整个散列空间。

    所以插入42时,探查到地址2被占据,就会探查T[2+1^2]也就是地址3的位置,被占据后接着探查到地址7,然后插入。(文章说是地址7位置上,但是照上面运算我觉得是T(2±1=1)),是1位置上添加。
    在这里插入图片描述

    3) 伪随机探测
    di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

    (三)再散列法

    fi=(f(key)+i*g(key)) % m (i=1,2,……,m-1)

    其中,f(key) 和 g(key) 是两个不同的哈希函数,m为哈希表的长度

    步骤:

    1. 双哈希函数探测法,先用第一个函数 f(key) 对关键码计算哈希地址,一旦产生地址冲突,再用第二个函数 g(key) 确定移动的步长因子,最后通过步长因子序列由探测函数寻找空的哈希地址。

    2. 比如,f(key)=a 时产生地址冲突,就计算g(key)=b,则探测的地址序列为 f1=(a+b) mod m,f2=(a+2b) mod m,……,fm-1=(a+(m-1)b) % m,假设 b 为 3,那么关键字42应放在 “5” 的位置。


    文章内容引用博客:
    数据结构:哈希表以及哈希冲突的解决方案: https://blog.csdn.net/yeyazhishang/article/details/82533211
    解决hash冲突的三种方法:https://www.cnblogs.com/kaleidoscope/p/9588151.html

    展开全文
  • 链表法解决冲突问题构造的哈希表参考链接:2. LRU缓存淘汰算法参考链接: 1. 链表法解决冲突问题构造的哈希表 参考链接: https://www.cnblogs.com/lpshou/archive/2012/05/08/2490191.html 2. LRU缓存淘汰算法 ...

    1. 链表法解决冲突问题构造的哈希表

    1.1 哈希表:

    线性表和树等线性结构中,记录在结构中的相对位置是随机的,和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需要进行一系列和关键字的比较。理想的情况是希望不经过任何比较,一次存取便能够取到所查找的记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时,只要根据这个对应关系f找到给定值K的像f(k)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,因此,不需要进行比较便可以直接取得所查记录。在此,我们称这个对应关系f为哈希函数,按照这个思想建立的表为哈希表。
      哈希函数的构造方法很多,常用的有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等

    1.2 冲突问题:

    对于不同的关键字可能得到同一哈希地址,即 key1!=key2,而f(key)=f(key2),这种现象叫做冲突,在一般情况下,冲突只能尽可能的少,而不能完全避免。因为,哈希函数是从关键字集合到地址集合的映像。通常,关键字集合比较大,它的元素包括多有可能的关键字,而地址集合的元素因为哈希表中的地址值。既然如此,那么,如何处理冲突则是构造哈希表不可缺少的。
      通常用于处理冲突的方法有:开放定址法、再哈希法、链地址法、建立一个公共溢出区等

    1.3 解决方法:链地址法

    • (1)采用除留余数法构造哈希函数,冲突解决采用链地址法。
    • (2)具体的关键字列表为(19,14,23,01,68,20,84,27,55,11,10,79),则哈希函数为H(key)=key MOD 13。则采用除留余数法和链地址法后得到的预想结果应该为:
        在这里插入图片描述
    • 哈希造表完成后,进行查找时,首先是根据哈希函数找到关键字的位置链,然后在该链中进行搜索,如果存在和关键字值相同的值,则查找成功,否则若到链表尾部仍未找到,则该关键字不存在。
    # -*- coding: utf-8 -*-
    """
    Created on Tue Apr 16 21:06:20 2019
    
    @author: janti
    """
    class Node:
        def __init__(self,key,value):
            self.key=key
            self.value=value
            self.next=None
            
    
    class ChainHash:
        def __init__(self,capacity):
             self.capacity=capacity
             self.table=[None]*capacity
        def buildHash(self,lista):
            for i in range(len(lista)):
                value=int(lista[i])
                key=value % 13
                print(key)
                node_=self.table[key]
            
                if node_ is None:
                    self.table[key]=Node(key,value)
                else:
                    while node_.next is not None:
                        if node_.key == key:
                            node_.value = value
                            return
                        node_ = node_.next
                    node_.next = Node(key, value)
            
        
            
        def InsertHash(self,value):
            key=value % 13
            node_=self.table[key]
            if node_ is None:
                self.table[key]=Node(key,value)
            else:
                while node_.next is not None:
                    if node_.key == key:
                        node_.value = value
                        return
                    node_ = node_.next
                node_.next = Node(key, value)
                
        def SearchHash(self,key,value):
            node_ = self.table[key]
            while node_ is not None:
                if node_.value == value:
                    return node_ # 返回该指针位置
                node_ = node_.next
            return None    # 若没有找到该数值,则返回空
    # In[]
    if __name__ == '__main__':
        s=ChainHash(20)
        lista=[1,6,11,14,19]
        
        # In[]
        s.buildHash(lista)
            # In[]
        s.InsertHash(27)
    #    print(s.table)
         # In[]
        print(s.SearchHash(1,17))
            
    

    参考链接:

    https://www.cnblogs.com/lpshou/archive/2012/05/08/2490191.html

    2. LRU缓存淘汰算法

    2.1 原理

    LRU(Least recently used,最近最少使用)缓存算法根据数据最近被访问的情况来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

    在这里插入图片描述
    下图中,介绍了一个缓存空间为5的缓存队列,当访问数据的顺序是:1,2,3,4,5,6,7,6,4,0 时空间中数据的变化过程。

    在这里插入图片描述

    1. 当缓存空间未满时,数据一直往新的空间写;
    2. 当缓存满,并且缓存中没有需要访问的数据时,最先进入缓存的数据被淘汰掉;
    3. 当缓存满,并且缓存中有需要访问的数据时,做了一个数据交换,把访问的数据拿出来,其余数据往下压,最后把访问的数据放到顶部

    2.2 代码原理

    参考链接:

    https://blog.csdn.net/qq1332479771/article/details/69370779
    https://zhuanlan.zhihu.com/p/34989978

    展开全文
  • 虽然我们不希望发生冲突,但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。... 用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(...
  • 哈希表冲突及处理冲突的方法

    万次阅读 多人点赞 2018-07-06 20:31:30
    哈希法又称散列、杂凑以及关键字地址计算等,相应的表成为哈希表。 基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f,使得P=f(K),其中f成为哈希函数。 创建哈希表时,把关键字K的元素直接...
  • 1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。 2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。 3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,...
  • 哈希表:通过关键码来映射到值的一个数据结构; 哈希函数:键与值映射的一个映射关系; 哈希函数的构建: 常用方法: 1、直接寻址:f(x) = kx+b (k、b都是常数) ,一旦确定了哈希函数,那么添加、获取元素都需要...
  • 哈希表 哈希函数:记录的存储位置和它的关键字之间建立一个确定的对应关系。 冲突:对不同的关键字可能得到同一哈希地址,这种现象称为冲突。 哈希函数构造方法 1.直接定址 取关键字或关键字的某个线性函数值...
  • “处理冲突”的含义是:为产生冲突的关键字寻找下一个哈希地址。通常有两类方法处理冲突:开放定址(Open Addressing)和拉链(Chaining)。前者是将所有结点均存放在散列表T[0..m-1]中;后者通常是将互为同义词的...
  • 哈希表之三冲突解决

    2017-07-01 20:07:00
    前的部分分析了,哈希表中的冲突时难以避免的,冲突是很正常的,所以就要知道如何解决冲突。 我觉得冲突是有两种解决的方法: 1、横向的解决 2、纵向的解决 所谓横向解决:指的是对冲突的键,会在哈希表上另外找...
  • 1 开放地址 这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述: H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ...
  • 哈希表以及解决冲突的方法

    千次阅读 2014-03-16 19:27:48
    哈希法又称散列、杂凑以及关键字地址计算等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...
  • 文章目录Java哈希表概念冲突避免冲突哈希函数的设计方法常见哈希函数负载因子调节解决哈希冲突两种常见的方法是:闭散列和开散列哈希表和 java 类集的关系 Java哈希表 概念 顺序结构以及平衡树中,元素关键码与其...
  • 哈希法又称散列、杂凑以及关键字地址计算等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...
  • 哈希表冲突解决

    千次阅读 2013-09-03 12:38:12
    这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:  H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – ...
  • 一文详解哈希表的哈希冲突

    千次阅读 2020-04-05 19:10:25
    哈希表如何进行冲突避免
  • Redis底层详解(一) 哈希表和字典

    万次阅读 多人点赞 2018-06-28 17:27:37
    一文读懂哈希表
  • 哈希表查找、哈希冲突-面试题

    千次阅读 2016-08-30 00:13:49
    哈希查找是面试中常见的问题。本文为自己梳理一下知识点。 对于大多数查找算法,其查找效率取决于查找过程的比较次数。比如二叉查找树,二分查找。...哈希表哈希存储的基本思想是以关键字(key)为自变量,通过
  • 基于先前的学习计划,最近打算深入学习Java的集合类,首先要研究的就是HashMap,在学习HashMap前,我花了几天时间温习了一下类中用到的数据结构 (哈希表,二叉树),并决定把所学的知识记录写成文章,本文讲述的...
  • 哈希表构造与处理冲突方法

    千次阅读 2014-02-12 18:10:07
    我们知道:哈希表是一个固定大小的数组,数组的每个元素是一个链表(单向或双向)的头指针。如果Key一样,则在一起,如果Key不一样,则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索,它利用Key的“哈希...
  • Hashtable的结构,采用的是数据结构中所说的链地址处理冲突的方法    从上面的结构图可以看出,Hashtable的实质就是一个数组+链表。图中的Entry就是链表的实现,Entry的结构中包含了对自己的另一个实例的引用...
  • 这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:  H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m –...
  • 0 1散列表 1简单来说就是给一个key,就可以找到对应...我们时常会碰到两个关键字key1 ≠ key2,但是却有f (key1) = f (key2),这种现象我们称为冲突(collision), 打个比方说:加上f的函数是这样的f(key)=key%10...
  • 哈希表和哈希冲突

    千次阅读 2018-08-19 17:02:55
    哈希表(hash table)是根据关键码(key)值(value)进行直接访问的数据结构 hash table的查询速度非常快,时间复杂度几乎是o(1)。如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度...
  • 哈希表及处理冲突的方法

    千次阅读 2018-11-20 13:08:14
    哈希法又称***散列、杂凑以及关键字地址计算***等,相应的表称为哈希表。 这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。 创建哈希表...
  • 前言  当我们在编程过程中,往往需要对线性表进行查找操作。在顺序中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,209
精华内容 12,483
关键字:

哈希表随机法解决冲突