Expected Length of the Longest Probe Sequence in Hash Code Searching
From MaRDI portal
Publication:3906430
DOI10.1145/322248.322254zbMath0456.68067OpenAlexW2091323212WikidataQ60960861 ScholiaQ60960861MaRDI QIDQ3906430
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322248.322254
analysis of algorithmsasymptotic analysishashingopen addressingseparate chainingtable searchdirect chaining
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20) Theory of operating systems (68N25)
Related Items
Tight bounds for parallel randomized load balancing, Shortest paths in Euclidean graphs, Minimum multiplicity edge coloring via orientation, Gamma and Factorial in the Monthly, Analytical depoissonization and its applications, On the structure and complexity of worst-case equilibria, Scalable Load Balancing in Networked Systems: A Survey of Recent Advances, Security of Numerical Sensors in Automata, Concentration of maximum degree in random planar graphs, NON-BACKTRACKING RANDOM WALKS MIX FASTER, A geometric Achlioptas process, Constructing Voronoi diagrams from hollow spheres using conformal geometric algebra, Unnamed Item, Branch structure and implementation of Lambert \(W\), On the expected longest length probe sequence for hashing with separate chaining, On the average height of trees in digital search and dynamic hashing, Avoiding Communication in Primal and Dual Block Coordinate Descent Methods, Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances, The expected degree of noninvertibility of compositions of functions and a related combinatorial identity, A parallel tree difference algorithm, Self‐adjusting trees in practice for large text collections, Layered hashing algorithm for real-time systems, The Maximum Displacement for Linear Probing Hashing, Choice-memory tradeoff in allocations, Self-stabilizing balls and bins in batches. The power of leaky bins, Cuckoo hashing: Further analysis, Forward-reverse expectation-maximization algorithm for Markov chains: convergence and numerical analysis, On the Lambert \(w\) function, On the \(k\)-orientability of random graphs, Range minimum queries in minimal space, Hashing with Linear Probing under Nonuniform Probabilities, Structure and complexity of extreme Nash equilibria, Interpolation-based index maintenance, Two-way chaining for non-uniform distributions, On parallel time in population protocols, Maximum queue size and hashing with lazy deletion, Laws of large numbers and tail inequalities for random tries and PATRICIA trees
