作者：初升的太阳1866 | 来源：互联网 | 2023-01-16 10:41
1.STL中hashtable的实现：首先，STL中hashtable是实现hash_map和hash_set的底层。它解决冲突的方式是开链法，每个放置索引值的节点
1. STL中hashtable的实现：
首先，STL中hashtable是实现hash_map和hash_set的底层。它解决冲突的方式是
开链法，每个放置索引值的节点称为
桶节点（也就是该索引值的头结点），桶节点里放着一个value值，一个指向下一个节点的next指针。
此外，还维护了一个vector buckets存放所有桶节点，还维护一张
质数表，里面质数为53,97,193....这个vector的容量大小是按离初始值最近的那个质数分配的，举个例子：hashtable对象构造时为50个桶的话，会自动选择比50大的最近质数53来作为vecotr成员函数reserve的大小。
当hashtable中插入的元素个数大于当前vector的容量时，会新建一个vector，新vector的容量是之前vector容量所在质数表里的下一个质数，如53的后一个是97，新vector的容量为97。之后把原来vector的数据放入新的vector中，最后用swap
交换两个vector，在函数结束后会自动释放新键的临时vector。
另外，STL中hashtable用的hash函数是采用
取模运算来计算索引值的，在计算索引值之前，还要调用
bkt_num函数将不同类型的key数据转换成统一的数值格式（如：const char *转换成特定的数值），以便hash函数进行取模处理，取模用的模值就是桶的数量值，也就是vector的容量。
2. hash_map的实现：
STL里的map底层实现是rb_tree类，而hash_map的底层实现是用hashtable类。几乎所有的hash_map的操作行为，都是转调hashtable的操作行为。map和hahs_map的区别是：rb_tree自带排序功能而hashtable没有，反应出来的结果就是map的元素都是自动排好序的，而
hash_map则无法排序。
在hash_map中，定义了hashtable类的对象rep，之后初始化rep的缺省桶数量为100，即buckets那个vector的容量，100对应质数表里的193，所以实际vector的容量是193。此外，hash_map的插入函数用的是hashtable的
insert_unique函数，即不允许重复插入。
京公网安备 11010802041100号