您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

chapter5 关联式容器:hashtable相关

目录

  • 1 hashtable
    • 1.1 概述
      • 1.1.1 线性探测
      • 1.1.2 二次探测
      • 1.1.3 开链
    • 1.2 hashtable的buckets和nodes
    • 1.3 hashtable的迭代器
    • 1.4 hashtable的数据结构
    • 1.5 hashtable的构造与内存管理
      • 1.5.1 插入与表格重整
      • 1.5.2 判知元素的落脚处(bkt_num)
      • 1.5.3 复制和整体删除
      • 1.5.4 应用实例
    • 1.6 hash functions
  • 2 hash_set
  • 3 hash_map
  • 4 hash_multiset&hash_multimap


1 hashtable

1.1 概述

要提供常数时间的操作,可以通过配置一个array,array的每一个元素值代表元素的出现次数,元素所在array中的位置为索引。这种解法的额外负担是array的空间和初始化时间。

存在两个问题:

  1. 元素是32-bits的,那么array太大
  2. 若元素形态是字符串非整数,则无法作为array的索引,即使通过编码也可能最终回归问题一,导致更大的索引值

解决方法:使用某种映射函数,将大数映射为小数。

散列函数(hash function):负责将某一元素映射为一个“大小可接受之索引”

碰撞问题:不同的元素被映射到相同位置

解决碰撞问题的方法:线性探测、二次探测、开链

1.1.1 线性探测

负载系数:元素个数除以表格大小,负载系数永远在0~1之间

  1. 元素插入:使用hash function计算出插入位置后,发现位置不可用,则循序往下一一寻找

  2. 元素搜寻:同上

  3. 元素删除:惰性删除,只标记删除记号,实际删除待表格重新整理——hash table中的每一个元素不仅表述它们自己,也关系到每个元素的排列
    在这里插入图片描述

1.1.2 二次探测

在这里插入图片描述
1.线性探测法每次探测的都必然是一个不同的位置,二次探测法是否能够保证如此?二次探测法是否能够保证如果表格之中没有X,那么我们插入X一定能够成功?

假设表格大小为质数,而且永远保持负载系数在0.5以下(超过0.5重新配置并重新整理表格),那么可确定每次插入一个新元素所需的探测次数不多于2

2.线性探测法的运算过程极其简单,二次探测法则显然复杂得多。这是否会在执行效率上带来太多的负面影响?

在这里插入图片描述
3.不论线性探测或二次探测,当负载系数过高时,表格是否能够动态成长?

欲扩充表格,首先必须找出下一个新的而且够大(大约两倍)的质数,然后必须考虑表格重建(rehashing)的成本——不只是原封不动地拷贝而已,还必须检验旧表格中的每一个元素,计算其在新表格中的位置,然后再插入到新表格中。

小结:

二次探测可以消除主集团(primary clustering),却可能造成次集团(secondary clustering):两个元素经hash function 计算出来的位置若相同,则插入时所探测的位置也相同,形成某种浪费。

消除次集团的办法:复式散列

1.1.3 开链

在每一个表格元素中维护一个list:hash function会分配一个list,可在list上执行元素的插入、搜寻和删除等操作。虽然针对list而进行的搜寻只能是一种线性操作,但如果list够短,速度还是够快。

1.2 hashtable的buckets和nodes

在这里插入图片描述

hashtable的节点定义:

template <class Value>
struct __hashtable_node {
   __hashtable_node* next;
    Value val;
};

1.3 hashtable的迭代器

迭代器类型:typedef forward_iterator_tag iterator_category

因此,hashtable的迭代器无后退操作(operator–())

在这里插入图片描述

1.4 hashtable的数据结构

在这里插入图片描述
SGI STL会以质数来设计表格大小(开链法并不要求表格大小必须为质数),并将28个质数计算好,以备随时方法,同时提供一个函数__stl_next_prime(unsigned long n)用来查询在这28个质数之中,最接近并大于n的质数

在这里插入图片描述

1.5 hashtable的构造与内存管理

专属节点配置器:typedef simple_alloc<node, Alloc> node_allocator

构造一个拥有50个节点的hashtable(传入50,返回53)

hashtable(size_type n, const HashFcn& hf, const EqualKey& eql) : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0) {
    initialize_buckets(n);
}
void initialize_buckets(size_type n) {
    const size_type n_buckets = next_size(n); //返回最接近并大于n的质数
    buckets.reserve(n_buckets);
    buckets.insert(buckets.end(), n_buckets, (node*)0);
    num_elements = 0;
}

1.5.1 插入与表格重整

//插入元素,不允许重复
pair<iterator, bool> insert_unique(const value_type& obj) {
    resize(num_elements + 1); //判断是否需要重建表格,如需要就扩充
    return insert_unique_noresize(obj);
}

表格重建与否的判断函数:将新增元素计入后的元素个数和buckets vector的大小来比。如果前者大于后者,就重建表格。由此可判断,每个bucket(list)的最大容量和buckets 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 nume_elements_hint)

不允许键值重复的新节点插入函数

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>::hashinsert_unique_noresize(const value_tyoe& obj)

在这里插入图片描述
允许键值重复,则使用insert_equal(),不再是inert_unique()。即原先发现与链表中的某键值相同时,不插入立即返回;insert_equal马上插入然后返回。

1.5.2 判知元素的落脚处(bkt_num)

通过bkt_num()函数调用hash function,取得一个可以执行moduls(取模)运算的数值。

因为有些元素型别无法直接拿来对hashtable的大小进行模运算,例如字符字符串,需要做一些转换。

1.5.3 复制和整体删除

由于整个hashtable由vector和linked-list组合而成,因此,复制和整体删除都需要特别注意内存的释放问题。

template<class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::clear() {
    //针对每一个bucket
    for(size_type i = 0; i < buckets.size(); ++i) {
        node* cur = buckets[i];
        //将bucket list中的每一个节点删除掉
        while(cur != 0) {
            node* next = cur->next;
            delete_node(cur);
            cur = next;
        }
        bucket[i] = 0; //令bucket内容为null指针
    }
    num_elements = 0;  //令总节点个数为0
    //buckets vector并未释放掉空间,仍抱有原来大小
}
template<class V, class K, class HF, class Ex, class Eq, class A> void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht) {
    buckets.clear();
    buckets.reserve(ht.buckets.size());
    buckets.insert(buckets.end(), ht.buckets.size(), (node*)0); //从己方的buckets vector尾端开始插入n个null指针
    __STL_TRY {
        for(size_type i = 0; i < ht.buckets.size(); ++i) {
            //复制vector的每一个元素
            if(const node* cur = ht.buckets[i]) {
                node* copy = new_node(cur->val);
                buckets[i] = copy;
                //针对同一个bucket list,复制每一个节点
                for(node* next = cur->next; next; cur = next, next = cur->next) {
                    copy->next = new_node(next->val);
                    copy = copy->next;
                }
            }
        }
        num_elements = ht.num_elements;
    }
    __STL_UNWIND(clear());
}

1.5.4 应用实例

在这里插入图片描述
在这里插入图片描述
hashtable提供的find和count函数

iterator find(const key_type& key) {
    size_type n = bkt_num_key(key); //首先判知元素落脚处,即在哪一个bucket内
    node* first;
    //从bucket list开始,一一比对每个元素的键值
    for(first = buckets[n]; first && !equals(get_key(first->val), key), first = first->next) {}
    return iterator(first, this);
}

size_type count(const key_type& key) const {
    const size_type n = bkt_num_key(key);
    size_type result = 0;
    //从bucket list开始,一一比对每个元素的键值,比对成功则加1
    for(const node* cur = buckets[n]; cur; cur = cur->next)
        if(equals(get_key(cur->val), key)) ++result;
   	return result;
}

1.6 hash functions

针对char,int,long等整数型别, hash functions只是返回原值:

__STL_TEMPLATE_NULL struct hash<char> {
    size_t operator()(char x) const { return x; }
}

对于char*,const char*则需要经过一个转换函数__stl_hash_string():

inline size_t __stl_hash_string(const char* s) {
    unsigned long h = 0;
    for(; *s; ++s)
        h = 5*h + *s;
    return size_t(h);
}

2 hash_set

  1. hash_set以hashtable为底层机制

  2. 使用set的目的:快速搜寻元素。而由于RB-tree有自动排序而hashtable没有,因此set的元素能够自动排序而hsh_set没有。

元素插入的次序可能受底层hashtable大小和元素大小的影响!

  1. hash_set的键值就是实值,实值就是键值。

  2. 插入操作使用insert_unique(),不允许键值重复

3 hash_map

  1. hash_map也以hashtable为底层机制,因此没有自动排序

  2. hash_map的每一个元素同时拥有一个实值和键值(使用方式与map相同)

  3. 插入操作使用insert_unique(),不允许键值重复

4 hash_multiset&hash_multimap

  1. hash_multiset/hash_multimap也以hashtable为底层机制,因此hash_multiset/hash_multimap的元素不会被自动排序

  2. 与hash_set/hash_map的唯一区别:元素插入采用insert_equal()


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进