1.原理讲解

 HashTable就是散列表((哈希表),将从下面几个方面来讲解散列表的原理

1.1散列表的概述

在说散列表之前,我们先说一下散列技术.
什么叫散列技术呢?一句话来说,散列技术是一种查找技术,而且是一种"一步到位"的查找技术
为什么可以一步到位呢?
在说散列技术之前,我们先回忆一下 顺序表查找 二分查找,插值查找这些查找技术是怎么操作的.
在这些查找技术中,我们先确定要查找的值key,然后在待查找的元素集合中与其中元素进行对比,然后找到要查找元素位置index
而散列技术是怎么操作的呢?
在散列查找技术中,不用逐个的对比,确定要查找的值key后,再通过一个函数f把key传进去计算,计算结果即要查找元素的位置index
总结一下就是说:
顺序/二分/差值查找:要查找元素key->与待查找集合中的元素对比->找到要查找元素的位置index
散列查找:要查找元素key->直接通过函数f计算出要查找元素的位置index   

这也就说明了用散列技术查找的时候,我们一开始存储元素就应该事先按照函数f所对应的规律去存储元素, ,使得我们存进去的元素key的位置是f(key),这样我们用函数f查找的时候才能奏效.所以说散列技术既是一种查找技术,也是一种存储技术.
这里的函数法f就叫散列函数(哈希函数),采用散列技术所建立的元素存储空间就是散列表(哈希表),元素的存储位置就叫散列地址(哈希地址)

 

1.2散列表的优缺点

优点:
1.简化了比较过程 效率大大提高.

缺点

1.散列技术不适合集合中重复元素很多的情形,因为这样的话同样的key,就会对应很多index,比如下面这种情况 

 
2.散列技术不适合范围查找 也不适合查找最大值,最小值.这些都无法从散列函数中计算出来.
3.散列函数需要很好的设计,应该保证简单 均匀 存储效率高
4.还有一个问题是冲突

 

1.3散列表的关键问题之散列函数的构建

散列函数应该满足什么样的特性呢?
首先应该计算简单,因为如果计算太复杂就会导致每次查找时计算散列地址耗费太多时间
其次应该保证计算出来的哈希地址空间分布均匀,这样可以节省空间,同时也减少了为处理冲突而耗费的时间.
 

 

            

• 直接定址法
• 数字分析法
  
• 平方取中法
  
• 折叠法
  
• 除留余数法
  
• 折叠法
  
• 随机数法

1.4散列表的关键问题之散列冲突的处理

在讨论散列技术的优缺点的时候 我们说其有一个缺点就是会产生冲突,即不同的key却会有相同的散列地址index
散列函数设计的再好也无法完全避免冲突,

• 线性探测法
  一旦发生该了冲突就去寻找下一个空的散列地址
  只要散列表足够大,空的地址一定能够找到.怎么样去寻找空的地址呢?
  线性探测法的思路是 碰到当前存储位置被占了,
  那就依次顺序线性的往下找,直到找到空的位置为止
  用数学表达式去表达就是
  
  举个例子
  
  上面我们说,散列技术的复杂度可以达到常数时间,但是用线性探测的话我们需要不断的解决冲突问题,
  所以在这种情况下,平均情况是线性巡防半个表格,最坏情况是线性巡防整个表格.远不及我们的期望时间.
  主要原因就在于每次插入元素时总是难以避免冲突,一旦碰到冲突就得不断解决碰撞问题,最后才找到一个空,
  在这个空里面安置了以后,又使主集团增大,又增加了下一次插入数据碰撞的概率.
  
   
• 二次探测法
  
   
• 随机探测法
  
• 再散列函数法
  
• 链地址法
  
  
   
• 公共溢出区法
  

1.5 散列表的性能分析

• 散列函数是否均匀
  
• 处理冲突的方法
  
• 散列表的装填因子
   

2.源码实现

2.1 节点定义

HashTable采用的是链地址法.
HashTable的散列表内每个节点被称为桶子bucket
散列表就是放bucket的vector
叫这个名字可能是因为表格内每个单元涵盖的可能不止一个结点,可能是一桶结点.

结点实现的源码如下

2.2 迭代器

2.3 数据结构

 

首先看它的模板参数,
模板参数挺多,包括如下


在<stl_hash_fun.h>文件中有定义有数个现成的hash_functions,用来计算查找元素的位置.
然后我们看它的buckets实现,可以看到buckets本质上就是一个vector
最后我们还要注意一点,虽然链地址法不要求表格大小必须为质数,但是SGI STL中仍然以质数来设计表格大小
并且将28个质数计算好,以备随时访问,用来查询在这28个质数中最接近并大于某数的质数

3.内存管理

3.1空间配置器 

HashTable里面定义了一个专属的节点配置器,用来更好的以结点为单位开辟空间
 
节点配置函数,

节点释放函数

3.2 构造函数
 

比如我要构造一个 拥有50个结点的哈希表,则按照下面的方式构造

 
这个构造函数有三个参数,第一个表示要构造哈希表结点多少,第二个是散列函数,即计算元素位置的函数型别
第三个是判断键值是否相等的方法,我们看一些这构造函数具体是如何执行的

本质上是调用了initialize_buckets,再看一下initialize_buckets是如何执行的

 
注:next_size(n)函数返回质数表中的是接近n但是大于n的质数
可以看到在initialize_buckets中,先计算了接近n的质数buckets空间大小,然后在里面都填充了类型为node*的空指针

3.3 插入函数insert

用insert_unique 函数来插入节点,得保证插入元素不重复
在insert_unique插入结点时,先判断要不要扩充重建buckets  vector,
判断依据是如果插入后元素个数大于buckets vector大小,则重建表格,否则返回
重建过程先找到下一个质数做为新的buckets vector大小,然后建立新的buckets vector
建立新的buckets vector的过程如下


整个重建过程的源码如下


如果不需要重建,或者重建完成了以后,在去执行插入新节点操作(需要保证插入结点不重复)

3.4 元素地址求解函数bkt_num

求解元素地址就是求出元素位于哪一个bucket内,这本来是hash_function的任务,SGI把这个任务封装了一层,先交给bkt_num
再由此函数调用hash_function 取得一个可以执行的,
为什么要这么做呢?因为有些元素比如字符串,无法直接拿来对hash_table的大小进行取模运算.这个时候就要通过bkt_num函数先进行一些转换.

 

上面所说的调用的<stl_hash_fun.h>定义有数个现成的hash functions .
针对char int long等整数类型 hash function 什么也没做,只是返回原值
针对字符数组const char* 有一个转换过程,见下面的源码
 

由上面可知,hashtable无法处理上述所列各项型别以外的元素
例如string double float ,x想要处理这些类型,必须自己为他们定义hash fu

 

3.5 整体删除clear

 

3.6 复制copy_from

 

3.7 查找find函数

3.8  计数count函数

4.使用

 

5.参考
 

1.侯捷<<STL源码剖析>>