番禺网站建设优化,北京高端网站建设规划,wordpress首页锚点,分享网站对联广告哈希表概念
二叉搜索树具有对数时间的表现#xff0c;但这样的表现建立在一个假设上#xff1a;输入的数据有足够的随机性。哈希表又名散列表#xff0c;在插入、删除、搜索等操作上具有「常数平均时间」的表现#xff0c;而且这种表现是以统计为基础#xff0c;不需依赖…哈希表概念
二叉搜索树具有对数时间的表现但这样的表现建立在一个假设上输入的数据有足够的随机性。哈希表又名散列表在插入、删除、搜索等操作上具有「常数平均时间」的表现而且这种表现是以统计为基础不需依赖输入元素的随机性。
听起来似乎不可能倒也不是例如
假设所有元素都是 8-bits 的正整数范围 0~255那么简单得使用一个数组就可以满足上述要求。首先配置一个数组 Q拥有 256 个元素索引号码 0~255初始值全部为 0。每一个元素值代表相应的元素的出现次数。如果插入元素 i就执行 Q[i]如果删除元素 i就执行 Q[i]--如果查找元素 i就看 Q[i] 是否为 0。 这个方法有两个很严重的问题。
如果元素是 32-bits数组的大小就是 2324GB2^{32} 4 GB2324GB这就太大了更不用说 64-bits 的数了如果元素类型是字符串而非整数就需要某种方法使其可用作数组的索引
散列函数
如何避免使用一个太大的数组以及如何将字符串转化为数组的索引呢一种常见的方法就是使用某种映射函数将某一元素映射为一个「大小可接受的索引」这样的函数称为散列函数。
散列函数应有以下特性
函数的定义域必须包含需要存储的全部关键字当散列表有 m 个地址时其值域在 0 到 m - 1 之间函数计算出来的地址能均匀分布在整个空间
直接定址法
取关键字的某个线性函数为散列地址Hash(Key)A∗KeyBHash(Key) A * Key BHash(Key)A∗KeyB
优点简单、均匀
缺点需要事先知道关键字的分布情况
使用场景数据范围比较集中的情况
除留余数法
设散列表的索引个数为 m取一个不大于 m但最接近 m 的质数 p 最为除数按照散列函数Hash(Key)keyHash(Key) key % pHash(Key)key将关键字转化为哈希地址
平方取中法
假设关键字为 1230它的平方是 1512900取中间的 3 位 129 作为哈希地址
再比如关键字为 321它的平方是 103041取中间的 3 位 304或 30作为哈希地址。
哈希冲突
使用散列函数会带来一个问题可能有不同的元素被映射到相同的位置。这无法避免因为元素个数大于数组的容量这便是「哈希冲突」。解决冲突问题的方法有很有包括线性探测、二次探测、开散列等。
线性探测
当散列函数计算出某个元素的插入位置而该位置上已有其他元素了。最简单的方法就是向下一一寻找到达尾端就从头开始找直到找到一个可用位置。
进行元素搜索时同理如果散列函数计算出来的位置上的元素值与目标不符就向下一一寻找直到找到目标值或遇到空。
至于元素的删除必须采用伪删除即只标记删除记号实际删除操作在哈希表重新整理时再进行。这是因为哈希表中的每一个元素不仅表示它自己也影响到其他元素的位置。 从上述插入过程我们可以看出当哈希表中元素变多时发生冲突的概率也变大了。由此我们引出哈希表一个重要概念负载因子。
负载因子定义为Q 表中元素个数 / 哈希表的长度
负载因子越大剩余可用空间越少发生冲突可能越大负载因子越小剩余可用空间越多发生冲突可能越小同时空间浪费更多
因此控制负载因子是个非常重要的事。对于开放定址法发生了冲突就找下一个可用位置负载因子应控制在 0.7~0.8 以下。超过 0.8查找时的 CPU 缓存不命中按照指数曲线上升。
二次探测
线性探测的缺陷是产生冲突的数据会堆在一起这与其找下一个空位置的方式有关它找空位置的方式是挨着往后逐个去找。二次探测主要用来解决数据堆积的问题其命名由来是因为解决碰撞问题的方程式 F(i)i2F(i) i^2F(i)i2 是个二次方程式。
更具体地说如果散列函数计算出新元素的位置为 H而该位置实际已被使用那么将尝试 H12,H22,H32,...,Hi2H 1^2, H 2^2, H 3^2, ... , H i^2H12,H22,H32,...,Hi2而不是像线性探测那样依次尝试 H1,H2,H3,...,HiH 1, H 2, H 3, ... , H iH1,H2,H3,...,Hi。 大量实验表明当表格大小为质数而且保持负载因子在 0.5 以下超过 0.5 就重新配置那么就可以确定每插入一个新元素所需要的探测次数不超过 2。
链地址法
这种方法是在每一个表格元素中维护一个链表在呢个链表上执行元素的插入、查询、删除等操作。这时表格内的每个单元不再只有一个节点而可能有多个节点。 节点的定义
template class Value
struct __hashtable_node {__hashtable_node* next;Value val;
};哈希表的实现
闭散列
接口总览
template class K, class V
class HashTable {struct Elem {pairK, V _kv;State _state EMPTY;};
public:Elem* Find(const K key);bool Insert(const pairK, V kv);bool Erase(const K key);
private:vectorElem _table;size_t _n 0;
};节点的结构
因为在闭散列的哈希表中的每一个元素不仅表示它自己也影响到其他元素的位置。所以要使用伪删除我们使用一个变量来表示。
/// brief 标记每个位置状态
enum State {EMPTY, // 空EXIST, // 有数据DELETE // 有数据但已被删除
};哈希表的节点结构不仅存储数据还存储状态。
/// brief 哈希表的节点
struct Elem {pairK, V _kv; // 存储数据State _state; // 存储状态
};查找
查找的思路比较简单
利用散列函数获取映射后的索引遍历数组看是否存在直到遇到空表示查找失败
/// brief 查找指定 key
/// param key 待查找节点的 key 值
/// return 找到返回节点的指针没找到返回空指针
Elem* Find(const K key) {if (_table.empty()) {return nullptr;}// 使用除留余数法的简化版本并没有寻找质数// 同时该版本只能用于正整数对于字符串等需使用其他散列函数size_t start key % _table.size(); size_t index start;size_t i 1;// 直到找到空位置停止while (_table[index]._state ! EMPTY) {if (_table[index]._state EXIST _table[index]._kv.first key) {return _table[index];}index start i;index % _table.size();i;// 判断是否重复查找if (index start) {return nullptr;}}return nullptr;
}在上面代码的查找过程中加了句用于判断是否重复查找的代码。理论上上述代码不会出现所有的位置都有数据查找不存在的数据陷入死循环的情况因为哈希表会扩容闭散列下负载因子不会到 1。
但假如我们插入了 5 个数据又删除了它们之后又插入了 5 个数据将 10 个初始位置都变为非 EMPTY。此时我们查找的值不存在的话是会陷入死循环的。
插入
插入的过程稍微复杂一些
首先检查待插入的 key 值是否存在其次需要检查是否需要扩容使用线性探测方式将节点插入
/// brief 插入节点
/// param kv 待插入的节点
/// return 插入成功返回 true失败返回 false
bool Insert(const pairK, V kv) {// 检查是否已经存在Elem* res Find(kv.first);if (res ! nullptr) {return false;}// 看是否需要扩容if (_table.empty()) {_table.resize(10);} else if (_n 0.7 * _table.size()) { // 变化一下负载因子计算可以避免使用除法HashTable backUp;backUp._table.resize(2 * _table.size());for (auto [k, s] : _table) {// C 17 的结构化绑定// k 绑定 _kvs 绑定 _stateif (s EXIST) {backUp.Insert(k);}}// 交换这两个哈希表现代写法_table.swap(backUp._table);}// 将数据插入size_t start kv.first % _table.size();size_t index start;size_t i 1;// 找一个可以插入的位置while (_table[index]._state EXIST) {index start i;index % _table.size();i;}_table[index]._kv kv;_table[index]._state EXIST;_n;return true;
}删除
删除的过程非常简单
查找指定 key找到了就将其状态设为 DELETE并减少表中元素个数
/// brief 删除指定 key 值
/// param key 待删除节点的 key
/// return 删除成功返回 true失败返回 false
bool Erase(const K key) {Elem* res Find(key);if (res ! nullptr) {res-_state DELETE;--_n;return true;}return false;
}开散列
接口总览
template class K, class V
class HashTable {struct Elem {Elem(const pairK, V kv) : _kv(kv), _next(nullptr){}pairK, V _kv;Elem* _next;};
public:Elem* Find(const K key);bool Insert(const pairK, V kv);bool Erase(const K key);
private:vectorElem* _table;size_t _n 0;
};节点的结构
使用链地址法解决哈希冲突就不再需要伪删除了但需要一个指针指向相同索引的下一个节点。
/// brief 哈希表的节点
struct Elem {Elem(const pairK, V kv) : _kv(kv), _next(nullptr){}pairK, V _kv; // 存储数据Elem* _next; // 存在下一节点地址
};查找
查找的实现比较简单
利用散列函数获取映射后的索引遍历该索引位置的链表
/// brief 查找指定 key
/// param key 待查找节点的 key 值
/// return 找到返回节点的指针没找到返回空指针
Elem* Find(const K key) {if (_table.empty()) {return nullptr;}size_t index key % _table.size();Elem* cur _table[index];// 遍历该位置链表while (cur ! nullptr) {if (cur-_kv.first key) {return cur;}cur cur-_next;}return nullptr;
}插入
开散列下的插入比闭散列简单
首先检查待插入的 key 值是否存在其次需要检查是否需要扩容将新节点以头插方式插入
/// brief 插入节点
/// param kv 待插入的节点
/// return 插入成功返回 true失败返回 false
bool Insert(const pairK, V kv) {// 检查是否已经存在Elem* res Find(kv.first);if (res ! nullptr) {return false;}// 检查是否需要扩容if (_table.size() _n) {vectorElem* backUp;size_t newSize _table.size() 0 ? 10 : 2 * _table.size();backUp.resize(newSize);// 遍历原哈希表将所有节点插入新表for (int i 0; i _table.size(); i) {Elem* cur _table[i];while (cur ! nullptr) {// 取原哈希表的节点放在新表上不用重新申请节点Elem* tmp cur-_next;size_t index cur-_kv.first % backUp.size();cur-_next backUp[index];backUp[index] cur;cur tmp;}_table[i] nullptr;}_table.swap(backUp);}// 将新节点以头插的方式插入size_t index kv.first % _table.size();Elem* newElem new Elem(kv);newElem-_next _table[index];_table[index] newElem;_n;return true;
}删除
开散列的删除与闭散列有些许不同
获取 key 对应的索引遍历该位置链表找到就删除
/// brief 删除指定 key 值
/// param key 待删除节点的 key
/// return 删除成功返回 true失败返回 false
bool Erase(const K key) {size_t index key % _table.size();Elem* prev nullptr;Elem* cur _table[index];while (cur ! nullptr) {if (cur-_kv.first key) {if (prev nullptr) {// 是该位置第一个节点_table[index] cur-_next;} else {prev-_next cur-_next;}delete cur; // 释放该节点--_n;return true;}prev cur;cur cur-_next;}return false;
}
