作者: 努力学习的少年
个人简介: 双非大二, 一个正在自学 c++ 和 Linux 操作系统, 写博客是总结知识, 方便复习.
目标: 进大厂
如果你觉得文章可以的话, 麻烦你给我点个赞和关注, 感谢你的关注!
种一颗树最好是 10 年前, 其次是现在.
目录
哈希概念
哈希函数
直接定址法
除留余数法
哈希冲突
闭散列 ---------- 开发定址法
闭散列的实现
开散列 -------- 哈希桶
开散列的增容
开散列的实现
哈希概念
用某个函数直接将元素映射到一个顺序结构中, 查找的时候通过映射关系直接找到该值. 这个映射函数叫做哈希函数.
哈希函数
设计哈希函数常用有两种方法: 直接定址法和除留余数法
直接定址法
取关键字的某个线性函数为散列地址: Hash(Key)= A*Key + B
优点: 简单, 均匀
缺点: 需要事先知道关键字的分布情况 使用场景: 适合查找范围集中且已知范围
如下这题就直接使用直接定址法:
该题直接采用直接定址法, 已知该题只包含小写字母, 所以直接创建一个大小为 26 的数组直接映射小写字母即可, 然后遍历字符串, 统计字符串中的小写字母出现的次数, 然后再遍历一遍字符串, 通过字符哈希映射关系, 直接找到第一个只出现一次的字符.
- class Solution {
- public:
- char firstUniqChar(string s) {
- int arr[26]={0};
- for(auto c:s)// 遍历一遍字符串, 统计 s 中字符的个数
- {
- arr[c-'a']++;
- }
- for(auto c:s)// 再遍历一遍字符串, 找出第一个只出现一次的字符
- {
- if(arr[c-'a']==1)
- return c;
- }
- return ' ';
- }
- };
时间复杂度: O(N)
空间复杂度: 因为我们只定义出一个 arr[26] 的数组, 所以空间复杂度为 O(1),
该题是直接将 0~25 映射出 a~z 这 26 个字母, 这种方式叫做直接定址法.
该方式的优点是: 效率高, 通过某个数字直接映射出某个字符.
缺点: 只适用于整数, 字符且范围较小的映射, 浮点数或者范围很广的映射不适用.
除留余数法
假设需要映射一些范围很广的元素, 可以将这个范围很广的数组缩小到一个哈希数组里进行映射, 也就是说映射该数的位置 = 该数 % 哈希表数组的大小, 这就是除留余数法.
例如我们的哈希数组的大小是 10, 所以我们可以将映射的每个元素进行 %10, 那么哈希数组中的范围映射位置是 0~9, 如下, 将下列的数组映射到哈希表中.
哈希冲突
简单来说, 哈希冲突就是不同的值映射到相同的位置
上面的除留余数法就会发生哈希冲突, 例如:
100 和 10 放在大小为 10 的哈希数组中, 那么它们都 %10 之后都是 0, 这就是哈希冲突.
解决哈希冲突常用有两种方法, 闭散列和开散列.
闭散列 ---------- 开发定址法
如果哈希表未满, 然后未被装满, 说明哈希表必然存在空位置, 那么可以把 key 值放在冲突的下一个空位置. 例如:
查找空位置的方式有线性探测和二次探测:
线性探测: 从冲突位置上往后一个一个查找空位置
例如: 上面的 10 映射到哈希表中, 它经过 1,12,3 最终在 4 的位置找到空位置, 往后一个一个查找就是线性探测, 线性探测一旦发生哈希冲突, 所有的冲突连在一起, 容易产生数据 "堆积", 即: 不同关键码占据了可利用的空位置, 使得寻找某关键码的位置需要许多次比较, 导致搜索效率降低., 例如: 当我们要查找 10 这个数据的时候, 我们需要踏过 1,12,3 这三个数据, 查找效率较低.
二次探测: 从冲突位置上往后以 n^2 进行查找空位置. n={1,2,3,4...}
查找值的时候, 也是按二次探测开始查找, 走到空时, 说明查找不到.
如下:
二次探测相对分散一些, 不容易发生踩踏事件.
思考:
哈希什么时候下进行增容? 如何增容?
散列表中载荷因子的定义: a = 哈希表填入的元素个数 / 哈希表的容量
a 越大, 填入表中的元素个数越多, 冲突可能性越大, 查找效率较低, 反之, a 越小, 冲突的可能性越小, 查找效率较高, 为了保证查找效率, 载荷因子到一定的数之后, 哈希表就要增容, 正常情况下, 载荷因子控制在 0~0.8, 超过 0.8, 则查找效率会很低.
闭散列的实现
1. 闭散列需要定义定义一个枚举数组来判断哈希表上位置的状态.
- enum State// 标识哈希表中位置的状态
- {
- EMPTY,// 空
- EXITS,// 存在
- DLETE// 删除
- };
2. 定义一个哈希表存储的数据结构体, 一个是存储的数据, 一个是存储的状态, 状态默认为空.
- template<class K,class V>
- class HashData// 哈希位置的数据
- {
- public:
- pair<K, V> _kv;// 哈希表上映射的数据
- State _state = EMPTY;// 位置上的状态
- };
3. 哈希表的定义
- namespace sjp
- {
- enum State// 标识哈希表中位置的状态
- {
- EMPTY,// 空
- EXITS,// 存在
- DLETE// 删除
- };
- template<class T>
- struct HashFunc// 哈希仿函数, 用来转化为整数, 才能进行除留余数
- {
- size_t operator()(const T& k)
- {
- return k;
- }
- };
- template<>//string 仿函数的模板特化
- struct HashFunc<string>
- {
- // 将字符变成对应的整形值
- //BKDRHAXI 每次加上一个数, 在乘上 131
- // 近似唯一
- size_t operator()(const string& st)
- {
- size_t ret = 0;
- for (auto e : st)
- {
- ret += e;
- ret *= 131;
- }
- return ret;
- }
- };
- template<class K,class V>
- class HashData// 哈希位置的数据
- {
- public:
- pair<K, V> _kv;// 哈希表上映射的数据
- State _state = EMPTY;// 位置上的状态
- };
- template<class K, class V, class HashFunc= HashFunc<K>>// 仿函数
- class HashTable
- {
- public:
- bool Insert(const pair<K, V>& kv)
- {
- if (find(kv.first) != NULL)// 如果 kv 值在_table, 则插入失败
- return false;
- if (_table.capacity() == 0)
- {
- _table.resize(10);
- }
- else if ((double)_n /(double) _table.size()>=0.7)// 计算负载因子
- {
- // 大于负载因子, 哈希表进行增容
- HashTable<K, V, HashFunc> newHT;// 创建新的哈希表并未原来的两倍
- newHT._table.resize(_table.size() * 2);
- for (auto& e : _table)// 将旧表中数据一个一个的映射到新表中
- {
- if (e._state == EXITS)
- {
- newHT.Insert(e._kv);// 在运行 insert, 相当于复用了 insert
- }
- }
- _table.swap(newHT._table);// 最后将 newHT.table 和本身的 table 交换即可
- }
- // 位置得模上 size()
- HashFunc hf;
- size_t index = hf(kv.first)%_table.size();
- size_t i = 1;
- int start = index;
- // 探测后面的位置 -- 线性探测 or 二次探测
- while (_table[index]._state == EXITS)// 发生冲突, 探测下一个位置
- {
- i += 1;
- index =start+i*1;// 进行二次探测
- index %= _table.size();
- }
- _table[index]._kv = kv;
- _table[index]._state = EXITS;
- ++_n;
- return true;
- }
- HashData<K, V>* find(const K& k)// 查找函数
- {
- HashFunc fc;// 仿函数
- if (_table.size()== 0)// 防止除 0
- return nullptr;
- int index = fc(k) % _table.size();
- int i = 1;
- while (_table[index]._state !=EMPTY )// 如果找到的位置不为空, 则继续往下找
- {
- // 找到了需要判断该值是否存在, 有可能被删除掉
- if (_table[index]._state == EXITS&&_table[index]._kv.first == k)
- {
- return &_table[index];
- }
- else
- {
- index += i;
- index %= _table.size();
- }
- }
- return NULL;
- }
- bool erase(const K& k)// 删除数据
- {
- HashData<K, V>* kv = find(k);// 查找 key 值
- if (kv == NULL)// 找不到, 则删除失败
- {
- return false;
- }
- else if (kv != NULL)// 找到了
- {
- kv->_state = DLETE; // 直接将该位置的状态设置为 DLETE, 假删除
- return true;
- }
- }
- private:
- vector<HashData<K,V>> _table;
- size_t _n=0;// 存储有效数据的个数
- };
- }
为了让各个类型都能映射到哈希表中, 需要创建一个仿函数的类模板, 该仿函数可以将 char 和 int 等直接转换为整数.
- template<class K>
- struct Hash// 将数据转换为整数的仿函数
- {
- size_t operator()(const K& k)
- {
- return k;
- }
- };
为了让 string 类型也能映射到哈希表里面, 所以我们需要将 string 转化为整数, 这样才能 % 某个数找到相应的位置, 所以我们需要对上面的仿函数进行模板的特化,. 如下:
- template<>// 模板的特化, 将 string 的转换为整数
- struct Hash<string>
- {
- size_t operator()(const string& s)
- {
- int ret = 0;
- for (auto c : s)
- {
- ret += c;
- }
- return ret;
- }
- };
当然, 这样将 string 中的字符相加起来后, 不同的 string 会发生冲突, 例如:
"abbc" 和 "acbb" 或者 "abcd" 和 "aadd" 它们的转化成整数是冲突的.
所以可以相加每个字符后 * 131, 这样使我们 string 转化成整数的冲突概率变得极低.
- template<>// 模板的特化, 将 string 的转换为整数
- struct Hash<string>
- {
- size_t operator()(const string& s)
- {
- int ret = 0;
- for (auto c : s)
- {
- ret += c;
- ret *= 131;
- }
- return ret;
- }
- };
然后将仿函数传入到模板列表中, 这样我们哈希表默认可以会对 string,char 等进行整形转化
template<class K, class V,class Hash=Hash<K>>
如果有其它类型需要转化成仿函数, 我们也可以自定义一个仿函数将它传进我们类模板中.
开散列 -------- 哈希桶
概念:
开散列概念开散列法又叫链地址法 (开链法), 首先对关键码集合用散列函数计算散列地址, 具有相同地址的关键码归于同一子集合, 每一个子集合称为一个桶, 各个桶中的元素通过一个单链表链接起来, 各链表的头结点存储在哈希表中.
如下: 将下面的数组
我们将映射相同位置的值用一个单链表连接起来, 各链表的头节点存储在哈希表中, 将每条链表称为一个桶. 其中链表的插入删除是进行头插, 因为头插的效率是 O(1).
开散列的增容
桶的个数是一定的, 随着数据的不断的插入, 冲突的概率越来越高, 每个桶的元素不断增加, 那么映射效率越低, 当每个桶的元素是只有一个元素时, 映射效率时最高的, 当元素个数等于桶的个数时, 可以给哈希表继续增容.
开散列的实现
- template<class K, class V,class Hash=Hash<K>>
- class HashTable
- {
- typedef HashData<K, V> node;
- public:
- bool insert(const pair<K, V>& kv)// 插入
- {
- if (find(kv.first) != nullptr)// 哈希表中的 k 值不允许重复
- return false;
- if (_table.capacity() == 0)// 如果容量为 0, 则哈希表初始化 10 个空间
- {
- _table.resize(10,0);
- }
- else if (_n / _table.size()>= 1)// 哈希表中的元素大于
- {
- HashTable<K,V> newtable;// 创建一个新的哈希表
- newtable._table.resize(_table.size() * 2);//newtable 的大小为_table 的两倍
- for (auto& c : _table)// 将_table 中的元素映射到 newtable 中
- {
- node* cur = c;//c 是每个链表的头节点
- while (cur)
- {
- newtable.insert(cur->_kv);
- cur=cur->_next;
- }
- }
- _table.swap(newtable._table);// 交换两个表格, 完成增容
- }
- node* newnode = new node(kv);// 创建新的节点
- Hash hs;
- int index = hs(kv.first) % _table.size();// 找到映射的位置
- node* cur = _table[index];// 新的节点进行头插
- newnode->_next = cur;
- _table[index] = newnode;
- _n++;// 有效数据加 1
- return true;
- }
- node* find(const K& k)// 查找
- {
- if (_table.size() == 0)// 如果哈希表的空间为 0, 则直接返回
- return nullptr;
- Hash hs;
- int index = hs(k) % _table.size();// 找到该值在哈希表对应的映射位置
- // 在该位置上的链表进行查找
- node* cur = _table[index];
- while (cur)
- {
- if (cur->_kv.first == k)// 找到了
- return cur;
- else
- {
- cur = cur->_next;
- }
- }
- return nullptr;// 找不到
- }
- bool erase(const K& k)// 删除
- {
- if (_table.size() == 0)
- return false;
- Hash hs;
- int index = hs(k) % _table.size();// 找到该值在哈希表对应的映射位置
- node* pre = nullptr;//cur 前面的一个节点
- node* cur = _table[index];
- while (cur)
- {
- if (cur->_kv.first == k)// 找到了
- {
- if (pre == nullptr)// 头节点删除
- {
- _table[index] = cur->_next;
- }
- else// 中间节点删除
- {
- pre->_next = cur->_next;
- }
- delete cur;
- cur = nullptr;
- _n--;
- return true;
- }
- else
- {
- pre = cur;
- cur = cur->_next;
- }
- }
- return false;// 找不到, 删除失败
- }
- private:
- vector<node*> _table;// 哈希表
- size_t _n;// 计算哈希表中有多少个有效元素
- };
- }
思考: 在极端情况下, 如果所有的数都映射在一个桶, 且没有到达有效数据个数小于哈希表的大小, 此时的查找的效率是 O(N), 请问有什么解决方法可以提高查找效率.
由于哈希表中的有效元素未达到哈希表的容量, 所以就没办法增容, 为了防止链表的太长, 我们可以将限制链表的长度, 如果链表大于该长度, 我们把该链表转化为红黑树, 例如我们可以 设置链表的最大长度为 8, 如果大于该长度, 在将该链表转换为红黑树.
若文章出现错误, 随时欢迎你帮我指正, 若文章对你有所帮助, 麻烦你给我点个关注!!!
来源: https://blog.csdn.net/sjp11/article/details/122477041