Tag: hashing

Hash tables changed search by using extra memory and a computed address to make dictionary operations expected constant time, turning collision handling and load factor into central design choices.

Burton Bloom's 1970 filter represented set membership in a compact bit array, allowing false positives but no false negatives and creating a durable space-time tradeoff used across modern storage systems.