STL--hashtable

hashtable使用开链的方式,解决元素个数大于array容量的问题。

当两个不同元素hash得到相同的hash值时,此时我们使用bucket list来链接连个元素。

hashtable迭代器必须永远维系着与整个"bucket vector"的关系,并记录目前所指的节点。其前进操作是首先从从目前所指的节点出发,前进一个位置(节点),由于节点被安置于list内,所有利用节点的next指针可轻易达成前进操作。如果目前节点正巧是list的尾端,就跳至下一个bucket身上,那正是指向下一个list的头部节点。

hashtable迭代器没有后退操作,没有逆向迭代器。只有++,没有--。

虽然开链法并不要求表格大小必须为质数,但是SGI STL仍然以质数来设计表格的大小。

原文地址:https://www.cnblogs.com/zhousong918/p/10789431.html