当前位置：首页 > news >正文

＜＜哈希表迭代器函数＞＞

news 2026/5/27 5:34:56

哈希表迭代器是手写哈希表的核心模块，依托KeyOfT取键仿函数实现通用适配，同时打通unordered_map / unordered_set遍历逻辑，是容器实现迭代遍历、范围for循环的底层支撑。哈希表迭代器不同于链表、数组迭代器，需要适配哈希桶数组+单链表的双层结构。

1 迭代器核心原理

哈希表底层结构为：数组（哈希桶）+ 每个桶挂载一条单链表。迭代器的核心工作逻辑：

记录当前遍历的节点指针（当前链表节点）
记录当前遍历的桶下标（定位当前遍历的数组桶）
重载++运算符，实现跨桶、同桶遍历切换
依托KeyOfT适配map/set不同数据类型，实现通用遍历

核心特点：哈希表迭代器是单向迭代器，仅支持前置/后置++，不支持 -- 反向遍历，和STL标准unordered容器迭代器特性一致。

2 迭代器完整源码实现（通用模板）

迭代器封装为模板类，和哈希表、KeyOfT联动，完美适配map、set两种场景，无代码冗余。

// 前置声明哈希表模板类 template<class K, class T, class KeyOfT, class HashFunc> class HashTable; // 哈希表迭代器类 template<class K, class T, class KeyOfT, class HashFunc> struct HashIterator { // 别名定义，简化代码 typedef HashNode<T> Node; typedef HashIterator<K, T, KeyOfT, HashFunc> Self; Node* _pNode; // 当前迭代器指向的节点 size_t _bucketIndex; // 当前所在桶的下标 HashTable<K, T, KeyOfT, HashFunc>* _ht; // 哈希表本体指针 // 构造函数 HashIterator(Node* node, size_t index, HashTable<K, T, KeyOfT, HashFunc>* ht) :_pNode(node) , _bucketIndex(index) , _ht(ht) {} // 重载解引用：返回节点存储的数据 T& operator*() { return _pNode->_data; } // 重载箭头：支持 -> 访问数据成员 T* operator->() { return &_pNode->_data; } // 重载前置++（核心遍历逻辑） Self& operator++() { // 1. 当前桶还有后续节点，直接往后走 if (_pNode->_next != nullptr) { _pNode = _pNode->_next; } // 2. 当前桶遍历完毕，寻找下一个非空桶 else { _bucketIndex++; // 遍历后续所有桶，找到第一个非空桶的头节点 while (_bucketIndex < _ht->_table.size()) { if (_ht->_table[_bucketIndex] != nullptr) { _pNode = _ht->_table[_bucketIndex]; break; } _bucketIndex++; } // 所有桶遍历完毕，迭代器置空（尾后迭代器） if (_bucketIndex >= _ht->_table.size()) { _pNode = nullptr; } } return *this; } // 重载后置++ Self operator++(int) { Self tmp = *this; ++(*this); return tmp; } // 重载相等判断 bool operator!=(const Self& it) { return _pNode != it._pNode; } // 重载不等判断 bool operator==(const Self& it) { return _pNode == it._pNode; } };

3 哈希表配套迭代器接口

在哈希表类中实现begin()和end()接口，对外提供遍历入口，适配范围for循环。

// 哈希表类内接口 // 找到第一个非空桶的首节点，返回起始迭代器 iterator begin() { for (size_t i = 0; i < _table.size(); i++) { if (_table[i] != nullptr) { return iterator(_table[i], i, this); } } return end(); } // 尾后迭代器：节点为空 iterator end() { return iterator(nullptr, -1, this); }