本文主要是介绍【STL源码剖析】第五章 关联式容器 之 hashtable底层实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hashtable
二叉搜索树具有对数平均时间的表现，但这种的表现构造在一个假设上：输入数据有足够的随机性。这一节介绍一种名为hastable（散列表）的数据结构，这种结构在插入、删除、搜寻等操作上也具有“常数平均时间”的表现，而这种表现是以统计为基础的，不需仰赖输入元素的随机性。
hashtable概述
hashtable通过hash function将元素映射到不同的位置，但当不同的元素通过hash function映射到相同的位置时，便产生了“碰撞”问题。解决碰撞问题的方法主要有线性探测、二次探测、开链法等。
线性试探
负载系数：意指元素个数除以表格大小。负载系数永远在0~1之间，除非采用开链策略。
当hash function计算处某个元素的插入位置，而该位置上的空间不再可用时，最简单的办法就是循序往下一一寻找（如果到达尾端，就绕过头部继续寻找），直到找到一个可用的空间为止。只要表格足够大，总是能够找到一个i安身立命的空间，需要花费的时间就很难说了。进行元素搜索操作时，道理也相同，如果hash function计算出来的位置上的元素与我们搜寻目标不符，就循序往下一一寻找，直到找到吻合者，或直到遇上空格元素。至于元素的删除，必须采用惰性删除，也就是只标记删除记号，实际删除操作则待表格中心整理时再进行——这是因为hash table中的每一个元素不仅表述自己，也关系到其它元素的排列。
欲分析线性探测的表现，需要两个假设：（1）表格足够大；（2）每个元素都独立。在此假设下，最坏的情况是线性巡防整个表格，平均情况则是寻访一半表格，和常数实际时间差已经很大了。会造成主集团（primary clustering）问题。
二次试探
二次试探发主要用来解决primary clusterign问题。其命名由来是因为解决碰撞问题的方程式F(i)=i^2是个二次方程式。明确地说，如果hash function计算出来新元素的位置为H，而该位置实际上已被使用，那么就依序尝试H+1^2,H+2^2,H+3^2,……，H+i^2，而不是像线性探测那样依序尝试H+1,H+2,H+3，……，H+i。
这篇关于【STL源码剖析】第五章 关联式容器 之 hashtable底层实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
