本文主要是介绍【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底层实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!