SGI中的STL中的hash_map和hash_set底層實現(xiàn)是用hash_table倦逐。
- 什么是哈希表铜跑，在另一篇文章：散列表有介紹耗绿。
hash_table
hash_table是采用開鏈法實現(xiàn)哈希表蛮放。
hash_table.jpg
template <typename Key>
class hash_table {
......
typedef HashtableSetNode<Key> node;
priavte:
Vector<node *> buckets;
size_type num_elements; // 元素總個數(shù)尝偎，用于size()
.....
}
由一個Vector保存每個list力麸。
hash_table節(jié)點
hash_table節(jié)點.jpg
template <typename Key>
struct HashtableSetNode {
Key key;
HashtableSetNode* next;
};
hash_table迭代器
hash_table迭代器類型是forward_iterator，只有++，沒有--后退的操作兰怠，也沒有定義逆向迭代器梦鉴。關(guān)于迭代器類型：《STL源碼剖析》筆記：迭代器
template <typename Key>
struct HashTableSetIterator {
......
typedef HashtableSetNode<Key> node;
node* cur; // 迭代器目前所指向的結(jié)點
HashTableSet<Key>* ht; // 保持對容器的連接能力，因為需要從一個桶跳到另一個桶
}
- 為什么需要一個記錄指向的結(jié)點所在的桶ht ?
因為在遍歷時揭保，當(dāng)遍歷到一個list的末尾時肥橙，我們必須要跳向下一個桶。所以需要記錄指向當(dāng)前節(jié)點所在的桶秸侣。HashTableSetIterator<Key>& HashTableSetIterator<Key>::operator++() { if (cur->next != nullptr) cur = cur->next; // 迭代器達到了一個list的末尾 else { size_type bucket = ht->bkt_num_key(cur->key); /* 定位下一個非空桶或者bucket計數(shù)到末尾 */ ++bucket; while(bucket < ht->bucketCount() && ht->buckets[bucket] == nullptr) bucket++; cur = bucket == ht->bucketCount() ? nullptr : ht->buckets[bucket]; } return *this; }
