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

展开全文
• 本文首先依据全域散列函数的全域性来证明全域散列法的性能，而后设计一个全域散列函数。 下面是定理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)introduction to algorithm

全域散列指出可以选择 |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...⑤全域散列法 书上写的没看懂，先记下以后补。 终于体会到数学当初没好好学的痛苦了，现在真真学什么都碰壁！ 所以，数学我可。
• 多数散列函数都假定关键字的全域为自然数集，因此我们首先想...下面介绍两种散列法：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
• 除法散列法中，散列函数为：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
唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字，即采用全域散列法全域散列法在执行开始时，就从一组精心设计的函数中，随机地选择一个作为散列函数。就像在快速排序中一样，随机化保证了...
• 散列的原理

...