hashtable
---------------------------------------------------------------------------
二叉搜索树具有对数平均时间的表现，它建立在输入数据有足够的随机性的如果
hashtable 有常数平均时间的表现，基于统计，不需依赖输入元素的随机性
hashtalbe 的简单实现：
所有元素都 16-bits 不带正负号的整数，范围 0~65535，配置一个 array。索引號码为 0~65535，初值所有为 0 。
每个元素值表示索引號相应的元素值出现的次数。
每插入元素 i ，运行 array[i]++; 每删除元素 i ，运行 array[i]--;
搜索元素 i ，仅仅要检查 array[i] 是否为 0
排序时，仅仅要遍历 array 。输入 array[i] 个 i
问题：
1.假设元素是字符串(或其他)而非整数。将无法被拿来作为 array 的索引
2.假设元素是 32-bits，须要的索引数是 2^32;
解决：
问题1
整数是由数字组成的。字符串是由字符组成的。
在整数的时候。索引取的是各个数字的十进制组合表示。 如 1234 取索引 1*10^3 + 2*10^2 + 3*10^1 + 4*10^0
在字符串的时候，索引相同也能够取各个字符的ASCII编码组合表示。如 hou 能够取索引 'h'*128^2 + 'o'*128^1 + 'u'*128^0
问题2
採用hash function 将元素值映射到大小可接受的索引范围
-->问题：不同元素被映射到同样的位置
-->解决：线性探測、二次探測、开链
线性、二次指的是碰撞时前进的步伐大小
线性 --> H+1, H+2, H+3, ...
二次 --> H+1^2, H+2^2, H+3^2, ...
开链法是指在每个表元素中维护一个 list ，在那个元素上运行元素的插入、搜寻、删除
SGI STL 的 hash table 採用的是开链法
hashtable 的能容纳的元素个数就是 bucket vector 的大小。当超过这个大小时。hashtable就会调用 resize() 函数又一次分配大小。
重建新的 hashtable
#ifndef __SGI_STL_INTERNAL_HASHTABLE_H
#define __SGI_STL_INTERNAL_HASHTABLE_H
// Hashtable class, used to implement the hashed associative containers
// hash_set, hash_map, hash_multiset, and hash_multimap.
#include <stl_algobase.h>
#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_tempbuf.h>
#include <stl_algo.h>
#include <stl_uninitialized.h>
#include <stl_function.h>
#include <stl_vector.h>
#include <stl_hash_fun.h>
__STL_BEGIN_NAMESPACE
// hashtable 元素所维护的链表节点
template <class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable;
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator;
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_const_iterator;
//hashtable 的迭代器
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef Value& reference;
typedef Value* pointer;
node* cur; //迭代器眼下所指的节点
hashtable* ht; //保持对容器的连结关系(由于可能须要从 bucket 跳到 bucket)
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
//为什么会有个专门的 __hashtable_const_iterator 。用 const __hashtable_iterator 不行吗？
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_const_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef const Value& reference;
typedef const Value* pointer;
const node* cur;
const hashtable* ht;
__hashtable_const_iterator(const node* n, const hashtable* tab)
: cur(n), ht(tab) {}
__hashtable_const_iterator() {}
__hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
reference operator*() const { return cur->val; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
const_iterator& operator++();
const_iterator operator++(int);
bool operator==(const const_iterator& it) const { return cur == it.cur; }
bool operator!=(const const_iterator& it) const { return cur != it.cur; }
};
//线性探測、二次探測的方法的表大小最好是质数
//开链法的表不须要是质数。只是 SGI STL 仍以质数来设计表的大小
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 3, 769,
1543, 3079, 6151, 122, 24593,
49157, 98317, 196613, 393241, 7833,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 4026531, 8053057,
1610612741, 3221225473ul, 4294967291ul
};
inline unsigned long __stl_next_prime(unsigned long n)
{
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n); //用 lower_bound 来查找与要设计的表的大小最接近的质数
return pos == last ?否则就要跳到下一个 bucket 了 if (!cur) { size_type bucket = ht->bkt_num(old->val); //定位当前 bucket 的下一个 while (!cur && ++bucket < ht->buckets.size()) //找到当前 bucket 之后的第一个不为空的 bucket cur = ht->buckets[bucket]; //让 cur 指向 bucket 的头节点 } return *this; } //如非必要，还是使用前置 operator++ 吧。后置的编译器要帮它生成和个 int 參数，执行时要产生暂时对象 //内部还是调用前置 operator++ 实现的，返回的时候又要调用拷贝构造函数，还要析构掉之前生成的暂时对象 template <class V, class K, class HF, class ExK, class EqK, class A> inline __hashtable_iterator<V, K, HF, ExK, EqK, A> __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int) { iterator tmp = *this; ++*this; return tmp; } template <class V, class K, class HF, class ExK, class EqK, class A> __hashtable_const_iterator<V, K, HF, ExK, EqK, A>& __hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++() { const node* old = cur; cur = cur->next; if (!cur) { size_type bucket = ht->bkt_num(old->val); while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket]; } return *this; } template <class V, class K, class HF, class ExK, class EqK, class A> inline __hashtable_const_iterator<V, K, HF, ExK, EqK, A> __hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++(int) { const_iterator tmp = *this; ++*this; return tmp; } #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION template <class V, class K, class HF, class ExK, class EqK, class All> inline forward_iterator_tag iterator_category(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&) { return forward_iterator_tag(); } template <class V, class K, class HF, class ExK, class EqK, class All> inline V* value_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&) { return (V*) 0; } template <class V, class K, class HF, class ExK, class EqK, class All> inline hashtable<V, K, HF, ExK, EqK, All>::difference_type* distance_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&) { return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0; } template <class V, class K, class HF, class ExK, class EqK, class All> inline forward_iterator_tag iterator_category(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&) { return forward_iterator_tag(); } template <class V, class K, class HF, class ExK, class EqK, class All> inline V* value_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&) { return (V*) 0; } template <class V, class K, class HF, class ExK, class EqK, class All> inline hashtable<V, K, HF, ExK, EqK, All>::difference_type* distance_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&) { return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ template <class V, class K, class HF, class Ex, class Eq, class A> bool operator==(const hashtable<V, K, HF, Ex, Eq, A>& ht1, const hashtable<V, K, HF, Ex, Eq, A>& ht2) { typedef typename hashtable<V, K, HF, Ex, Eq, A>::node node; if (ht1.buckets.size() != ht2.buckets.size()) return false; for (int n = 0; n < ht1.buckets.size(); ++n) { node* cur1 = ht1.buckets[n]; node* cur2 = ht2.buckets[n]; for ( ; cur1 && cur2 && cur1->val == cur2->val; cur1 = cur1->next, cur2 = cur2->next) {} if (cur1 || cur2) return false; } return true; } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class Val, class Key, class HF, class Extract, class EqKey, class A> inline void swap(hashtable<Val, Key, HF, Extract, EqKey, A>& ht1, hashtable<Val, Key, HF, Extract, EqKey, A>& ht2) { ht1.swap(ht2); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ //在不须要重建表的情况下插入新节点。键值反复的节点不会插入 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_noresize(const value_type& obj) { const size_type n = bkt_num(obj); //决定 obj 就位于哪个 bucket node* first = buckets[n]; //令 first 指向 bucket 相应的串行头部 for (node* cur = first; cur; cur = cur->next) //发现键值与链表同的某节点键值同样，不插入 if (equals(get_key(cur->val), get_key(obj))) return pair<iterator, bool>(iterator(cur, this), false); //在链表头插入新节点 node* tmp = new_node(obj); tmp->next = first; buckets[n] = tmp; ++num_elements; return pair<iterator, bool>(iterator(tmp, this), true); } //在不须要重建表的情况下插入新节点。插入的节点键值能够反复 template <class V, class K, class HF, class Ex, class Eq, class A> typename hashtable<V, K, HF, Ex, Eq, A>::iterator hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj) { const size_type n = bkt_num(obj); //决定 obj 就位于哪个 bucket node* first = buckets[n]; //令 first 指向 bucket 相应的串行头部 for (node* cur = first; cur; cur = cur->next) //假设发现与链表中的某键值同样。就立即插入。然后返回 if (equals(get_key(cur->val), get_key(obj))) { node* tmp = new_node(obj); tmp->next = cur->next; cur->next = tmp; ++num_elements; return iterator(tmp, this); } //链表中没有同样键值的节点，将新节点插入在链表 node* tmp = new_node(obj); tmp->next = first; buckets[n] = tmp; ++num_elements; return iterator(tmp, this); } template <class V, class K, class HF, class Ex, class Eq, class A> typename hashtable<V, K, HF, Ex, Eq, A>::reference hashtable<V, K, HF, Ex, Eq, A>::find_or_insert(const value_type& obj) { resize(num_elements + 1); size_type n = bkt_num(obj); node* first = buckets[n]; for (node* cur = first; cur; cur = cur->next) if (equals(get_key(cur->val), get_key(obj))) return cur->val; node* tmp = new_node(obj); tmp->next = first; buckets[n] = tmp; ++num_elements; return tmp->val; } template <class V, class K, class HF, class Ex, class Eq, class A> pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, typename hashtable<V, K, HF, Ex, Eq, A>::iterator> hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key) { typedef pair<iterator, iterator> pii; const size_type n = bkt_num_key(key); for (node* first = buckets[n]; first; first = first->next) { if (equals(get_key(first->val), key)) { for (node* cur = first->next; cur; cur = cur->next) if (!equals(get_key(cur->val), key)) return pii(iterator(first, this), iterator(cur, this)); for (size_type m = n + 1; m < buckets.size(); ++m) if (buckets[m]) return pii(iterator(first, this), iterator(buckets[m], this)); return pii(iterator(first, this), end()); } } return pii(end(), end()); } template <class V, class K, class HF, class Ex, class Eq, class A> pair<typename hashtable<V, K, HF, Ex, Eq, A>::const_iterator, typename hashtable<V, K, HF, Ex, Eq, A>::const_iterator> hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key) const { typedef pair<const_iterator, const_iterator> pii; const size_type n = bkt_num_key(key); for (const node* first = buckets[n] ; first; first = first->next) { if (equals(get_key(first->val), key)) { for (const node* cur = first->next; cur; cur = cur->next) if (!equals(get_key(cur->val), key)) return pii(const_iterator(first, this), const_iterator(cur, this)); for (size_type m = n + 1; m < buckets.size(); ++m) if (buckets[m]) return pii(const_iterator(first, this), const_iterator(buckets[m], this)); return pii(const_iterator(first, this), end()); } } return pii(end(), end()); } template <class V, class K, class HF, class Ex, class Eq, class A> typename hashtable<V, K, HF, Ex, Eq, A>::size_type hashtable<V, K, HF, Ex, Eq, A>::erase(const key_type& key) { const size_type n = bkt_num_key(key); node* first = buckets[n]; size_type erased = 0; if (first) { node* cur = first; node* next = cur->next; while (next) { if (equals(get_key(next->val), key)) { cur->next = next->next; delete_node(next); next = cur->next; ++erased; --num_elements; } else { cur = next; next = cur->next; } } if (equals(get_key(first->val), key)) { buckets[n] = first->next; delete_node(first); ++erased; --num_elements; } } return erased; } template <class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::erase(const iterator& it) { if (node* const p = it.cur) { const size_type n = bkt_num(p->val); node* cur = buckets[n]; if (cur == p) { buckets[n] = cur->next; delete_node(cur); --num_elements; } else { node* next = cur->next; while (next) { if (next == p) { cur->next = next->next; delete_node(next); --num_elements; break; } else { cur = next; next = cur->next; } } } } } template <class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::erase(iterator first, iterator last) { size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size(); size_type l_bucket = last.cur ?
bkt_num(last.cur->val) : buckets.size(); if (first.cur == last.cur) return; else if (f_bucket == l_bucket) erase_bucket(f_bucket, first.cur, last.cur); else { erase_bucket(f_bucket, first.cur, 0); for (size_type n = f_bucket + 1; n < l_bucket; ++n) erase_bucket(n, 0); if (l_bucket != buckets.size()) erase_bucket(l_bucket, last.cur); } } template <class V, class K, class HF, class Ex, class Eq, class A> inline void hashtable<V, K, HF, Ex, Eq, A>::erase(const_iterator first, const_iterator last) { erase(iterator(const_cast<node*>(first.cur), const_cast<hashtable*>(first.ht)), iterator(const_cast<node*>(last.cur), const_cast<hashtable*>(last.ht))); } template <class V, class K, class HF, class Ex, class Eq, class A> inline void hashtable<V, K, HF, Ex, Eq, A>::erase(const const_iterator& it) { erase(iterator(const_cast<node*>(it.cur), const_cast<hashtable*>(it.ht))); } //推断是否须要重建表。如须要就扩充 //为什么要 resize 呢？ 底层的 vector 不是会动态添加大小吗？ // --> ？？由于表太大了， 装载率太大，减少了查找效率 template <class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type num_elements_hint) { const size_type old_n = buckets.size(); //假设元素个数大于 bucket vector 的大小，就重建表 if (num_elements_hint > old_n) { //新表的大小 const size_type n = next_size(num_elements_hint); if (n > old_n) { //暂时的表，用来存放新建立的表，之后会和原来的表 swap。 vector<node*, A> tmp(n, (node*) 0); __STL_TRY { //遍历每个旧 bucket for (size_type bucket = 0; bucket < old_n; ++bucket) { node* first = buckets[bucket]; //遍历bucket 里的每个节点 while (first) { size_type new_bucket = bkt_num(first->val, n); //当前节点应落在新 bucket vector 的哪一个 bucket 里 // 以下四个操作当前节点链接到新 bucket 下的链表前面 buckets[bucket] = first->next; first->next = tmp[new_bucket]; tmp[new_bucket] = first; first = buckets[bucket]; } } buckets.swap(tmp); //和原来的表交换，由编译器收回 tmp。 --> 为什么要 swap 。把 tmp 作为新的 bucket vector 不好吗？ --> ??