- [1] Dietzfelbinger and Meyer auf der Heide. How to distribute a dictionary on a complete network. In Proceedings of 22nd Annual ACM Symposium on Theory of Computing, 1990. Google ScholarDigital Library
- [2] Dietzfelbinger and Meyer auf der Heide. A new class of universal hash functions and dynamic hashing in real time. to appear in ICALP 1990. Google ScholarDigital Library
- [3] Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert, and Tarjan. Dynamic perfect hashing: upper an lower bounds. In 29th Annual Symposium on Foundations of Computer Science, pages 524-531, Oct. 1988.Google Scholar
- [4] Fredman, Komlós, and Szemerédi. Storing a sparse table with O(1) worst case access time. Journal of The Association for Computing Machinery, 31(3):538-544, July 1984. Google ScholarDigital Library
- [5] Joseph Gil and Yossi Matias. o(log log n) time hashing on pram. Mar. 1990. In preparation.Google Scholar
- [6] Anna Karlin and Eli Upfal. Parallel hashing-- an efficient implementation of shared memory. In 18th Annual ACM Symposium on Theory of Computing, pages 160-168, May 1983. Google ScholarDigital Library
- [7] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin Heidelberg, 1984.Google Scholar
- [8] Michael Sipser. A complexity approach to randomness. In Proceedings of 15th Annual ACM Symposium on Theory of Computing, pages 330-335, April 1983. Google ScholarDigital Library
- [9] Larry Stockmeyer. A complexity approach to randomness. In Proceeding of 15th Annual ACM Symposium on Theory of Computing, pages 118-126, April 1983.Google Scholar
- [10] Andrew Chi-Chih Yao. Should tables be sorted? Journal of The Association for Computing Machinery, 28(3):615-628, July 1981. Google ScholarDigital Library
Index Terms
- Not all keys can be hashed in constant time
Recommendations
Upper bounds for constant-weight codes
Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n⩽24 and d⩽12, which is the parameter range of existing ...
Partially persistent data structures of bounded degree with constant update time
The problem of making bounded in-degree and out-degree data structures partially persistent is considered. The node copying method of Driscoll et al. is extended so that updates can be performed in worst-case constant time on the pointer machine model. ...
Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity
SIGMOD '22: Proceedings of the 2022 International Conference on Management of DataHashing is a widely used technique for creating uniformly random numbers from arbitrary data. This is required in a large range of core data-driven operations including indexing, partitioning, filters, and sketches. As such, hashing is a core component ...
Comments