首页 > 代码库 > 《STL源码剖析》学习笔记系列之五——关联式容器(2)

《STL源码剖析》学习笔记系列之五——关联式容器(2)

Hashtable

2.1 简介

   哈希表,又名散列表,可以提供“常数时间”的插入、删除、查询等操作。不同的元素通过hash function映射到不同的位置,但当不同元素获得经hash function获得相同的位置(索引)时,则发生“碰撞”,此时需要通过以下几种方法为新加入的元素寻找新的索引地址。

1、        线性探测法

由于为元素准备的为一块连续内存空间地址,该方法会循序往下一一寻找,若达到所分配地址尾端,则环绕到头部继续寻找。所找到的第一个空闲地址即分配给该元素。

2、        二次探测法

   二次探测法主要为了解决主集团问题(连续空间被占据,后续插入的结点依然被插入于该连续空间的边缘),该方法依次尝试H+1,H+22,H+33等位置。

3、        复式散列法

   该方法将第一次获取的索引地址再次作为hash function的参数,再次计算得出新的索引地址。

4、        开链法

该方法是在每一个表格中维护一个list,若出现具有相同的索引地址的新元素,则将其插入到该list中。这样就避免了重复的探测寻找新的地址存放该新元素。底层的表格数据结构采用vector,这样可以保持动态增长。同时每个vector中存放的数据结构为_hashtable_node,定义如下:

template<classvalue>

struct  _hashtable_node

{

_hashtable_node*next;

valueval;

};

 

2.2、基本方法和内存管理

2.2.1、初始化及内存管理

Hashtable以质数来设计表格(buckets)大小,事先准备好28个质数计算好,存放入一个数组中S,以便随时获取。初始化构造函数时,若传入的初始化节点数字为n,则从S中取出最接近n且大于n的质数作为实际的表格大小。调整表格大小的判断条件当元素总数大于表格大小时,即‘负载系数’大于1时,开始创建新表格,找出下一个质数,然后把原表格中数据挨个拷贝到新的地址空间(非简单拷贝,还需要通过hash函数判定地址)。

2.2.2、相关函数

1、insert_unique(): 插入操作,不允许hashtable中已有相同键值的元素。

2、insert_equal(): 插入操作,允许hashtable中已有相同键值元素。

3、size(): 返回表格的大小值

4、max_size(): 返回size_type(-1) 即无符号数的最大整数

5、iterator find(constkey_type& key):返回相应键值的位置索引

6、size_type count(constkey_type& key): 返回相应键值出现的个数

2.2.3、数据类型

Hashtable不能处理string、double、float等类型。只能处理以下类型:char*、short、int (以上三个元素包含const 和unsigned)

2.3、hash_set\hash_multiset

    hash_set和hash_multiset均采用hashtable作为底层数据结构,且都采用hashtable的相关接口函数实现自己的功能。另外两者没有自动排序功能。键值和实值相同。

    两者唯一的区别是:hash_set插入元素的操作采用底层机制hashtable的insert_unique(),而后者采用insert_equal()。

2.4、hash_map\hash_multimap

     hash_map和hash_multimap均采用hashtable作为底层数据结构,且都采用hashtable的相关接口函数实现自己的功能。另外两者没有自动排序功能。键值和实值不相同。

    两者唯一的区别是:hash_map插入元素的操作采用底层机制hashtable的insert_unique(),而后者采用insert_equal()。

 

《STL源码剖析》学习笔记系列之五——关联式容器(2)