Hashtable

2.1 简介

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

1、        线性探测法

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

2、        二次探测法

   二次探测法主要为了解决主集团问题（连续空间被占据，后续插入的结点依然被插入于该连续空间的边缘），该方法依次尝试H+1，H+2²，H+3³等位置。

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）