SGI中的STL中的hash_map和hash_set底层实现是用hash_table。
- 什么是哈希表，在另一篇文章：散列表有介绍。
hash_table
hash_table是采用开链法实现哈希表。
hash_table.jpg
template <typename Key>
class hash_table {
......
typedef HashtableSetNode<Key> node;
priavte:
Vector<node *> buckets;
size_type num_elements; // 元素总个数，用于size()
.....
}
由一个Vector保存每个list。
hash_table节点
hash_table节点.jpg
template <typename Key>
struct HashtableSetNode {
Key key;
HashtableSetNode* next;
};
hash_table迭代器
hash_table迭代器类型是forward_iterator，只有++，没有--后退的操作，也没有定义逆向迭代器。关于迭代器类型：《STL源码剖析》笔记：迭代器
template <typename Key>
struct HashTableSetIterator {
......
typedef HashtableSetNode<Key> node;
node* cur; // 迭代器目前所指向的结点
HashTableSet<Key>* ht; // 保持对容器的连接能力，因为需要从一个桶跳到另一个桶
}
- 为什么需要一个记录指向的结点所在的桶ht ?
因为在遍历时，当遍历到一个list的末尾时，我们必须要跳向下一个桶。所以需要记录指向当前节点所在的桶。HashTableSetIterator<Key>& HashTableSetIterator<Key>::operator++() { if (cur->next != nullptr) cur = cur->next; // 迭代器达到了一个list的末尾 else { size_type bucket = ht->bkt_num_key(cur->key); /* 定位下一个非空桶或者bucket计数到末尾 */ ++bucket; while(bucket < ht->bucketCount() && ht->buckets[bucket] == nullptr) bucket++; cur = bucket == ht->bucketCount() ? nullptr : ht->buckets[bucket]; } return *this; }
