织梦添加网站音乐,网站支付方案的设计,传媒公司简介模板,网站把域名解析到新ip后1.底层结构
顺序结构以及平衡中#xff0c;元素关键码与其存储位置之间没有相对应的关系#xff0c;因此在查找一个元素时#xff0c;要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。
理想的搜索方法#xff1a;可以不经过比较#xff0c;依次直接从表中直接搜索…1.底层结构
顺序结构以及平衡中元素关键码与其存储位置之间没有相对应的关系因此在查找一个元素时要经过关键码的多次比较。顺序查找的时间复杂度为O(N)。
理想的搜索方法可以不经过比较依次直接从表中直接搜索到指定元素如果构造一种数据结构通过某种函数使元素的存储位置与它的关键码之间能够建立----映射关系就可以很快的查找到指定的元素。
插入元素根据插入元素的关键码用函数计算出这个元素的存储位置并存放
查找元素对元素的关键码进行计算得到的函数值去取出此位置的存储元素并把输入的元素与此元素进行比较若关键码相等则查找成功
该方式为哈希(散列)方法哈希方法中的转换函数为哈希函数构造出来的结构为哈希表 一般是用关键码膜上该结构的总容量得到的值就为映射后的位置下标。
2.哈希冲突
对于俩个数据元素的关键码通过哈希函数后得到的值一样不同关键字通过相同哈希函数计算出相同的哈希值地址该现象称为哈希冲突或哈希碰撞。
3.哈希函数
引起哈希冲突的原因可能哈希函数设计不够合理
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址则值域必须在[0 m-1]之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数形式相对简单 除留余数法
设散列表中允许存储的地址数位m个取一个不大于m的数p且p最接近或者等于m的质数作为除数Hush(key)key%p(pm) ,将关键码转换为哈希地址
补充
key%2^16表示的是取后十六位然后key32-n假设n16是把前16位移到后16位最后把前16位和后16位异或的结果作为哈希值(key的前16位和后16位都到同一位置也就是后16位上了)把key的每一位都参与到计算这样得出的哈希值冲突会更少一些。 哈希冲突解决
闭散列也叫开放地址法当发生哈希冲突时如果哈希表未被填满说明哈希表中心必然还有空位置那么可以把key存放到冲突位置的下一个位置去。
找到空位置
1.线性探测
如下图要插入元素44先通过哈希函数计算出哈希地址44%104应在4的位置但是这个位置已经放了数据了所以要从发生冲突的位置开始依次向后找直到寻找到空位置为止 2.删除
采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其它元素的搜索比如删除4那么查找44时根据计算的哈希地址就是4的位置当44不在4位置在后面。所以通过枚举用标记的方式来删除元素。 enum State { EMPTY, EXIST, DELETE }; 3.哈希表扩容
散列表的载荷因子定义a填入表中的个数/散列表的长度
对于开放定址法 载荷因子应该限制在0.7~0.8以下 线性探测优点实现简单
线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据堆积在查找时需要进行多次比较导致搜索效率降低。
二次探测
线性探测的缺陷是产生冲突的数据堆积到一块这与其找找的下一个位置有关从发生冲突的位置向后找空位置可能会发生的问题二次探测就是为了避免该现象的出现。 hashhash0i^2 or hashhash0i^2 代码实现
1.枚举定义状态
设置三个状态存在空删除
enum State
{EXIST,EMPTY,DELETE
};2.定义存在哈希表里面的数据
pair模板first表示键值second表示值
templateclass K,class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};3.哈希表的构造 内联函数里面提供的数字就是质数有28个这里lower_bound是选一个大于等于n的数字这里的n也就是哈希表的存储个数返回处使用了三目操作符如果不是最后一个就是pos如果是最后一个就要返回最后一个的前一个。
HashTable():_tables(__stl_next_prime(0)),_n(0)
{}
inline unsigned long __stl_next_prime(unsigned long n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;
}
4.哈希表的插入
首先要判断插入的元素是否已经存在接着是判断载荷因子是否超过0.7这里把_n*10所以和7比较如果大于7就要扩容了哈希表扩容则原来的存储位置在新的里面是不一样的因为之前的存储是旧的size扩容后是新的size哈希函数得出的值改变了所以存储位置要重新计算这里newht的空间还是去之前的28个里面选这里1是因为28个数字对应不同区间所以只需要加一就会到下一个区间还要判断旧表每一个位置的状态是否是存在的说明之前是由元素在这个位置上则把此处的元素再作为Insert的参数重新插入最后交换地址如果没超过0.7则就正常插入通过模来得到哈希值然后还要线性检测是否此位置为空位置while循环后就找到了空位置则插入并改变状态为存在并把已经存储的个数n。
bool Insert(const pairK, V kv)
{if (Find(kv.first))return false;if (_n * 10 / _tables.size() 7){HashTableK, V newht;newht._tables.resize(__stl_next_prime(_tables.size() 1));for (auto data : _tables){if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 kv.first % _tables.size();size_t hashi hash0;size_t i 1;int flag 1;while (_tables[hashi]._state EXIST){hashi (hash0 i) % _tables.size();i;///二次探测////// hashi(hash0(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}
5.哈希表的查找
这里查找需要注意的是位置被占了可能在哈希函数得出的值的后面或者前面先得到要查找的键的哈希值然后用循环来寻找先看是否为空空说明不存在如果不为空还要判断键值是否一样不一样就线性检测去遍历找到就返回此处的地址。
HashDataK, V* Find(const K key)
{size_t hash0 key % _tables.size();size_t hashi hash0;size_t i 1;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi (hash0 i) % _tables.size();i;}return nullptr;
}
6.哈希表的删除
前面已经提到不能删除只改变状态为删除状态就行先用Find去找到指定位置判断是否找到找到就只改变状态变量。
bool Erase(const K key)
{HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;return true;}else{return false;}
} 总代码
HashTable.h
#pragma once#includevectorenum State
{EXIST,EMPTY,DELETE
};templateclass K,class V
struct HashData
{pairK, V _kv;State _state EMPTY;
};templateclass K,class V
class HashTable
{
public:HashTable():_tables(__stl_next_prime(0)),_n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}bool Insert(const pairK, V kv){if (Find(kv.first))return false;if (_n * 10 / _tables.size() 7){HashTableK, V newht;newht._tables.resize(__stl_next_prime(_tables.size() 1));for (auto data : _tables){if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 kv.first % _tables.size();size_t hashi hash0;size_t i 1;int flag 1;while (_tables[hashi]._state EXIST){hashi (hash0 i) % _tables.size();i;///二次探测////// hashi(hash0(i*i*flag))%_tables.size();/// ///}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){size_t hash0 key % _tables.size();size_t hashi hash0;size_t i 1;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi (hash0 i) % _tables.size();i;}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n;
};test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeiostream
#includeset
#includeunordered_setusing namespace std;
#includeHashTable.h
int main()
{//int a[] { 19,30,52,63,11,22 };int a[] { 19,30,5,36,13,20,21,12 };HashTableint, int ht;for (auto e : a){ht.Insert({ e, e });}//ht.Insert({ 15, 15 });ht.Erase(30);if (ht.Find(20)){cout 找到了 endl;}if (ht.Find(30)){cout 找到了 endl;}else{cout 没有找到 endl;}return 0;
}
