c++学习之---哈希表的实现(开放定址法和链地址法)
目录
哈希表简介:
哈希表的框架设计:
1`映射的大致过程 :
2`哈希函数:
3`哈希表结构设计 :
开放定址法:
1`除留余数法:
2`除留余数法的除数(每次的映射区间大小):
3` 线性探测法:
4`负载因子:
5`Insert()的实现:
6`Erase()的实现(主要是Find())
7`采用开放定址法的哈希表代码实现:
链地址法:
1`被淘汰的开放定址法法:
2 `和开放定址法的相似和相异:
3`Insert函数的实现:
4`Find()的实现:
5`Erase()的实现:
6`析构函数的实现:
7`拷贝构造函数的实现:
8`赋值重载函数的实现:
9`采用链地址法的哈希表(哈希桶)完整代码实现:
哈希表简介:
哈希表是C++ STL中unordered_set和unordered_map的底层实现结构，其插入、查找和删除操作的平均时间复杂度均为O(1)，具有极高的运行效率。
哈希表是数据结构 , 哈希则是一种算法 , 提供类似于数学函数的功能---接受一个值 , 输出一个唯一不重复的值(理想情况) .
哈希的英文术语是"hash" , 其本意包含散乱的含义 , 即通过哈希函数映射产生的数据会均匀分布在特定范围内 . 因此 , 基于这一特性设计的哈希表也被称为散列表.
哈希表的框架设计:
1`映射的大致过程 :
假设我们要往哈希表里存入一组整形值 : {19, 30 , 5 , 36 ,13 , 20 , 21 ,12 }. 那经过哈希函数(后面再详细说明)的映射后就会是如下的结果 :
上面的h(x) = y 就是一种抽象的哈希函数的表达形式 , x是映射之前的值 , y是映射后的值 . 如下图所示 , 被映射后的y值就存储在相应的数组下标处 :
但是 , 可以发现在最上面哈希函数的映射里 , 19和30这位两个相异的数却在映射后成了相同的哈希值 , 这种现象称为"哈希冲突" . 哈希冲突无法避免 , 只能通过设计优秀的哈希函数来减少冲突 .
即便是出现了哈希冲突 , 也可以看到19和18在数组中没有挤在一起 , 而是让后映射的30找到了随后的空位置来存放 . 这个过程叫做"处理哈希冲突" , 处理哈希冲突的方法也是哈希表设计过程中的重要部分.
2`哈希函数:
在哈希算法中，key值最终需要转换为整数并取模后才能作为数组下标进行映射。然而在实际应用中，key值并不总是可以直接取模的整型，这时就需要通过哈希函数将其他类型的值转换为整型后再取模。
- 如果key是 负数/浮点数 , 那可以将其强转为size_t类型
- 如果key是string , 就需要特定的算法并借助仿函数将其转化为整形. 比如著名的BKDR算法 , 如下:
- 如果key是其他自定义类型 , 就需要根据实际的情况来编写仿函数以达到获取合适哈希值的效果了
//哈希函数(将key转换为整形)
template<class Key>
struct HashFunc
{size_t operator()(const Key& key){return key;}
};
//哈希函数(string作key很常见,所以特化一个)
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t ret = 0;for (auto& au : key){ret += au;ret *= 131;}return ret;}
};
//////////////////////////////////////////////////////////////
//使用
HashFunc hfc //提前声明仿函数对象
hfc(key) //调用仿函数并传入key值后 , 返回一个处理过后的整形 , 能够直接取模3`哈希表结构设计 :
- 操作的时间复杂度要想和O(1)沾边 , 那多多少少得和数组扯上一点关系 . 哈希的底层是以数组为基础来存储数据的.
- 哈希表在存储数据时难免会出现哈希冲突 , 即不同的值映射到数组中的同一位置 . 因此，在插入新元素时，需要通过特殊的状态标识符（存在/被删除/为空）来判断是该直接插入当前位置，还是解决冲突后插入其他位置。
- 考虑到数组操作的需求 , 为了简化实现 , 我们选择vector作为底层容器 ; 但是 , vector仅支持在外部线性追加元素 , 这与哈希表通过哈希函数分散存储的特性存在矛盾 . 为此我们需要预先分配并初始化vector的存储空间 ; 正因如此 , vector自带的size方法不再适用 , 必须而外再维护一个成员变量来跟踪记录实际存储的元素数量 .
//用三个枚举值来表示存在/移除/空缺等三种位置的状态
enum State
{EXIST,REMOVE,EMPTY
};
//哈希内部vector每个元素 : 一个键值对和一个此元素的状态标识符
template<class Key , class Val>
struct HashData
{pair<Key, Val> _item;State _state;
};template<class Key , class Val>
class HashTable
{
public:using Data = HashData<Key, Val>;
private:vector<Data> _table; //底层使用vector来简化数组操作int _size; //手动最终一段范围内实际存在的元素
};开放定址法:
1`除留余数法:
除留余数法是最基本的一种哈希函数 , 它通过取模操作符 , 将元素严格的限定在指定数组区间内(类似于用数组实现循环队列时的做法).
假设规定的数组空间是11个元素 , 那将插入的元素模上11后得到的结果就是一个不超过10的值,如下 :
2`除留余数法的除数(每次的映射区间大小):
既然除留余数法的核心在于模上已初始化空间的容量来得到更为分散的哈希值 , 那这个数就必须很有讲究了 . 一般而言 , 使用素数作为除数更能达到分散哈希值的目的 .
- 忌讳用2的整数幂做除数 , 因为这些除数的二进制位中0占了大多数 , 会导致模出来的结果有很多重复值. (类似于10进制里 , 一万和一百万模上100都等于100,而一万和一百万相差的可远了)
- STL在实现时 , 使用了一个看起来及其原始 , 类似打标的方式定义了这个除数的大小,如下:
//这个函数里定义的数组元素都是素数,每个素数之间正好又能满足2倍扩容的需求,这样的空间也适合做除数 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; }
3` 线性探测法:
- 线性探测法是最基本的一种解决哈希冲突的方法 .
- 通过哈希函数映射出哈希值后到对应数组下标后 , 如果判断出当前位置直接就是"空"状态(EMPTY) , 则没有出现哈希冲突,直接插入 .
- 如果判断出当前位置是"存在"状态(EXIST) , 则出现哈希冲突 , 需要线性增加哈希值来检查随后数组位置的状态标识符 , 只有否为"空"状态(EMPTY)或"以移除"状态(REMOVE)才能插入.
- 并且要时刻用vector中已初始化的空间(通过vector的size()获取)来模上哈希值 , 防止越界访问.
4`负载因子:
- 毕竟底层是用vector来存储 , 而且哈希对于vector空间的使用是一次性开辟和初始化一块空间 , 然后在这一块里分散的填充数据.
- 随着一段空间不断地被填充 , 空闲的位置越来越少 , 插入的效率也会变低 . 因为线性探测法需要一个一个往后找空闲位置 , 太多的非空位置就形成了"群积现象" , 这又会导致线性探测法要查找多次才能找到空闲位置.
- 通过计算平衡因子 , 并依次来判断合适的扩容时机就很重要 . 负载因子= 已插入元素/已初始化的总空间
- 一般规定平衡因子在0.7左右时扩容最为合适.
5`Insert()的实现:
//插入
bool Insert(const pair<Key, Val>& input)
{//计算负载因子,决定是否扩容if (_size * 10 / _table.size() > 7){HashTable<Key, Val> newTable;newTable._table.resize(__stl_next_prime(_table.size() + 1));for (auto& au : _table){if (au._state == EXIST)newTable.Insert(au._item);}_table.swap(newTable._table);}//计算哈希值,并检测和解决哈希冲突int hashKey = input.first % _table.size();while (_table[hashKey]._state == EXIST){//hashKey = (hashKey + 1) % (_table.size());hashKey = (hashKey + 1) % (_table.size());}//找到合适的哈希值后,填入新数据_table[hashKey]._item = input;_table[hashKey]._state = EXIST;_size += 1;return true;
}6`Erase()的实现(主要是Find())
//查找(可以单独用,也可以给下面的Erase()来用)
Data* Find(Key key)
{int hashKey = key % (_table.size());while (_table[hashKey]._state != EMPTY){if (_table[hashKey]._state == EXIST && _table[hashKey]._item.first == key){return &_table[hashKey]._item;}hashKey = (hashKey + 1) % (_table.size());}return nullptr;
}
//删除
bool Erase(Key key)
{Data* ret = Find(key);if (ret != nullptr){ret->_state = REMOVE;return true;}else{return false;}
}7`采用开放定址法的哈希表代码实现:
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;
}namespace OpenAddress
{//枚举状态值enum State{EXIST,REMOVE,EMPTY};//哈希表的元素定义(包含元素标识符)template<class Key , class Val>struct HashData{pair<Key, Val> _item;State _state = EMPTY;};//哈希函数(将key转换为整形)template<class Key>struct HashFunc{size_t operator()(const Key& key){return key;}};//哈希函数(对于string的特化版本)template<>struct HashFunc<string>{size_t operator()(const string& key){size_t ret = 0;for (auto& au : key){ret += au;ret *= 131;}return ret;}};//哈希表的类定义template<class Key , class Val , class HashFunc = HashFunc<Key>>class HashTable{public:using Data = HashData<Key, Val>;//构造HashTable(){_table.resize(11);_size = 0;}//插入bool Insert(const pair<Key, Val>& input){//计算负载因子,决定是否扩容if (_size * 10 / _table.size() > 7){HashTable<Key, Val> newTable;newTable._table.resize(__stl_next_prime(_table.size() + 1));for (auto& au : _table){if (au._state == EXIST)newTable.Insert(au._item);}_table.swap(newTable._table);}//计算哈希值,并检测和解决哈希冲突//int hashKey = input.first % _table.size();int hashKey = HashFunc()(input.first) % _table.size();while (_table[hashKey]._state == EXIST){//hashKey = (hashKey + 1) % (_table.size());hashKey = (hashKey + 1) % (_table.size());}//找到合适的哈希值后,填入新数据_table[hashKey]._item = input;_table[hashKey]._state = EXIST;_size += 1;return true;}//查找Data* Find(Key key){//int hashKey = key % (_table.size());int hashKey = HashFunc()(key) % _table.size();/*while (_table[hashKey]._state != EXIST){hashKey = (hashKey + 1) % (_table.size());if (_table[hashKey]._state == EMPTY)return nullptr;}return &_table[hashKey];*/while (_table[hashKey]._state != EMPTY){if (_table[hashKey]._state == EXIST && _table[hashKey]._item.first == key){return &_table[hashKey]._item;}hashKey = (hashKey + 1) % (_table.size());}return nullptr;}//删除bool Erase(Key key){Data* ret = Find(key);if (ret != nullptr){ret->_state = REMOVE;return true;}else{return false;}}private:vector<Data> _table;int _size;};
}链地址法:
1`被淘汰的开放定址法法:
开放地址法存在天然的问题 , 在于它天然的逃避哈希值的冲突 , 以至于通过各种探测法解决冲突的过程中不可避免的牺牲了效率 . 因此此处仅仅实现他的大框架以及关键的Insert和Erase函数.
接下来继续学习链地址法。这种方法实现的哈希表也被称为"哈希桶". 这是一个非常形象名称 , 因为发生哈希冲突时，链地址法不会去寻找其他空位，而是直接在当前位置通过单链表将所有冲突的元素链接起来 ; 于是哈希桶的底层存储结构是一个指针数组 , 数组的每个元素都是一个单链表的头结点指针.
2 `和开放定址法的相似和相异:
虽然咱嘴上说着开放定址法不太行 , 但链地址法的实现也是基于他的一些思想来的 .
- 在使用哈希函数来获得哈希值这一点上他俩还是一样的.
- 链地址法不需要像开放定址法法那样为每个元素弄一个存在标识符 , 因为此时不需要通过它来辅助进行冲突的解决 , 而是直接插入对应数组位置的单链表里.
3`Insert函数的实现:
- 和开放定址法类似 , 链地址法同样需要通过哈希函数将key值转化为哈希值的过程.
- 插入时即便发生哈希冲突 , 也只用把新元素头插在对应映射数组位置的单链表里 . 因此以哈希桶为底层数据结构的unordered_set 和 unordered_map等容器的插入效率是O(1)
- 和开放定址法不同 , 链地址法实现的哈希桶在负载因子达到1的时候才要扩容.
- 请注意 , 哈希桶的每个元素都是在堆上动态分配的链表节点 . 在扩容时 , 应将旧哈希桶的节点直接迁移至新哈希桶 , 而非逐个重新插入 . 这种方式能够避免重复申请堆空间和释放就空间带来的性能损耗.
//插入
bool Insert(const pair<Key, Val>& input)
{//避免重复值if (Find(input.first) != nullptr)return false;//判断平衡因子if (_size == _table.size()) //平衡因子为1时扩容,即size/_table.size()==1{vector<Node*> newTable;newTable.resize(__stl_next_prime(_size + 1));for (int i = 0; i < _table.size(); i++) //由于每个元素都是动态开辟的节点,因此将原哈 //希桶的节点挪到新的哈希桶 {if (_table[i] != nullptr){Node* cur = _table[i];while (cur != nullptr){Node* next = cur->_next;size_t hashKey = HashFunc()(cur->_item.first) % newTable.size();cur->_next = newTable[hashKey];newTable[hashKey] = cur;cur = next;}_table[i] = nullptr;}}_table.swap(newTable);}//直接往对应数组位置的单链表头插size_t hashKey = HashFunc()(input.first) % _table.size();Node* newNode = new Node(input);newNode->_next = _table[hashKey];_table[hashKey] = newNode;_size += 1;return true;
}4`Find()的实现:
哈希桶的Find函数实现起来也很简单 , 算出key对应的哈希值后再对应的单链表里遍历就可以 , 效率依然是常数次的O(1) .
//查找
pair<Key, Val>* Find(Key key)
{size_t hashKey = HashFunc()(key) % _table.size();Node* cur = _table[hashKey];while (cur != nullptr){if (cur->_item.first == key)return &cur->_item;cur = cur->_next;}return nullptr;
}5`Erase()的实现:
哈希桶的Erase函数实现起来有讲究 . 因为要判断所要删除的元素是单链表的头结点还是其他节点 , 又或者不存在 . 属于是单链表的操作 , 也很简单 , 效率依然是O(1).
//删除
bool Erase(Key key)
{auto ret = Find(key);//不存在要删除的值if (ret == nullptr){return false;}//存在要删除的值else{HashFunc hfc;int hashKey = hfc(key) % _table.size();Node* cur = _table[hashKey];Node* prev = nullptr;while (cur != nullptr){if (cur->_item.first == key){//此时待删除的节点是单链表的头结点if (prev == nullptr){_table[hashKey] = cur->_next;delete cur;break;}//此时待删除的节点是其他节点else{Node* next = cur->_next;delete cur;prev->_next = next;break;}_size -= 1;return true;}else{prev = cur;cur = cur->_next;}}return false;}
}6`析构函数的实现:
哈希桶的析构函数也很简单 , 类似于多个单链表的销毁 . 只需要遍历哈希桶底层的指针数组 , 一次销毁存在的单链表节点即可.
//析构
~HashTable()
{if (_table.size() > 0){for (int i = 0; i < _table.size(); i++){if (_table[i] != nullptr){Node* cur = _table[i];while (cur != nullptr){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}}
}7`拷贝构造函数的实现:
- 由于拷贝构造函数旨在创建一个值相同 , 但是内存上独立于原对象的新对象 . 所以此时可以直接遍历原哈希桶的每个节点值 , 复用Insert函数来简化为新对象插入元素的逻辑.
- 需要注意的是，在使用取模运算计算哈希值时，模数应取底层数组（即vector）的size值。拷贝构造函数的作用是初始化新对象，由于它本身就是一种构造函数，因此不会再调用其他构造函数。而由于新对象的vector初始状态为空（size为0），必须先在拷贝构造函数的初始化列表中进行初始化，才能正确计算哈希值，否则会出现除数为0的错误情况。
//拷贝构造
HashTable(const HashTable& obj):_table(11,nullptr) //初始化列表初始化底层的vector,_size(0)
{if (obj._table.size() > 0){_table.resize(11,nullptr);_size = 0;for (int i = 0; i < obj._table.size(); i++){if (obj._table[i] != nullptr){Node* cur = obj._table[i];while (cur != nullptr){Node* next = cur->_next;Insert(cur->_item);cur = cur->_next;}}}}
}8`赋值重载函数的实现:
通过传值方式传递哈希桶对象可以巧妙地复用拷贝构造函数。根据C++规范，传递自定义类型参数时会自动触发拷贝构造，从而生成一个临时哈希桶对象。随后利用swap函数获取该临时对象的资源，最终由编译器自动销毁临时对象。
//赋值重载
Self& operator=(Self other)
{std::swap(_table, other._table);std::swap(_size, other._size);return *this;
}9`采用链地址法的哈希表(哈希桶)完整代码实现:
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;
}namespace HashBucket
{template<class Key, class Val>struct HashNode{HashNode(pair<Key, Val> item):_item(item){}pair<Key, Val> _item;HashNode<Key, Val>* _next = nullptr;};//哈希函数(将key转换为整形)template<class Key>struct HashFunc{size_t operator()(const Key& key){return key;}};//哈希函数(对于string的特化版本)template<>struct HashFunc<string>{size_t operator()(const string& key){size_t ret = 0;for (auto& au : key){ret += au;ret *= 131;}return ret;}};template<class Key , class Val , class HashFunc = HashFunc<Key>>class HashTable{public:using Node = HashNode<Key, Val>;using Self = HashTable<Key, Val, HashFunc>;//构造 = 0;Hashtable():_table(11,nullptr),_size(0){}//析构~HashTable(){if (_table.size() > 0){for (int i = 0; i < _table.size(); i++){if (_table[i] != nullptr){Node* cur = _table[i];while (cur != nullptr){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}}}}//拷贝构造
HashTable(const HashTable& obj):_table(11,nullptr),_size(0)
{if (obj._table.size() > 0){for (int i = 0; i < obj._table.size(); i++){if (obj._table[i] != nullptr){Node* cur = obj._table[i];while (cur != nullptr){Node* next = cur->_next;Insert(cur->_item);cur = next;}}}}
}//赋值重载Self& operator=(Self other){std::swap(_table, other._table);std::swap(_size, other._size);return *this;}//插入bool Insert(const pair<Key, Val>& input){//避免重复值if (Find(input.first) != nullptr)return false;//判断平衡因子if (_size == _table.size()){vector<Node*> newTable;newTable.resize(__stl_next_prime(_size + 1));for (int i = 0; i < _table.size(); i++){if (_table[i] != nullptr){Node* cur = _table[i];while (cur != nullptr){Node* next = cur->_next;size_t hashKey = HashFunc()(cur->_item.first) % newTable.size();cur->_next = newTable[hashKey];newTable[hashKey] = cur;cur = next;}_table[i] = nullptr;}}_table.swap(newTable);}//直接往对应数组位置的单链表头插size_t hashKey = HashFunc()(input.first) % _table.size();Node* newNode = new Node(input);newNode->_next = _table[hashKey];_table[hashKey] = newNode;_size += 1;return true;}//查找pair<Key, Val>* Find(Key key){size_t hashKey = HashFunc()(key) % _table.size();Node* cur = _table[hashKey];while (cur != nullptr){if (cur->_item.first == key)return &cur->_item;cur = cur->_next;}return nullptr;}//删除bool Erase(Key key){auto ret = Find(key);if (ret == nullptr){return false;}else{HashFunc hfc;int hashKey = hfc(key) % _table.size();Node* cur = _table[hashKey];Node* prev = nullptr;while (cur != nullptr){if (cur->_item.first == key){if (prev == nullptr){_table[hashKey] = cur->_next;delete cur;break;}else{Node* next = cur->_next;delete cur;prev->_next = next;break;}_size -= 1;return true;}else{prev = cur;cur = cur->_next;}}return false;}}private:vector<Node*> _table;int _size;};
}