A New Universal Class of Hash Functions and Dynamic Hashing in Real Time

No abstract is available for this paper.

• Publication year

  1990

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  1990-07-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BFb0032018
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Not all keys can be hashed in constant time

  1990cited by this paper
• A Complexity Theory of Efficient Parallel Algorithms

  1990cited by this paper
• How to distribute a dictionary in a complete network

  1990cited by this paper
• On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications

  1989cited by this paper
• An optimal parallel dictionary

  1989cited by this paper
• The Generation of Random Permutations on the Fly

  1988cited by this paper
• Dynamic perfect hashing: upper and lower bounds

  1988cited by this paper
• How to emulate shared memory (Preliminary Version)

  1987cited by this paper
• Probabilistic Analysis of Algorithms

  1987cited by this paper
• Storing a dynamic sparse table

  1986cited by this paper
• Parallel hashing—an efficient implementation of shared memory

  1986cited by this paper
• Efficient Schemes for Parallel Communication

  1984cited by this paper
• Data Structures and Algorithms

  1983cited by this paper
• Storing a sparse table with O(1) worst case access time

  1982cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper

• Modern Minimal Perfect Hashing: A Survey

  2025cites this paper
• Text Indexing for Simple Regular Expressions

  2025cites this paper
• Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing

  2025cites this paper
• Optimal Non-oblivious Open Addressing

  2025cites this paper
• Faster Sliding Window String Indexing in Streams

  2024cites this paper
• Vizing’s Theorem in Near-Linear Time

  2024cites this paper
• A Micro-architecture that supports the Fano-Elias encoding and a hardware accelerator for approximate membership queries

  2024cites this paper
• On the Complexity of Computing the Co-lexicographic Width of a Regular Language

  2024cites this paper
• Locally Uniform Hashing

  2023cites this paper
• Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

  2023cites this paper
• Sliding Window String Indexing in Streams

  2023cites this paper
• Two-way Linear Probing Revisited

  2023cites this paper
• ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force

  2023cites this paper
• Dynamic Dictionary with Subconstant Wasted Bits per Key

  2023cites this paper
• ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force

  2023cites this paper
• A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits

  2022cites this paper
• Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations

  2022cites this paper
• Predecessor on the Ultra-Wide Word RAM

  2022cites this paper
• Making de Bruijn Graphs Eulerian

  2022cites this paper
• An extendable data structure for incremental stable perfect hashing

  2022cites this paper
• On the optimal time/space tradeoff for hash tables

  2021influential citation
• Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs

  2021cites this paper
• Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering

  2021cites this paper
• Constructing Strings Avoiding Forbidden Substrings

  2021cites this paper
• Iceberg Hashing: Optimizing Many Hash-Table Criteria at Once

  2021influential citation
• All-Purpose Hashing

  2021cites this paper
• A Space-Efficient Dynamic Dictionary for Multisets with Constant Time Operations

  2020cites this paper
• A Dynamic Space-Efficient Filter with Constant Time Operations

  2020cites this paper
• Succinct Filters for Sets of Unknown Sizes

  2020cites this paper
• Manycore clique enumeration with fast set intersections

  2020cites this paper
• Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses

  2019cites this paper
• String Processing and Information Retrieval: 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings

  2019influential citation
• Algorithms for Similarity Search and Pseudorandomness

  2019cites this paper
• Online Algorithms on Antipowers and Antiperiods

  2019cites this paper
• PIR with Compressed Queries and Amortized Query Processing

  2018cites this paper
• Efficient Computation of Sequence Mappability

  2018cites this paper
• Ja n 20 17 Fast and Powerful Hashing using Tabulation

  2018cites this paper
• Hashing, Load Balancing and Multiple Choice

  2017cites this paper
• A Simple Hash Class with Strong Randomness Properties in Graphs and Hypergraphs

  2016influential citation
• Prince: an effective router mechanism for networks with selfish flows

  2016cites this paper
• Optimal Dynamic Strings

  2015cites this paper
• Fast and powerful hashing using tabulation

  2015cites this paper
• Topics in combinatorial pattern matching

  2015cites this paper
• From Independence to Expansion and Back Again

  2015cites this paper
• A study of manycore shared memory architecture as a way to build SOC applications

  2015cites this paper
• Praktické datové struktury

  2015cites this paper
• On the Analysis of Two Fundamental Randomized Algorithms - Multi-Pivot Quicksort and Efficient Hash Functions

  2015cites this paper
• Thresholds for Matchings in Random Bipartite Graphs with Applications to Hashing-Based Data Structures

  2015cites this paper
• 1 Hash Tables

  2014cites this paper
• Various improvements to text fingerprinting

  2013cites this paper
• Properties of universal hashing

  2013cites this paper
• Òøø¹ôö×××øøò Àà×øóöý Áòòòôòòòòø Øø Ëøöù Blockinøùöö×

  2013cites this paper
• How to Approximate a Set without Knowing Its Size in Advance

  2013influential citation
• A Heaviest Hitters Limiting Mechanism with O(1) Time Complexity for Sliding-Window Data Streams

  2013cites this paper
• On Randomness in Hash Functions

  2012cites this paper
• we cover are basic chaining, perfect hashing, linear probing, and cuckoo hashing.

  2012cites this paper
• Time-Space Trade-Offs for Longest Common Extensions

  2012cites this paper
• Dynamic Hashing in Real Time 1

  2012cites this paper
• An Exact and O(1) Time Heaviest and Lightest Hitters Algorithm for Sliding-Window Data Streams

  2011cites this paper
• Balls and Bins: Smaller Hash Families and Faster Evaluation

  2011cites this paper
• Low-contention data structures

  2010cites this paper
• Hashing, randomness and dictionaries

  2010cites this paper
• 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit

  2009cites this paper
• Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

  2009influential citation
• Applications of a Splitting Trick

  2009cites this paper
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results

  2009cites this paper
• Hashing, contention, and cell-probe proofs

  2009cites this paper
• Lower bound techniques for data structures

  2008cites this paper
• Uniform Hashing in Constant Time and Optimal Space

  2008influential citation
• Computational geometry through the information lens

  2007cites this paper
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners

  2007cites this paper
• 5.2 Dynamic Matching 5.1 Parallel Static Dictionary Matching 3.2 Compressed Tries 4 Trie Based Dictionary Matching Algorithm 4.1 a Separator Decomposition Tree 3.1 Denition and Construction

  2007cites this paper
• A tight analysis of the (1 + 1)-EA for the single source shortest path problem

  2007cites this paper
• Computational Geometry through the Information Lens by Mihai Pǎtraşcu

  2007cites this paper
• Design Strategies for Minimal Perfect Hash Functions

  2007cites this paper
• Algorithm Engineering for the Basic Toolbox

  2007cites this paper
• Fully Dynamic Orthogonal Range Reporting on RAM

  2006cites this paper
• 2 Dictionary/membership Problem 3 Hashing with Chaining

  2005cites this paper
• De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)

  2005cites this paper
• De Dictionariis Dynamicis Pauco Spatio Utentibus

  2005cites this paper
• Two-Way Chaining with Reassignment

  2005cites this paper
• On Dynamic Dictionaries Using Little Space )

  2005cites this paper
• Balanced allocation on graphs

  2005cites this paper
• On dynamic range reporting in one dimension

  2005cites this paper
• In this lecture, we discuss hashing as a solution to dictionary/membership problem. Various results on hashing are presented with emphasis on static perfect hashing and Cuckoo hashing.

  2005cites this paper
• Mathematisches Forschungsinstitut Oberwolfach Report No . 41 / 2004 Mini-Workshop : Probability Theory on Trees and Analysis of Algorithms Organised

  2004cites this paper
• On Worst-Case Robin Hood Hashing

  2004cites this paper
• Two-way hashing with separate chaining and linear probing

  2004cites this paper
• Efficient hashing with lookups in two memory accesses

  2004cites this paper
• Generalized static orthogonal range search- ing in less space

  2003cites this paper
• Cuckoo hashing: Further analysis

  2003cites this paper
• Uniform hashing in constant time and linear space

  2003influential citation
• Simulating Uniform Hashing in Constant Time and Optimal Space

  2002cites this paper
• Automata, Languages and Programming

  2002influential citation
• Optimal Bounds for the Predecessor Problem and Related Problems

  2002cites this paper
• One-Probe Search

  2002cites this paper
• Efficient Minimal Perfect Hashing in Nearly Minimal Space

  2001cites this paper
• Cuckoo Hashing

  2001cites this paper
• Anti-persistence: history independent data structures

  2001cites this paper
• Faster suffix tree construction with missing suffix links

  2000cites this paper