hashtable

一.hashtable概述

hashtable是一种在插入、删除、搜寻等操作上具有常数平均时间的数据结构，原理是hashtable利用散列函数把每一个值映射到另一个值上形成一一对应的关系，类似于索引，所以可以直接查索引。

二.解决相同索引

使用hashtable有一个不可避免的问题，即不同的元素可能映射到相同的位置，即具有相同的索引。因为元素的数量大于容器的数量这个问题只能尽力避免。解决问题的方法有很多种，如线性探测，二次探测，开链等。

线性探测

首先认识一个新名词：负载系数：指表中已有的元素个数除以表格大小，永远在0到1之间（除非使用开链）。

线性探测解决碰撞的方法就是当插入时产生碰撞了，循序往下查找空格位置进行插入。进行元素搜寻时，如果映射位置不是该元素，循序往下查找直到空格。删除时采用惰性删除，即做一个删除标记，表格重新整理的时候再删除，这样做的原因是hashtable中的元素会影响其他元素排列，例如如果直接删除了，那其他映射到这个位置但是存储在其他位置的元素就搜寻不到了。

线性探测的缺点在于一种叫做主集团现象，即随着插入元素的增多，主集团增大，之后每次插入要花更多时间探测的可能性增大，即平均插入的成长幅度原高于负载系数的成长幅度，且每次插入又增大了主集团。

二次探测

二次探测主要解决主集团的entity，即现在不是一个一个往下探寻了，即线性探测是H+1,H+2,H+3…二次探测是H+i^2，这样每次跳的步数多了，更容易找到空格，且不会和原来的元素形成主集团。

如果表格大小为质数，且永远保持负载系数在0.5以下，那么在二次探测中每插入一个新元素所需要的探测系数不多于2.

至于实现的复杂度，有一个简化的算法，即利用前一个算出的结果算后一个，具体看书。

二次探测的问题在于次集团（还有每次rehashing的成本）：即若两个元素进散列函数算出的位置相同，则每次探测的位置也相同，造成浪费。

开链

开链就是在每一个表格元素中维护一个list，然后我们在这个list身上执行插入，搜寻，删除，不过list的搜寻只能是一种线性操作。

使用开链的话hashtable的负载系数将可以大于1，SGI STL 的hashtable就是使用的开链。

三.hashtable的桶子与节点

我们把hashtable中的每个元素成为桶子表示每个单元不止存放一个元素，而是一桶节点。hashtable节点的定义是普通的list的结点的定义，一个数据域一个next指针，存放整个桶子聚合体的是vector。

四.hashtable的迭代器

hashtable的迭代器始终维持这它与一个桶子聚合体的关系，然后里面的cur指针指向一个节点，在++操作中，首先判断当前桶子是否还有元素，如果没有，则跳到下一个桶子直到有元素，注意，桶子所在vector的序号其实是不重要的，因为这可以根据cur指针所指的值算出来，还可以通过序号得到一个cur指针。

五.hashtable的数据结构

hashtable的数据结构没什么好说的，就是用vector来存储桶子，元素是节点的一个指针，注意hashtable的参数。

value：实值 key：键值 hashfcn：散列函数的函数类别 extractkey：从节点中取出键值的方法 equalkey：判断键值是否相同

SGI STL以质数来设计vector存储的hashtable，事先准备好了一个质数的数组，到时候需要重新配置的时候利用一个函数找到最接近又较大的质数进行配置。

六.hashtable的构造与内存管理

首先有一个节点配置器，节点的配置也很简单，就是分配空间构造函数，析构函数释放空间。

然后是整个hashtable的构造，当新建一个hashtable并确定桶子数量时，新建的hashtable会自动找到接近并大于该数的质数然后建立这么多桶子，并且全部初始化为0.

插入操作(insert)与表格重整(resize)

插入操作分为允许插入相同键值或不允许插入相同键值，无论哪种情况，都要先判断是否进行表格重整。

表格重整的判断标准比较奇特，因为按道理来说，SGI STL采用开链的方法，可以一直增长链表不用重新配置，但是考虑到链表过长搜索时间也过长所以当元素个数超过vector大小就重新配置。

重新配置的方法就是新开一个vector，然后利用链表的指针重新指向配置好新的vector，然后利用swap函数交换新老vector（swap在这里的原理是交换了几个关键的迭代器，毕竟vector就靠那几个关键的迭代器标识）。

插入操作就先找到桶子号，然后搜寻链表找有没有（或找位置）相同键值的。

注意：表格重整时是重新算了索引的。

判知元素的落脚处（bkt_num）

bkt_num函数的主要作用是判断元素的桶子号（或者说索引，索引和键值不是一个东西，键值可以说是关系表中的主码，而索引是用来找元组的，即键值是本身有的一个东西，而索引是外界加上的，但是大多数时候还是利用键值来算索引的，毕竟键值相同一般要保证索引相同）。判断索引是散列函数的责任（hash function）但是这里用bkt_num做了一层封装，主要是有点元素型别无法直接用散列函数。bkt_num和散列函数都有很多版本。

整体删除(clear)和复制(copy_from)

整体删除就是对每个桶子的每个节点删除，但是注意整体的vector是没有被删除的。

复制是先调用整体删除清空当前vector，然后看是否要重新配置，然后每个桶子每个节点的复制过来。

七.hash functions

散列函数是用来得到一个值的，在SGI STL中散列函数得到的这个值去模桶子的个数得到索引，在hash functions中大多数是直接返回值，对于char*有特殊的处理，而且没有定义string，double，float的散列函数，所以这几个是不能作为值类型的。

八.小结

hashtable是通过(键)值建立索引进而使得搜寻为常数时间的数据结构，在SGI STL中的实现为开链的方式。

九.补充

hash_set

使用set的目的是为了更快的搜寻元素，这一点set和hashset都可以做到，不过set使用RB-tree作为底层容器有排序的功能，而hashset没有，hashset使用hashtable作为底层容器，使用的功能几乎都是hashtable转调过来的。当然也具有set的特性，即键值即实值，实值即键值。

hash_map

map和set的不同就是map即有键值又有实值（这个可以通过把value_type弄成pair实现），功能基本也是调用hashtable实现，搜寻效率也很高。也没有排序功能。

hash_multiset，hash_multmap

这两个跟上面那两个差不多，不过允许键值重复，即insert的时候用的是insert_equal。