Linear Max Load and Additive StructureResearch Paper
A hash function compresses a large universe into a small number of bins, and its quality is judged by how evenly it spreads a set of inputs. For a set of items hashed into bins by a fully random function, the expected size of the fullest bin, the expected max load, is . Fully random functions are expensive in time, space and…