rambo

STL中的HASH

SGI STL的hash table采用分离链接法(seperate chaining)实现。在每一个表格元素中维护一个list ,hash function分配某一个list,虽然针对list的find操作只能是一种线性操作,但如果list 够短,速度还是足够快。具体原理参见hashtable(一)。本文着重于分析STL中的hash table实现"stl_hashtable.h"。

QQ截图20150909195404

hashtable节点的定义:

注意,bucket(采用vector,以便有动态扩充能力)所维护的linked list,(向前生成链表算法,新加入的元素一般被插到表的前端,因为最后插入的元素最有可能不久再次被访问)。而不采用STL的list 或slist。

HashTable的迭代器

hashtable的迭代器记录目前所指的节点。其前进操作是首先尝试从目前所指的节点出发,前进一个位置(节点),由于节点被安置于list内,利用节点的next指针即可完成操作。如果目前节点正巧是list的尾端,就跳至下一个bucket身上,即指向下一个list的头部节点。

注意,hashtable的迭代器没有后退操作(operator--()),hashtable也没有定义所谓的逆向迭代器。(reverse itertor)

QQ截图20150909201954