精华内容
下载资源
问答
  • hash table(全域散列法实现的哈希表) 利用每次重建哈希表时随机生成散列函数 #ifndef C11LEARN_HASHUNIVERSAL_H #define C11LEARN_HASHUNIVERSAL_H #include "Chain.h" #include "../tools/random.h" template<...

    hash table(全域散列法实现的哈希表)

    利用每次重建哈希表时随机生成散列函数

    
    #ifndef C11LEARN_HASHUNIVERSAL_H
    #define C11LEARN_HASHUNIVERSAL_H
    #include "Chain.h"
    #include "../tools/random.h"
    template<typename T>
    class HashUniversal
    {
    protected:
        Chain<T>** array;
        int capacity;
        long long large_prime_numbers;
        long long a;
        long long b;
    public:
        HashUniversal(int capacity = 1<<10,long long large_prime_numbers = 100001651);
        HashUniversal(const HashUniversal<T>& hashUniversal);
        const HashUniversal<T>& operator=(const HashUniversal<T>& hashUniversal);
        ~HashUniversal();
        T & operator[](int key);
        bool remove(int key);
    
    protected:
        virtual int hashing(int key);
        void insert(Chain<T>* node);
        Chain<T>*search(int key);
        void clear();
        void copy(const HashUniversal<T> & hashUniversal);
        bool remove(Chain<T>* node);
    };
    template<typename T>
    HashUniversal<T>::HashUniversal(int capacity,long long large_prime_numbers):capacity(capacity),large_prime_numbers(large_prime_numbers){
        array = new Chain<T>*[this->capacity];
        a = random_include_left_right(1ll,this->large_prime_numbers-1);
        b = random_include_left_right(0ll,this->large_prime_numbers-1);
    }
    template<typename T>
    HashUniversal<T>::HashUniversal(const HashUniversal<T>& hashUniversal)
    {
        capacity = hashUniversal.capacity;
        a = hashUniversal.a;
        b = hashUniversal.b;
        array = new Chain<T>*[this->capacity];
        large_prime_numbers = hashUniversal.large_prime_numbers;
        copy(hashUniversal);
    }
    template<typename T>
    const HashUniversal<T>& HashUniversal<T>::operator=(const HashUniversal<T>& hashUniversal){
        if(this == &hashUniversal) return *this;
        clear();
        delete[] array;
        capacity = hashUniversal.capacity;
        a = hashUniversal.a;
        b = hashUniversal.b;
        array = new Chain<T>*[this->capacity];
        large_prime_numbers = hashUniversal.large_prime_numbers;
        copy(hashUniversal);
        return *this;
    }
    template<typename T>
    HashUniversal<T>::~HashUniversal(){
        clear();
        if(array!= nullptr)
        {
            delete [] array;
            array = nullptr;
        }
    }
    template<typename T>
    T & HashUniversal<T>::operator[](int key){
        Chain<T>* node = search(key);
        if(node == nullptr)
        {
            node = new Chain<T>();
            node->key = key;
            insert(node);
        }
        return node->value;
    }
    template<typename T>
    int HashUniversal<T>::hashing(int key)
    {
        return ((a*key+b)%large_prime_numbers)%capacity;
    }
    template<typename T>
    void HashUniversal<T>::insert(Chain<T>* node){
        int pos = hashing(node->key);
        Chain<T>* current = array[pos];
        if(current == nullptr)
        {
            array[pos] = node;
        }
        else
        {
            current->prev = node;
            node->next = current;
        }
    }
    template<typename T>
    Chain<T>* HashUniversal<T>::search(int key){
        int pos = hashing(key);
        Chain<T>* current = array[pos];
        while (current!= nullptr && current->key != key)
            current = current->next;
        return current;
    }
    template<typename T>
    void HashUniversal<T>::clear(){
        Chain<T>* current;
        Chain<T>* next;
        for (int i = 0; i < capacity; ++i) {
            current = array[i];
            while (current!= nullptr)
            {
                next = current->next;
                delete current;
                current = next;
            }
        }
    }
    template<typename T>
    void HashUniversal<T>::copy(const HashUniversal<T> & hashUniversal){
        Chain<T>* current;
        Chain<T>* prev;
        for (int i = 0; i < capacity; ++i) {
            prev = nullptr;
            current = hashUniversal.array[i];
            while (current!= nullptr)
            {
                prev = current;
                current = current->next;
            }
            while (prev!= nullptr)
            {
                Chain<T>* node = new Chain<T>();
                node->key = prev->key;
                node->value = prev->value;
                insert(node);
                prev = prev->prev;
            }
        }
    }
    template<typename T>
    bool HashUniversal<T>::remove(int key){
        Chain<T>* node = search(key);
        if(node == nullptr)
        {
            return false;
        }
        return remove(node);
    }
    template<typename T>
    bool HashUniversal<T>::remove(Chain<T>* node){
        if(node == nullptr) return false;
        if(node->prev == nullptr)
        {
            int pos = hashing(node->key);
            array[pos] = node->next;
            if(node->next!= nullptr)
            {
                node->prev = nullptr;
            }
        }
        else
        {
            node->prev->next = node->next;
            if(node->next!= nullptr)
            {
                node->next->prev = node->prev;
            }
        }
        delete node;
        node = nullptr;
        return true;
    }
    #endif //C11LEARN_HASHUNIVERSAL_H
    
    

    辅助类
    1⃣️Chain链接地址
    2⃣️random_include_left_right链接地址

    测试代码

    	HashUniversal<string> hashUniversal;
        hashUniversal[2] = "hello";
        hashUniversal[123456] = "world";
        cout << hashUniversal[2] << endl;
        cout << hashUniversal[123456] << endl;
        HashUniversal<string> hashUniversal1 = hashUniversal;
        cout << hashUniversal1[2] << endl;
        cout << hashUniversal1[123456] << endl;
        HashUniversal<string> hashUniversal2;
        hashUniversal2 = hashUniversal;
        cout << hashUniversal2[2] << endl;
        cout << hashUniversal2[123456] << endl;
        cout<<hashUniversal2.remove(123456)<<endl;
    
    展开全文
  • 全域散列法性能证明

    2019-01-14 19:01:43
    本文首先依据全域散列函数的全域性来证明全域散列法的性能,而后设计一个全域散列函数。 下面是定理11.3和推论11.4的证明分析,其实我们的目的是为了证明推论11.4,才想到去证明定理11.3 • 【证明核心步骤】 ○ ...

    本文首先依据全域散列函数的全域性来证明全域散列法的性能,而后设计一个全域散列函数。

    下面是定理11.3和推论11.4的证明分析,其实我们的目的是为了证明推论11.4,才想到去证明定理11.3
    • 【证明核心步骤】
    ○ 指示器变量+分类讨论+穷举
    ○ 【证明目标锁定】:因为散列表的性能主要决定于其查找操作的性能,因此我们决定求得任意关键词k所在链表的期望长度
    • 【证明成功的背后本质原因】
    ○ 核心假设:散列函数的全域性假设,即得知冲突概率为1/m,这是本次证明和核心。
    ○ 【直观分析】:既然知道了冲突概率1/m,那么冲突的数量很自然就是n/m了
    ○ 本定理是全域性假设假设成立后的直接结果
    • 【证明结果的意义】
    定理11.3直接导出了推论11.4,而推论11.4即说明了我们的全域散列函数性能非常好。

    在这里插入图片描述
    在这里插入图片描述

    下文将设计一个全域散列函数,并证明其全域性。
    证明全域性是一个纯代数活,没有什么好分析的

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 文章目录全域散列指出可以选择 |H| 个散列函数,且它们最大重合(个数) ≤ t=|H|/m(这个值t=|H|/m是精心构造的指标,以便得到后面的1/m)introduction to algorithm 全域散列指出可以选择 |H| 个散列函数,且它们最大...

    全域散列指出可以选择 |H| 个散列函数,且它们最大重合(个数) ≤ t=|H|/m(这个值t=|H|/m是精心构造的指标,以便得到后面的1/m)

    其中重合是指,对任意 x != y,使散列函数集合 H 中 h(x) == h(y) 的散列函数个数。
    随机选择散列函数后,对于恶意的精心设计来引起尽可能多的冲突的破坏行为的输入k1!=k2),能够被这个 k1,k2 命中的散列函数个数就会 ≤t= |H|/m,
    (在这里需要注意一下,函数越多,那么被命中函数就可能f风险越多,如果对于|H|个(所有的)散列函数,
    对于输入同一对k1,k2输给所有散列函数,能够命中次数不超过t=|H|/m;
    则若指定其中的一个散列函数,那么k1,k2输入能够使得冲突的发生的概率满足:不超过t/|H|=1/m的命中率
    即命中概率 ≤ |H|/m / |H| = 1/m。
    也就是说,对于精心构造的(恶意要引起冲突)的输入,冲突率仍然能够控制在 1/m内。

    H:全域散列函数组
    一组有限的散列函数
    它将给定的关键字全域U,映射到{0,1,…,m-1}(m为散列表的长度)中
    如果每一对关键字k,l(k!=l),满足h(k)=h(l)的散列函数h(h属于H)的个数至多位|H|/m

    introduction to algorithm

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 全域散列法在执行开始时,就从一组精心设计的函数中,随机地选择一个作为散列函数。选定后,后续操作都用这一个函数,不再更改。 完全散列 采用两级的散列方法来设计完全散列方案,在每级上都使用全域散列。  .....

    参考:算法导论

    全域散列

    全域散列法在执行开始时,就从一组精心设计的函数中,随机地选择一个作为散列函数。选定后,后续操作都用这一个函数,不再更改。

    完全散列

    采用两级的散列方法来设计完全散列方案,在每级上都使用全域散列。

     

    展开全文
  • 在直接寻址方式中,具有关键字kkk的元素被存放在槽kkk中,在散列方式下,该元素存放在槽h(k)h(k)h(k)中,即利用散列函数hhh,由关键字kkk计算出槽的位置。函数hhh将关键字的全域UUU映射到散列表T[0..m−1]T[0..m-1]T...
  • 本文探讨拉链表解决哈希冲突的方式和几种常见的散列函数。  首先,什么是散列表?  对于一个数组,我们在O(1)时间复杂度完成可以完成其索引的查找,现在我们想要存储一个key value的键值对,我们可以根据key生成...
  • 二、哈希表的链接 每个槽保存一个链表,若是双链表可以方便删除 效率分析:一次不成功查找的平均时间为θ(1+α),其中α=n/m称为装载因子。因此当槽的个数m为n的常数倍时,可以认为一次哈希操作耗费O(1)的时间 ...
  • 散列表是实现字典操作的一种有效数据结构,你可以把它和STL中的map或者Python...⑤全域散列法 书上写的没看懂,先记下以后补。 终于体会到数学当初没好好学的痛苦了,现在真真学什么都碰壁! 所以,数学我可。
  • 学习笔记(散列法

    2018-02-28 20:36:52
    多数散列函数都假定关键字的全域为自然数集,因此我们首先想...下面介绍两种散列法:1.除法散列法 散列函数h(k)=k mod m 要避免选择m的某些值。如m不应为2的幂,否则h(k)就是k的p个最低位数字。m常常取不太接近2的...
  • 散列表之散列函数

    千次阅读 2015-06-26 13:38:20
    全域散列法散列表之散列函数我们在之前的文章《散列表之链接法》中已经提到过,散列函数是散列表的一个难点,一个好的散列可以很大程度上提升散列表的查找和删除操作的速度,而一个设计差劲的散列表的,查找和删除...
  • 散列

    2017-12-06 17:40:40
    设计散列函数 开放寻址(open addressing)
  • 除法散列法中,散列函数为:h(k) = k mod m 其中k为关键字,关键字全域为自然数集N;m为槽的个数。 为什么《算法导论》上说“m = 2^p,则h(k)就是k的p个最低位数字”呢? 我的思路是:由于10的p次(和p次以上)幂...
  • 散列表之完美散列

    千次阅读 2015-07-27 11:56:54
    两级散列法 gperf工具来自动生成完美散列函数 gperf的安装 gperf关键字文件的书写格式 gperf应用举例 注意本文中的所有代码你都可以在这里:https://github.com/qeesung/algorithm/tree/master/chapter11/11-5/gperf...
  • 其中的两种方法(用除进行散列和用乘法进行散列)本质上属于启发式方法,而第三种方法(全域散列)则利用了随机技术来提供可证明的良好性能。 好的散列函数的特点 一个好的散列函数应(近似地)满足简单均匀散列...
  • 浅析散列存储

    2017-08-07 14:57:49
    说到散列,我们可能觉得是个新奇的事物,但实际上学过Java的人就会知道,在equal函数中会使用到hashcode,那就是所谓的散列码,而将对应的字转换成散列码的过程,我们称之为散列过程,这个过程函数被称之为散列函数...
  • 设计好的哈希函数 除数散列法 乘数散列法 全域散列法 解决哈希冲突方法 链式地址法 开放寻址法 线性探查 二次探查 双重散列 完全散列法 文章快速说明索引 学习目标: 前言:还记得在大学的时候,数据结构作为计算机...
  • 解决散列表冲突方法

    万次阅读 2018-03-26 15:55:23
    1 解决冲突方法1.1 链接又叫拉链,将具有同一散列地址的记录存储在一条线性链表中1.2 开放定址通过对原hash函数进行修改,添加探查函数,当出现冲突时,往下一个地址写数据图中p(i)为探查函数探查函数分为以下四种...
  • 散列表

    2018-05-24 13:39:23
    通过散列函数,我们可以实现对数据的快速访问(理想情况下是常数时间内,但这取决于散列函数、碰撞概率、负载系数等因素)。  实际上,散列表是普通数组概念的推广。由于对普通数组可以直接寻址,使得...
  • 全域散列法确保,当k!=l时,两者发生碰撞的概率不大于1/m。设计一个全域散列函数类的方法如下,该方法中,散列表大小m的大小是任意的。 选择一个足够大的质数p,使得每一个可能的关键字都落在0到p-1的范围内。设...
  • 先简单介绍下哈希函数 ...这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)
  • 浅谈散列

    2017-03-05 16:26:12
    浅谈散列   通俗的说,程序是能够完成既定目标的具有特定逻辑组织形式的指令集序列。既然有现实的需求,那么我们知道外界环境必然会给予程序某些特定形式的“输入”,然而在机器的内部,这种“输入”将转换为...
  • 除法散列法 在除数散列法中,对于除数的选择很重要。 3. 乘法散列法 4. 全域哈希 读者可以参考下述答案知乎-怎么理解全域哈希理解【全域哈希】的思想与实现 对于任意一个特定的散列函数,如果别有用心地设计一组...
  • 2.2 散列函数方法 2.2.1 直接定址法 2.2.2 数字分析法 2.2.3 平方取中法 2.2.4 折叠法 2.2.5 除留余数法 2.2.6 随机数法 2.2.7 除法散列法 2.2.8 乘法散列法 2.2.9 全域散列法 2.2.10 使用总结 3 哈希冲突 ...
  • 散列表的基本概念散列表(hash table),是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录,以加快查找的...这个映射函数叫做散列函数,存放记录的数组叫做散列表。
  • 全域散列法。定义多个散列函数,随机调用。 碰撞处理 分离链接法 链表链接: 你可以想象在数组的槽里面存了一个指向链表的指针。比如这样 vector<list<int> *> 。这个实现的缺点就是, 遍历...
  • 散列表(Hash Table)全解析

    千次阅读 2013-11-12 18:39:11
    唯一有效的改进方法是随机地选择散列函数,使之独立于要存储的关键字,即采用全域散列法全域散列法在执行开始时,就从一组精心设计的函数中,随机地选择一个作为散列函数。就像在快速排序中一样,随机化保证了...
  • 散列的原理

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 507
精华内容 202
热门标签
关键字:

全域散列法