论文标题
一种用于获得记忆约束接近完美哈希的遗传算法
A Genetic Algorithm for Obtaining Memory Constrained Near-Perfect Hashing
论文作者
论文摘要
从固定集合中检索的快速项目的问题通常在大多数计算机科学领域都遇到，从操作系统组件到数据库和用户界面。我们提出了一种基于哈希表的方法，该方法既着重于最大程度地减少搜索过程中执行的比较数量以及最小化总收集大小。通过非线性转换可以进行参数化，以确保哈希表中的数据均匀分布，从而改善了标准的开放式双锤方法。使用遗传算法确定最佳参数。论文结果表明，接近完美的哈希速度比二进制搜索要快，但使用的内存而不是完美的哈希，这是搜索时间也很关键的内存约束应用程序的好选择。
The problem of fast items retrieval from a fixed collection is often encountered in most computer science areas, from operating system components to databases and user interfaces. We present an approach based on hash tables that focuses on both minimizing the number of comparisons performed during the search and minimizing the total collection size. The standard open-addressing double-hashing approach is improved with a non-linear transformation that can be parametrized in order to ensure a uniform distribution of the data in the hash table. The optimal parameter is determined using a genetic algorithm. The paper results show that near-perfect hashing is faster than binary search, yet uses less memory than perfect hashing, being a good choice for memory-constrained applications where search time is also critical.
