企业官网建设流程全解析

目录

一. 哈希概念

1.1 直接定址法

1.1.1 概念

1.1.2 题目示例

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

二. 哈希的一些概念

2.1 哈希冲突

2.2 负载因子

2.3 将关键字转为整数

2.4 哈希函数

2.4.1 除法散列法 / 除留余数法

2.4.2 乘法散列法

2.4.3 全域散列法

三. 处理哈希冲突

3.1 开放定址法

3.1.1 线性探测

3.1.2 二次探测法

3.1.3 双重散列

3.2 开放定址法的实现

3.2.1 key不能取模问题

3.2.2 key 能否比较相等的问题

3.2.3 扩容问题

3.2.4 代码实现

3.3 链定址法

3.3.1 扩容问题

3.3.1.1 极端情况

3.3.2 代码实现

一. 哈希概念

哈希(hash)又称散列，故哈希表又称散列表，是一种组织数据的方式。哈希是音译名，从译名来看，有散乱排列（散列）的意思。哈希的本质就是通过哈希函数把关键字Key跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进行快速查找。

1.1 直接定址法

1.1.1 概念

当关键字的范围比较集中时，直接定址法是非常简单高效的方法：比如一组关键字都在[0，99]之间，那么我们开一个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母，那么我们开一个26个数的数组，每个关键字acsii码-aascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们不仅在计数排序部分用过，在string部分的OJ题目那里也用过了.

1.1.2 题目示例

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution { public: int firstUniqChar(string s) { // 每个字⺟的ascii码-'a'的ascii码作为下标映射到count数组，数组中存储出现的次数 int count[26] = { 0 }; // 统计次数 for (auto ch : s) { count[ch - 'a']++; } for (size_t i = 0; i < s.size(); ++i) { if (count[s[i] - 'a'] == 1) return i; } return -1; } };

二. 哈希的一些概念

2.1 哈希冲突

直接定址法的缺点也非常明显，当关键字的范围比较分散时，就很浪费内存甚至内存不够用。假设我们只有数据范围是[0，9999]的N个值，我们要映射到一个M个空间的数组中（一般情况下M >= N），那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这里要注意的是h(key)计算出的值必须在[O , M)之间。

这里存在的一个问题就是，两个不同的key可能会映射到同一个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。

2.2 负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子 = N / M，负载因子有些地方也翻译为载荷因子/装载因子等，他的英文为loadfactor。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。

2.3 将关键字转为整数

我们将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后面代码实现中再进行细节展示。下面哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。

2.4 哈希函数

好的哈希函数能让 key 均匀分布，减少冲突，常用设计方法如下：

2.4.1 除法散列法 / 除留余数法

1、除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

2、当使用除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是2^X，key % 2^X本质相当于保留key的后X位（后X位相同的值），计算出的哈希值都是一样的——就冲突了。比如：[63，31}看起来没有关联的值，如果M是16，也就是2^4，那么计算出的哈希值都是15，因为63的二进制后8位是00111111，31的二进制后8位是00011111。如果是10^x，就更明显了，保留的都是10进值的后X位，如：[112,12312}，如果M是100(10^2)，计算出的哈希值都是12。

3、当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数（素数）

2.4.2 乘法散列法

乘法散列法对哈希表大小M没有要求，这里介绍一下大思路，第一步：用关键字K乘上常数A（0 < A < 1)，并抽取出k*A的小数部分；第二步：后再用M乘以k * A的小数部分，再向下取整。

h(key) = floor(M * ((A * key) % 1.0))，其中floor表示对表达式进行下取整，A(0 , 1)，%1.0是为了取小数，这里最重要的是A的值应该如何设定，Knuth——这又是一位大佬——他认为A = (5 - 1) / 2 = 0.6180339887...（黄金分割点)比较好。

乘法散列法对哈希表大小M是没有要求的，假设M为1024，key为1234，A = 0.6180339887，A * key = 762.6539420558，取小数部分为0.6539420558,M * ((A * key) % 1.0) = 0.6539420558*1024 = 669.6366651392，那么h(1234) = 669。

2.4.3 全域散列法

如果存在这样一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中——这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。

hab(key) = ((a * key + 6) % P) % M，P需要选一个足够大的质数，a可以随机选[1 , P - 1]之间的
任意整数，b可以随机选[0 , P - 1]之间的任意整数，这些函数构成了一个P * (P - 1)组全域散列函数组。假设P = 17，M = 6，a = 3，b = 4,则h34(8) = ((3 * 8 + 4) % 17) % 6 = 5。

需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查
改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，
查找又是另一个散列函数，就会导致找不到插入的key了。

三. 处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，因为冲突是避免不了的，我们只能减少冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放定址法和链地址法。

3.1 开放定址法

在开放定址法中所有的元素都放到哈希表里，当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于的。这里的规则有三种：线性探测、二次探测、双重探测。

3.1.1 线性探测

enum state { EXIST, EMPTY, DELETE }; template<class K, class V> class HashData { public: pair<K, V> _kv; state _state = EMPTY; }; template<class K,class V> class HashTable { public: HashTable() :_tables(11) ,_n(0) {} bool insert(const pair<K, V>& kv) { if (find(kv.first)) { return false; } //负载因子 >= 0.7 扩容 if (_n * 1.0 / _tables.size() >= 0.7) { HashTable<K, V> newht; newht._tables.resize(_tables.size() * 2); 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; while (_tables[hashi]._state == EXIST) { hashi = (hash0 + i) % _tables.size(); i++; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; } HashData<K, 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) { HashData<K, V>* ret = find(key); if (ret) { ret->_state = DELETE; _n--; return true; } return false; } private: vector<HashData<K, V>> _tables; size_t _n; };

3.1.2 二次探测法

enum state { EXIST, EMPTY, DELETE }; template<class K, class V> class HashData { public: pair<K, V> _kv; state _state = EMPTY; }; template<class K,class V> class HashTable { public: HashTable() :_tables(11) ,_n(0) {} bool insert(const pair<K, V>& kv) { if (find(kv.first)) { return false; } //负载因子 >= 0.7 扩容 if (_n * 1.0 / _tables.size() >= 0.7) { HashTable<K, V> newht; newht._tables.resize(_tables.size() * 2); for (auto& data : _tables) { if (data._state == EXIST) { newht.insert(data._kv); } } _tables.swap(newht._tables); } size_t hash0 = kv.first % _tables.size(); int hashi = hash0; size_t i = 1; int flag = 1; while (_tables[hashi]._state == EXIST) { hashi = (hash0 + i*i*flag) % _tables.size(); if (hashi < 0) { hashi += _tables.size(); } if (flag == 1) { flag = -1; } else { flag = 1; i++; } } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; } HashData<K, V>* find(const K& key) { size_t hash0 = key % _tables.size(); int hashi = hash0; size_t i = 1; int flag = 1; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi = (hash0 + i*i*flag) % _tables.size(); if (hashi < 0) { hashi += _tables.size(); } if (flag == 1) { flag = -1; } else { flag = 1; i++: } } return nullptr; } bool erase(const K& key) { HashData<K, V>* ret = find(key); if (ret) { ret->_state = DELETE; _n--; return true; } return false; } private: vector<HashData<K, V>> _tables; size_t _n; };

3.1.3 双重散列

3.2 开放定址法的实现

3.2.1 key不能取模问题

当key是string / Date等类型时，key不能取模，我们需要给HashTable增加一个仿函数，这个仿函数支持把key转换成一个可以取模的整型，如果key可以转换为整型并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整型，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整型值不同。string做哈希表的key非常常见，所以我们可以考虑把string特化一下——

template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> struct HashFunc<string> { // 字符串转换成整形，可以把字符ascii码相加即可 // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 // 这里我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以一个质数，这个质数一般取31, 131等效果会比较好 size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash *= 131; hash += e; } return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: private: vector<HashData<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 };

3.2.2 key 能否比较相等的问题

当 key 为Date等类型时，我们可能面临比较相等的问题，我们既可以在 Date 类中就实现相等的重载，也可以像取模问题一样传入一个仿函数。

class Date { public: Date(int year, int month, int day) :_year(year) , _month(month) , _day(day) {} Date() = default; bool operator==(const Date& date)const { return _year == date._year && _month == date._month && _day == date._day; } int _year; int _month; int _day; };

3.2.3 扩容问题

这里我们哈希表负载因子控制在0.7，当负载因子到0.7以后我们就需要扩容了，我们还是按照2倍的方式扩容，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2倍后就不是质数了。如何解决？一种方案就是上面在【除法散列法】中我们介绍过的JavaHashMap的使用2的整数次幂，但是计算时不能直接取模的改进方法；另外一种方案是SGI版本的哈希表使用的方法，给了一个近似2倍的质数表，每次去质数表获取扩容后的大小。

// 质数表(SGI STL 同款，用于扩容) 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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; // >= n const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; }

3.2.4 代码实现

// 质数表(SGI STL 同款，用于扩容) 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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; // >= n const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } template<class K> class HashFunc { public: size_t operator()(const K& key) { return (size_t)key; } }; template<> class HashFunc<string> { public: size_t operator()(const string& str) { size_t hash = 0; for (auto ch : str) { hash += (size_t)ch; hash *= 131; } return hash; } }; namespace OpenAddress { // 状态标识 enum State { EMPTY, // 空位置 EXIST, // 已存储元素 DELETE // 已删除元素 }; // 哈希表结点结构 template<class K, class V> struct HashData { pair<K, V> _kv; // 存储key-value对 State _state = EMPTY; //初始状态为空 }; // 开放定址法哈希表(线性探测) template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: // 构造函数(初始化哈希表大小为第一个质数) HashTable() :_tables(__stl_next_prime(1)) {} // 插入 key-value对(去重) bool Insert(const pair<K, V>& kv) { // 1.先查找，避免重复插入 if (Find(kv.first)) return false; // 2.负载因子 >=0.7，扩容 if ((double)_n / (double)_tables.size() >= 0.7) { HashTable<K, V, Hash> newht; newht._tables.resize(__stl_next_prime(_tables.size() + 1)); // 3.迁移旧表元素到新表 for (size_t i = 0; i < _tables.size(); i++) { // 遍历旧表，旧表数据插入到newht if (_tables[i]._state == EXIST) { newht.Insert(_tables[i]._kv); } } // 4.交换新旧表 _tables.swap(newht._tables); } // 5.线性探测找空闲位置 Hash hs; size_t hash0 = hs(kv.first) % _tables.size(); // 线性探测 size_t i = 1; size_t hashi = hash0; while (_tables[hashi]._state == EXIST) { // 冲突，线性探测下一个位置 hashi = (hash0 + i) % _tables.size(); ++i; } // 6.插入元素 _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; } // 查找key，返回节点指针(nullptr表示未找到) HashData<K, V>* Find(const K& key) { Hash hs; size_t hash0 = hs(key) % _tables.size(); // 线性探测 size_t i = 1; size_t hashi = hash0; // 遇到EMPTY才停止查找(DELETE继续探测) while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } // 线性探测下一个位置 hashi = (hash0 + i) % _tables.size(); ++i; } return nullptr; } // 删除key(仅修改状态为DELETE,不实际删除元素) bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { // 标记为 DELETE,避免影响后续查找 ret->_state = DELETE; --_n; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; // 哈希表数组 size_t _n = 0;// 已存储的数据个数 };

3.3 链定址法

3.3.1 扩容问题

开放定址法负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。stl中unordered_xxx的最大负载因子基本控制在1（负载因子平均是1，但是这是理想的情况，当然没有那么平均，有的哈希桶不挂，有的挂2~3个），大于1就扩容，艾莉丝之后在代码实现中也使用这个方式进行扩容。

3.3.1.1 极端情况

3.3.2 代码实现

namespace Hash_bucket { template<class K,class V> class HashNode { public: HashNode(const pair<K,V>& kv) :_kv(kv) ,_next(nullptr) {} pair<K, V>_kv; HashNode<K, V>* _next; }; template<class K,class V,class Hash=HashFunc<K>> class HashTable { private: typedef HashNode<K, V> Node; public: HashTable() :_tables(__stl_next_prime(1)) {} HashTable(const HashTable<K,V,Hash>& oldht) :_tables(oldht._tables.size()) { for (size_t i = 0; i < oldht._tables.size(); i++) { Node* cur = oldht._tables[i]; while (cur) { Insert(cur->_kv); cur = cur->_next; } } } HashTable<K, V, Hash>& operator=(HashTable<K, V, Hash> ht) { _tables.swap(ht._tables); _n = ht._n; return *this; } ~HashTable() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; Node* lat = cur; while (cur) { lat = lat->_next; delete cur; cur = lat; } _tables[i] = nullptr; } } bool Insert(const pair<K, V> kv) { if (Find(kv.first)) { return false; } Hash hash; //负载因子==1时扩容 if (_n == _tables.size()) { vector<Node*> newTable(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hash0 = hash(cur->_kv.first) % newTable.size(); cur->_next = newTable[hash0]; newTable[hash0] = cur; cur = next; } _tables[i] = nullptr; } } size_t hash0 = hash(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[hash0]; _tables[hash0] = newnode; _n++; return true; } Node* Find(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } bool Erase(const K& key) { Hash hash; size_t hash0 = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; size_t _n = 0;; }; }