重读STL源码剖析:hashtable

hashtable:

hashtable的设计是一个vector数组,每个数组内为一个链表,链表链着hash到同位置的节点,但链表的实现不是list或slist

hashtable的节点设计:

1.存储元素值的变量val

2.一个指向下一个节点(同一个bucket内的)的指针next

hashtable的迭代器:

1.内部维护两个成员:

指向当前节点的cur

指向所属bucket的指针

2.迭代器属于forward_iterator,只能++与读写,这是由链表的特性决定的。

hashtable的结构:

1.一个vector数组buckets,用于存放节点

2.num_elements用于统计所有节点的个数(不是指vector的大小)

插入与表格重整:

插入:

当插入时,首先通过一个resize(num_elements)用于判断是否需要重建表格,如果需要就扩充。然后进行插入

表格重整:

判断表格是否需要重整是通过判断num_elements是否大于buckets.size()

也就是说如果节点个数大于vector的size,则重整表格。

重整的表格大小为大于当前表格大小的一个质数,关系上来看接近于两倍。

表格大小调整完后,对原buckets里的每个节点进行重哈希(因为表格大小变了),重新构造。

hash_set:

底层以hashtable为基础,插入使用insert_unique

hash_map:

底层以hashtable为基础,插入使用insert_unique

hash_multiset:

底层以hashtable为基础,插入使用insert_equal

hash_multimap:

底层以hashtable为基础,插入使用insert_equal

原文地址:https://www.cnblogs.com/lxy-xf/p/11525598.html