《STL源码剖析》笔记：hash_table

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;
  }