完美散列

✍ dations ◷ 2025-03-23 14:55:28 #散列,散列函数,搜寻算法

对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致,但不需要任何冲突解决方案。在数学术语中,这是一个完全单射函数.

对于特定集合S的完美散列函数能在常数时间中被计算出,其映射值在一个相对小的范围内,能被一个随机化算法发现,该算法的操作次数与S的大小成正比.任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。

一个值的位数被限定范围的完美散列函数能应用于高效查找操作中:假定查找键(key)与集合S(或与集合S关联的值)对应,然后将完美散列函数应用于查找键,得到哈希值(一个整数),然后在查找表中取出该整数对应的值。在集合S极少更新且查询频率非常多的情况下,使用完美hash函数是非常有效的。对集合S更新频率的限定是由于对任何集合S的修改,都将导致该完美散列函数退化为非完美散列函数。每次集合S被修改后自动更新hash函数的解决方案被称为dynamic perfect hashing,但这类方法非常复杂,难以实现。一个简单的允许动态更新集合S的完美散列函数的替代品叫cuckoo hashing。

最小完美散列函数是一个能将个键(key)映射到个连续的整数的完美散列函数。 产生的值通常为 或 。正式表述如下:设和是有限集合K的两个元素。F是一个最小完美散列函数iff F()=F()只在=的情况下成立(单射);并且存在整数,使得F的范围为..+|K|−1。已经在数学上证明,通用的完美hash函数至少需要每个键(key)1.44 比特(bit) 。而当前已知的最小完美hash散列函数每个键需要2.6 比特。

对一个最小完美散列函数F,若键以1, 2, ..., 次序给出,对任意键 and , <,意味着F()<F(). Order-preserving minimal perfect hash functions require necessarily Ω( log ) bits to be represented.,我们称该最小完美散列函数F是保序的。

若对一个最小完美散列函数F,其应用变换后得到的值保持了键(key)的字典序,我们称该最小完美散列函数F为单调的。在此情况下,函数产生的值就是输入的键在所有可能的有序键序列中的位置。若被hash的键被存储于有序数组中,已实现一种策略,对每个键存储少量附加位(bits),以取得更快计算hash值的优势。


相关

  • 神秘主义神秘主义(英语:Mysticism),也有较模糊的称为密契主义,包涵人类与神明或某种超自然力量结合为一的各种形式、经验、体验,并且强调这是一切宗教共有的现象。神秘主义者的基本信条是
  • 氯甲烷一氯甲烷又称甲基氯,无色、可燃、有毒气体,属有机卤化物。分子式是CH3Cl,分子量是50.49。主要用于生产甲基氯硅烷、聚硅酮、四甲基铅(汽油抗爆剂)、甲基纤维素。少量用于生产季
  • 安森美安森美半导体(ON Semiconductor,NASDAQ:ON)是一家财富美国500强半导体供应商。公司的产品系列包括电源和信号管理、逻辑、分立及定制器件,帮助客户解决他们在汽车、通信、计算机
  • 拜伦·多甘拜伦·多甘(Byron Dorgan;1942年5月14日-)是美国的一位政治人物。在1992年至2011年期间,他是北达科他州的两位参议院议员之一。他的党籍是民主党。在成为参议员之前,他曾经担任12
  • 磷酸氢钙磷酸氢钙是一种化合物,通常以二水合物(其化学式为 CaHPO4 · 2H2O )的形式存在,但可经由加热变成无水的形式。磷酸氢钙几乎不溶于水,在 25 °C 时的溶解度只有 0.02 g/100 mL 。
  • 阴部除毛阴部除毛指的是完全或部分除去生殖器周围的阴毛。 通常是为了达到美观的需求。英语为“Removing pubic hair”但通常会使用详细的除毛方法来指不同种类的阴部除毛,例如:使用“
  • 菲利普·拉金菲利普·拉金,CH,CBE,FRSL(Philip Larkin,1922年8月9日-1985年12月2日),20世纪后半叶英国著名诗人,小说家、爵士乐评论家。1955年以第二部诗集《少受欺骗者》获得关注,之后又出版了《
  • 浅野幸长和歌山県和歌山市吹上大泉寺父:浅野长政幸长、长晟、长重、堀亲良室、浅野幸长(1576年-1613年)为安土桃山时代到江户时代初期的武将‧大名。纪伊国和歌山藩(纪州藩)初代藩主,浅野氏
  • 云田镇 (陇西县)云田镇,是中华人民共和国甘肃省定西市陇西县下辖的一个乡镇级行政单位。云田镇下辖以下地区:北站村、石家门村、杜家门村、三湾村、咀头村、二十铺村、三十铺村、神家川村、上
  • 爆丸2大爆破《爆丸2大爆破》(日语:爆丸バトルブローラーズ ニューヴェストロイア;英文:Bakugan Battle Brawlers New Vestroia)是一套由2009年4月至2010年5月间,开始在加拿大播放的动画。为《