完美哈希虽然做到了查询时间复杂度O(1),但是在建立映射表时就比较大费周折了,要随机的产生映射函数。
所以,正如书中所言,是一种适合静态数据的访问的数据结构。树上的例子是编译器的程序语言保留字集合、还有CD-ROM上的文件查询。
首先是,实际真的有人这么实现么?感觉有点大材小用。
第二,有没有其他什么应用场景,使用完美哈希具有较强的优势?
完美哈希的应用场景
|
完美哈希虽然做到了查询时间复杂度O(1),但是在建立映射表时就比较大费周折了,要随机的产生映射函数。
|
浏览器项目中,HTML文档解析步骤。
解析html得到一个字符串,需要根据字符串来判别是否有效html标签/属性,并生成相应对象。
最朴实方案:
if (token == "img")
elseif (token == "table")
elseif .....
使用完美hash来做,效率提升在10倍左右。
经过我测试,哈希表建的比较大,在比较随机的情况下性能并不差。即便哈希表快满了,开始有冲突了,跳转的次数的期望也是比较小的(1/(1-a)),一般情况也就1到2次撑死了4次。所以我觉得并不需要完美哈希这玩意,没什么特别强的优势。上面说的浏览器那个什么的,个人认为用普通的哈希表也完全能够胜任的。
> 我来回应