page contents

STL中hashtable的底层实现?

轩辕小不懂 发布于 2022-01-07 14:29
阅读 764
收藏 0
分类:C/C++开发
  • c
  • c++
  • 2836
    Nen
    Nen
    - 程序员

    hashtable中的bucket所维护的list既不是list也不是slist,而是其自己定义的由hashtable_node数据结构组成的linked-list,而bucket聚合体本身使用vector进行存储。hashtable的迭代器只提供前进操作,不提供后退操作

    在hashtable设计bucket的数量上,其内置了28个质数[53, 97, 193,…,429496729],在创建hashtable时,会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量(vector的长度),其中每个bucket所维护的linked-list长度也等于hashtable的容量。如果插入hashtable的元素个数超过了bucket的容量,就要进行重建table操作,即找出下一个质数,创建新的buckets vector,重新计算元素在新hashtable的位置。

    请先 登录 后评论