完美散列

✍ dations ◷ 2025-07-26 21:43:37 #散列,散列函数,搜寻算法

对集合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值的优势。


相关

  • 路易·波拿巴路易·波拿巴(Louis Napoléon Bonaparte,1778年9月2日-1846年7月25日),任荷兰国王时称路德维克一世,法国皇帝拿破仑一世的弟弟。妻子是拿破仑的继女,约瑟芬和前夫博阿尔内所生的女
  • 乙部,是为汉字索引中的部首之一,康熙字典214个部首中的第五个(一划的则为第五个)。就正体中文中,乙部归于一划部首。而简体部首称“乛部”,而乙为‘乛部’的附形部首。乙部通常从
  • 詹姆士·A·约克詹姆斯·阿兰·约克(英语:James Alan Yorke,1941年8月3日-),美国数学家和理论物理学家,马里兰大学学院市分校数学和物理和数学系前任系主任。他和本华·曼德博是2003年日本国际奖科
  • 李红良李红良(1974年9月-),中国生物学家,武汉大学教授,长江学者特聘教授。现任武汉大学基础医学院长、武汉大学模式动物研究所所长。2018年,他被武汉大学千人计划专家霍文哲实名举报涉嫌
  • 宜兰美术馆宜兰美术馆是位于台湾宜兰县宜兰市中山路三段1号的一座美术馆。台湾银行宜兰出张所设立于1898年,1906年因位于东门街旧址空间过于狭隘,重新择定南门现址,基地紧邻城垣并以新样
  • U型谷冰川谷(又称U形谷、冰川槽谷)是冰川侵蚀作用形成的谷地。它的山谷陡峭,谷底平缓,横剖面呈抛物线形,类似字母U。当冰川顺着倾斜的山坡向下移动,山谷就会被冲刷、侵蚀。等到冰川融化
  • 加法尔·巴巴敦加法尔·巴巴(Tun Abdul Ghafar bin Baba,1925年2月18日-2006年4月23日),马来西亚第六任副总理(1986年—1993年),于森美兰瓜拉庇劳县出生。其父早逝,留下他和九个弟妹。为了赚钱养
  • 周二珂周二珂(1994年1月6日-),原名周可,中国网络主播、歌手,出生于广东省湛江市赤坎区。曾就读北京现代音乐学院爵士演唱系(2015年2月退学)。她最初为斗鱼TV女主播,曾与当时的陈一发、大
  • 韦秀韦秀(?-740年4月29日),京兆郡杜陵县(今陕西省西安市长安区)人,出自京兆韦氏彭城公房,唐玄宗李隆基的妃子,唐中宗和韦皇后外孙女,彭城郡公韦鐬之女,永寿公主所生。出自京兆韦氏彭城公房,深
  • 戴钤戴钤(1796年11月19日-19世纪),字豹臣,号渔溪,四川省潼川府中江县人,民籍。清朝政治人物。曾祖惟楫,祖濂、父文仪,母赵氏,妻杨氏,子之癸。行一,清嘉庆元年丙辰十月二十日(1796年11月19日)生