...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Tetris-Hashing or optimal table compression
【24h】

Tetris-Hashing or optimal table compression

机译：俄罗斯方块哈希或最佳表压缩

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we present a new method for mapping a static set of n keys, each an integer between 0 and N - 1, into a hash table of size n without any collision. Our data structure requires only an additional array of n integers, each less than n, and achieves a worst-case lookup time of O(1). This method is based on a randomized compression scheme, and it finds a minimal perfect hash function in average time O(n). Our concept can be easily adapted for dynamic key sets. Then, the hash table has no longer minimal size but the storage location remains very small. Because of its simplicity our approach is particularly interesting for practical purposes.
机译：在本文中，我们提出了一种新方法，可将n个键的静态集合（每个键在0到N-1之间）映射到大小为n的哈希表中而不会发生任何冲突。我们的数据结构仅需要n个整数的附加数组，每个整数都小于n，并实现最坏情况下的查找时间O（1）。该方法基于随机压缩方案，并且在平均时间O（n）中找到最小的完美哈希函数。我们的概念可以轻松地应用于动态键集。然后，哈希表不再具有最小大小，但是存储位置仍然很小。由于其简单性，我们的方法在实际应用中特别有趣。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号