hashtable：
SGI STL的hashtable是用的开链法完成的。用一个vector储存一系列的指针，指向一个节点元素链表的头（节点元素自身维护了一个list）。
节点定义：
template <class Value>
struct __hashtable_node
{
__hashtable_node *next;
Value val;
}; 迭代器摘要（没有--操作，没有逆向迭代器）：
struct __hashtable_iterator
{
node *cur; //迭代器目前节点
hashtable *ht;//保持对容器的关联
iterator operator++()
{
const node *old = cur;
cur = cur->next; //如果存在结果就是它
if(!cur)
{
size_type bucket = ht->bkt_num(old->value); //bkt_num()函数计算得到应该放到第几个“桶”
while(!cur && ++bucket < ht->buckets.size()) //跳到下一个有元素的“桶”的第一个元素
cur = ht->buckets[bucket];
}
return *this;
}
};
hashtable以质数来设计表格大小，预先计算好了28个质数，大约都是两倍的关系递增，查询28个质数中，“最接近且大于元素数目”的数字作为vector的长度，如果需要重新分配，则分配下一个质数长度的vector。
hashtable设计的容量和buckets vector的大小一样。因此如果数目超过了，就需要重新建立：新建一个temp，将原来hashtable中的元素一个一个切割出来插入到新的temp的适当位置，全部插完后交换hashtable和temp。同时释放temp的内存。
同样，hashtable的插入操作也分为insert_unique和insert_equal,分别代表不允许重复和允许重复插入。下面是不允许重复插入操作的具体实现。
template <class V, class K, class HF, class Ex, class Eq, class A>
pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool>
hashtable<V, K, HF, Ex, Eq, A>::insert_unique_norssize(const value_type& obj)
{
const size_type n = bkt_num(obj); //决定其应该插入的"桶"
node *first = buckets[n]; //first指向那个"桶"
for(node *cur=first, cur, cur=cur->next) //如果已有元素，则进入循环，没有则不进入
if(equals(get_key(cur->value), get_key(obj))) //如果已存在键值相同的
return pair<iterator, bool>(iterator(cur, this), false); //不插入直接返回
//如果无重复，则插入
node *tmp = new_node(obj);
temp->next = first;
buckets[n] = tmp;
++num_elements;
return pair<iterator, bool>(iterator(tmp, this), true);
}
hashtable有一些无法处理的型别，除非用户为那些型别写了相应的hash function。
hash_set/hash_map：
此两个跟set/map相比较，只是插入的元素不会自动排序。其他使用方式完全一致，而操作基本全部由hashtable完成。
hash_mulitset/hash_multimap:
和multiset/multimap比较，也只是插入元素不会自动排序。
posted on 2010-06-08 02:50
dead_horse 阅读(538)
评论(0) 编辑 收藏 引用 所属分类:
STL读书笔记