版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338319
hashtable(散列表)结构,在插入、删除、搜索等操作也具有”常数平均时间”的表现。
举个例子,假设所有元素都是16bits,范围0~65535,简单的使用一个array即可以满足常数时间的插入、删除、搜索。
但是上面的解法存在两个问题:
第二个问题不难解决:可以将字符编码,每个字符以7-bits的数值表示(也就是ASCII码),如字符串”jjhou”表现为:
数值太大了,这有回到了问题一。
那么,如何避免一个大的慌缪的array呢?办法之一就是使用某种映射函数(hash function散列函数),将任意的元素映射到TableSize范围之内。
二、常用的哈希函数
使用hash function会带来一个问题:不同元素可能会被映射到相同的位置。这便是所谓的“碰撞(collision)”问题。解决的办法有很多种,包括线性探测(linear probing),二次探测(quadratic probing),开链(seperate chaining)…等做法。
哈希冲突的处理方法
线性探测法的地址增量di = 1, 2, … , m-1,其中,i为探测次数。该方法一次探测下一个地址,知道有空的地址后插入,若整个空间都找不到空余的地址,则产生溢出。
线性探测容易产生“聚集”现象。当表中的第i、i+1、i+2的位置上已经存储某些关键字,则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上,这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为“聚集”。聚集对查找效率有很大影响。
二次探测法的地址增量序列为 di = 12, -12, 22, -22,… , q2, -q2 (q <= m/2)。二次探测能有效避免“聚集”现象,但是不能够探测到哈希表上所有的存储单元,但是至少能够探测到一半。
链地址法特点:
以上参考: https://blog.csdn.net/u011080472/article/details/51177412
SGI的hash table正是以开链(seperate chaining)实现。
节点定义如下:
template<typename T>
struct __hashtable_node{
T val;
__hashtable_node* next;
};
注意:bucket所维护的linked list ,并不是采用STL的list,而是自行维护。
hashtable的核心成员定义如下:
template<typename Key, typename Value, typename HashFun>
class hashtable{
public:
typedef size_t size_type;
typedef HashFun hasher;
typedef Value value_type;
typedef Key key_type;
public:
typedef __hashtable_node<value_type> node;
// 分配桶节点,分配器
typedef allocator<node> nodeAllocator;
// 成员就是vector维护的node*数组
std::vector<node*> buckets;
size_type num_elements;
};
下面给出的iterator和侯捷先生的书,有不同,我认为迭代器关联hashtable是没有必要的。
template <typename Value>
struct __hashtable_iterator{
typedef Value value_type;
typedef Value& reference;
typedef __hashtable_node<value_type> node;
typedef node* pointer;
typedef __hashtable_iterator<value_type> self;
// 成员
node* cur;
reference operator*()const {return cur->val;}
pointer operator->()const{return &(operator*());}
// 返回的是引用
self& operator++(){
cur = cur->next;
return *this;
}
// 返回的非引用
self operator++(int){
self tmp = *this;
cur = cur->next;
return tmp;
}
};
在看构造函数,之前先看下,buckets表格大小的计算问题。
虽然开链法并不要求表的大小(buckets)必须也质数,但是SGI STL仍然以质数来设计表格大小。 将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问。同时提供一个函数,用来查询在这28个质数之中,”最接近某数,并大于某数” 的质数。
static const int __stl_num_primes = 28;
static const unsigned long __stl__prime_arr[__stl_num_primes] =
{
5, 53, 97, 193, 389,
769, 1543, 3079, 6151, 12289,
24593, 49157, 98317, 196613, 393241,
786433, 1572869, 3145739, 6291469, 12582917,
25165843, 50331653, 100663319, 201326611, 402653189,
805306457, 1610612741, 3221225473, 4294967291
};
// 找出上述28个质数之中,最接近并大于 n 的那个质数
inline unsigned long __stl_next_prime(unsigned long n){
const unsigned long* first = __stl__prime_arr;
const unsigned long* last = __stl__prime_arr + __stl_num_primes;
const unsigned long* pos = std::lower_bound(first, last, n);
return pos == last ? *(last - 1): *pos;
}
假设现在,创建含有50个bucket节点的hashtable:
hashtable<int, int, std::hash<int>> hash_table(50);
hashtable会返回53个节点(50的下一个质数是53)的bucket 数组:
插入6个元素后,hash table的状态如下:
构造函数如下:
template<typename Key, typename Value, typename HashFun>
hashtable<Key, Value, HashFun>::hashtable(size_type n){
initialize_buckets(n);
}
template<typename Key, typename Value, typename HashFun>
void hashtable<Key, Value, HashFun>::initialize_buckets(size_type n) {
// 例如传入 50 则返回 53
const size_type n_buckets = next_size(n);
buckets.reserve(n_buckets);
buckets.insert(buckets.end(), n_buckets, nullptr);
num_elements = 0;
}
下面重点是元素的插入,类型与红黑树有unique插入,以及equal插入:
template<typename Key, typename Value, typename HashFun>
std::pair<iterator, bool> hashtable<Key, Value, HashFun>::insert_unique(const value_type& obj){
// 判断是否需要重建表格,入需要则扩充
resize(num_elements + 1);
insert_unique_noresize(obj);
}
template<typename Key, typename Value, typename HashFun>
void hashtable<Key, Value, HashFun>::resize(const size_type n){
// 根据 n 决定是否重新建立表格
// 先省略......
}
可以插入重复的数据:
std::pair<iterator, bool> insert_equal(const value_type& obj);
// 根据 obj 定位到哪个buckets数组
size_type bkt_num(const value_type& obj, size_t n){
return btk_num_key(get_key(obj), n);
}
key_type& get_key(const value_type& obj){
// 这里面省略了从 obj 获取 key
return key_type();
}
size_type btk_num_key(const key_type& key, size_type n){
return std::hash(key) % n;
}
template<typename Key, typename Value, typename HashFun>
void hashtable<Key, Value, HashFun>::clear(){
for (size_type i = 0; i < buckets.size(); ++i) {
node* cur = buckets[i];
// 情况每个bucket的list
while (cur){
node* next = cur->next;
dealloc_dtor_node(cur);
cur = next;
}
buckets[i] = 0;
}
num_elements = 0; // 令总的个数为 0
// 注意, buckets vector并未释放掉空间,人保留原有的
}
find查询函数:
template<typename Key, typename Value, typename HashFun>
iterator hashtable<Key, Value, HashFun>::find(const key_type& key){
// 根据 obj 定位到哪个buckets数组
size_type idx = bkt_num(key, num_elements);
// 遍历查找bucket中的list
node* it = buckets[idx];
while (it++){
if (get_key(it->val) != key)
break;
}
return iterator(it);
}
链表中的节点的配置、构造、与析构。
// 产生(配置并构造)一个节点, 首先分配内存, 然后进行构造
node* alloc_ctor_node(const value_type& value){
node* tmp = nodeAllocator::allocate(); // 配置空间
construct(tmp, value); // 构造节点
return tmp;
}
// 析构结点元素, 并释放内存
void dealloc_dtor_node(node* p){
destroy(&p->val);
nodeAllocator::destroy(p);
}