C++王牌结构hash：哈希表开散列(哈希桶)的实现与应用

目录

一、开散列的概念

1.1开散列与闭散列比较

二、开散列/哈希桶的实现

2.1开散列实现

哈希函数的模板构造

哈希表节点构造

开散列增容

插入数据

2.2代码实现

一、开散列的概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

1.1开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a _data; } Self& operator++() { //如果当前桶内还有节点 if (_node->_next) { _node = _node->_next; } else { //当前桶找完，就去找下一个桶 Keyoft kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size(); hashi++; while (hashi _tables.size()) { if (_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; break; } hashi++; } //如果后面没有桶 if (hashi == _ht->_tables.size()) { _node = nullptr; } } return *this; } bool operator!=(const Self& s) { return _node != s._node; } }; //哈希桶搭建 template class HashTable { template friend struct __HTIterator; typedef HashNode Node; public: typedef __HTIterator iterator; HashTable() { _tables.resize(10, nullptr); _n = 0; } ~HashTable() { for (size_t i = 0; i _next; delete cur; cur = next; } _tables[i] = nullptr; } } iterator begin() { for (size_t i = 0; i _next; //头插到新表 size_t hashi = hs(kot(cur->_data)) % newtables.size(); newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } size_t hashi = hs(kot(data)) % _tables.size(); Node* newnode = new Node(data); //头插 newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } //查找 Node* Find(const K& key) { Hash hs; Keyoft kot; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return cur; cur = cur->_next; } return nullptr; } Node* Erase(const K& key) { Hash hs; Keyoft kot; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = cur->next; } else { prev->_next = cur->_next; } } prev = cur; cur = cur->_next; } return false; } private: vector _tables;//指针数组 size_t _n; }; }