fbpx
维基百科

完美散列

九月 24, 2023

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

特性及使用 编辑

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

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

最小完美散列函数 编辑

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

对一个最小完美散列函数F，若键以a1, a2, ..., an次序给出，对任意键aj and ak, j<k，意味着F(aj)<F(ak).[4] Order-preserving minimal perfect hash functions require necessarily Ω(n log n) bits to be represented.[5]，我们称该最小完美散列函数F是保序的。

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


请参阅 编辑

  • Dynamic perfect hashing
  • Pearson hashing
  • Succinct data structure
  • Universal hashing

索引 编辑

  1. ^ Fredman, M. L.; Komlós, J. N.; Szemerédi, E. Storing a Sparse Table with 0(1) Worst Case Access Time. Journal of the ACM. 1984, 31 (3): 538. doi:10.1145/828.1884. 
  2. ^ Belazzougui, D.; Botelho, F. C.; Dietzfelbinger, M. Hash, Displace, and Compress. Algorithms - ESA 2009 (PDF). LNCS 5757. 2009: 682 [2016-02-13]. ISBN 978-3-642-04127-3. doi:10.1007/978-3-642-04128-0_61. （原始内容 (PDF)于2011-07-24）. 
  3. ^ Baeza-Yates, Ricardo; Poblete, Patricio V., Searching, Atallah, Mikhail J.; Blanton, Marina (编), Algorithms and Theory of Computation Handbook: General Concepts and Techniques 2nd, CRC Press, 2010, ISBN 9781584888239 . See in particular p. 2-10
  4. ^ Jenkins, Bob, order-preserving minimal perfect hashing, Black, Paul E. (编), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, 14 April 2009 [2013-03-05], （原始内容于2009-01-30） 
  5. ^ Fox, E. A.; Chen, Q. F.; Daoud, A. M.; Heath, L. S. Order preserving minimal perfect hash functions and information retrieval. Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '90. 1990: 279. ISBN 0897914082. doi:10.1145/96749.98233. 
  6. ^ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano, Theory and practice of monotone minimal perfect hashing, Journal of Experimental Algorithmics, November 2008, 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378 .

延伸内容 编辑

  • Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple, Communications of the ACM, Vol. 23, Number 1, January 1980.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 11.5: Perfect hashing, pp. 245–249.
  • Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani. "Perfect Hashing for Data Management Applications".
  • Fabiano C. Botelho and Nivio Ziviani. "External perfect hashing for very large key sets"（页面存档备份，存于互联网档案馆）. 16th ACM Conference on Information and Knowledge Management (CIKM07), Lisbon, Portugal, November 2007.
  • Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. . In Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA), New York, 2009. ACM Press.
  • Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. . In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2009.
  • Douglas C. Schmidt, , C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.

外部链接 编辑

九月 24, 2023
完美散列, 此條目目前正依照en, perfect, hash, function上的内容进行翻译, 2016年2月13日, 如果您擅长翻译, 並清楚本條目的領域, 欢迎协助翻譯, 改善或校对本條目, 此外, 长期闲置, 未翻譯或影響閱讀的内容可能会被移除, 对集合s的函数是一个将s的每个元素映射到一系列无冲突的整数的哈希函数, 一个函数的应用与其他哈希函数的应用基本一致, 但不需要任何冲突解决方案, 在数学术语中, 这是一个完全单射函数, 目录, 特性及使用, 最小函数, 请参阅, 索引, 延伸内容, 外部链接特. 此條目目前正依照en Perfect hash function上的内容进行翻译 2016年2月13日 如果您擅长翻译 並清楚本條目的領域 欢迎协助翻譯 改善或校对本條目 此外 长期闲置 未翻譯或影響閱讀的内容可能会被移除 对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数 一个完美散列函数的应用与其他哈希函数的应用基本一致 但不需要任何冲突解决方案 在数学术语中 这是一个完全单射函数 目录 1 特性及使用 2 最小完美散列函数 3 请参阅 4 索引 5 延伸内容 6 外部链接特性及使用 编辑对于特定集合S的完美散列函数能在常数时间中被计算出 其映射值在一个相对小的范围内 能被一个随机化算法发现 该算法的操作次数与S的大小成正比 1 任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数 一个值的位数被限定范围的完美散列函数能应用于高效查找操作中 假定查找键 key 与集合S 或与集合S关联的值 对应 然后将完美散列函数应用于查找键 得到哈希值 一个整数 然后在查找表中取出该整数对应的值 在集合S极少更新且查询频率非常多的情况下 使用完美hash函数是非常有效的 对集合S更新频率的限定是由于对任何集合S的修改 都将导致该完美散列函数退化为非完美散列函数 每次集合S被修改后自动更新hash函数的解决方案被称为dynamic perfect hashing 但这类方法非常复杂 难以实现 一个简单的允许动态更新集合S的完美散列函数的替代品叫cuckoo hashing 最小完美散列函数 编辑最小完美散列函数是一个能将n个键 key 映射到n个连续的整数的完美散列函数 产生的值通常为 0 n 1 或 1 n 正式表述如下 设j和k是有限集合K的两个元素 F是一个最小完美散列函数iff F j F k 只在j k的情况下成立 单射 并且存在整数a 使得F的范围为a a K 1 已经在数学上证明 通用的完美hash函数至少需要每个键 key 1 44 比特 bit 2 而当前已知的最小完美hash散列函数每个键需要2 6 比特 3 对一个最小完美散列函数F 若键以a1 a2 an次序给出 对任意键aj and ak j lt k 意味着F aj lt F ak 4 Order preserving minimal perfect hash functions require necessarily W n log n bits to be represented 5 我们称该最小完美散列函数F是保序的 若对一个最小完美散列函数F 其应用变换后得到的值保持了键 key 的字典序 我们称该最小完美散列函数F为单调的 在此情况下 函数产生的值就是输入的键在所有可能的有序键序列中的位置 若被hash的键被存储于有序数组中 已实现一种策略 对每个键存储少量附加位 bits 以取得更快计算hash值的优势 6 请参阅 编辑Dynamic perfect hashing Pearson hashing Succinct data structure Universal hashing索引 编辑 Fredman M L Komlos J N Szemeredi E Storing a Sparse Table with 0 1 Worst Case Access Time Journal of the ACM 1984 31 3 538 doi 10 1145 828 1884 Belazzougui D Botelho F C Dietzfelbinger M Hash Displace and Compress Algorithms ESA 2009 PDF LNCS 5757 2009 682 2016 02 13 ISBN 978 3 642 04127 3 doi 10 1007 978 3 642 04128 0 61 原始内容存档 PDF 于2011 07 24 Baeza Yates Ricardo Poblete Patricio V Searching Atallah Mikhail J Blanton Marina 编 Algorithms and Theory of Computation Handbook General Concepts and Techniques 2nd CRC Press 2010 ISBN 9781584888239 See in particular p 2 10 Jenkins Bob order preserving minimal perfect hashing Black Paul E 编 Dictionary of Algorithms and Data Structures U S National Institute of Standards and Technology 14 April 2009 2013 03 05 原始内容存档于2009 01 30 Fox E A Chen Q F Daoud A M Heath L S Order preserving minimal perfect hash functions and information retrieval Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval SIGIR 90 1990 279 ISBN 0897914082 doi 10 1145 96749 98233 Belazzougui Djamal Boldi Paolo Pagh Rasmus Vigna Sebastiano Theory and practice of monotone minimal perfect hashing Journal of Experimental Algorithmics November 2008 16 Art no 3 2 26pp doi 10 1145 1963190 2025378 延伸内容 编辑Richard J Cichelli Minimal Perfect Hash Functions Made Simple Communications of the ACM Vol 23 Number 1 January 1980 Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Section 11 5 Perfect hashing pp 245 249 Fabiano C Botelho Rasmus Pagh and Nivio Ziviani Perfect Hashing for Data Management Applications Fabiano C Botelho and Nivio Ziviani External perfect hashing for very large key sets 页面存档备份 存于互联网档案馆 16th ACM Conference on Information and Knowledge Management CIKM07 Lisbon Portugal November 2007 Djamal Belazzougui Paolo Boldi Rasmus Pagh and Sebastiano Vigna Monotone minimal perfect hashing Searching a sorted table with O 1 accesses In Proceedings of the 20th Annual ACM SIAM Symposium On Discrete Mathematics SODA New York 2009 ACM Press Djamal Belazzougui Paolo Boldi Rasmus Pagh and Sebastiano Vigna Theory and practise of monotone minimal perfect hashing In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments ALENEX SIAM 2009 Douglas C Schmidt GPERF A Perfect Hash Function Generator C Report SIGS Vol 10 No 10 November December 1998 外部链接 编辑Minimal Perfect Hashing 页面存档备份 存于互联网档案馆 by Bob Jenkins gperf 页面存档备份 存于互联网档案馆 is an Open Source C and C perfect hash generator cmph 页面存档备份 存于互联网档案馆 is Open Source implementing many perfect hashing methods Sux4J 页面存档备份 存于互联网档案馆 is Open Source implementing perfect hashing including monotone minimal perfect hashing in Java MPHSharp is Open Source implementing many perfect hashing methods in C 取自 https zh wikipedia org w index php title 完美散列 amp oldid 67588040, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。