hashing hashing dates to at least when luhn wrote an internal ibm memorandum that used separate chaining hashing early papers on hashing are [ and [ wealth of information on the subjectincluding an analysis of hashing with linear probing under the assumption of totally random and independent hashingcan be found in [ more recent results have shown that linear probing requires only -independent hash functions [ an excellent survey on early classic hash tables methods is [ ][ contains suggestionsand pitfallsfor choosing hash functions precise analytic and simulation results for separate chaininglinear probingquadratic probingand double hashing can be found in [ howeverdue to changes (improvementsin computer architecture and compilerssimulation results tend to quickly become dated an analysis of double hashing can be found in [ and [ yet another collision resolution scheme is coalesced hashingdescribed in [ yao [ has shown the uniform hashingin which no clustering existsis optimal with respect to cost of successful searchassuming that items cannot move once placed universal hash functions were first described in [ and [ ]the latter paper introduces the "carter-wegman trickof using mersenne prime numbers to avoid expensive mod operations perfect hashing is described in [ ]and dynamic version of perfect hashing was described in [ [ is survey of some classic dynamic hashing schemes the (log nlog log nbound on the length of the longest list in separate chaining was shown (in precise formin [ the "power of two choices,showing that when the shorter of two randomly selected lists is chosenthen the bound on the length of the longest list is lowered to only (log log )was first described in [ an early example of the power of two choices is [ the classic work on cuckoo hashing is [ ]since the initial papera host of new results have appeared that analyze the amount of independence needed in the hash functions and describe alternative implementations [ ][ ][ ][ ][ ][ ][ ][ ][ and [ hopscotch hashing appeared in [ extendible hashing appears in [ ]with analysis in [ and [ exercise ( -dis from [ part (eis from [ ]and part (fis from [ the fnv- hash function described in exercise is due to fowlernolland vo arbitmanm naorand segev"de-amortized cuckoo hashingprovable worst-case performance and experimental results,proceedings of the th international colloquium on automatalanguages and programming ( ) - azara brodera karlinand upfal"balanced allocations,siam journal of computing ( ) - boyer and moore" fast string searching algorithm,communications of the acm ( ) - broder and mitzenmacher"using multiple hash functions to improve ip lookups,proceedings of the twentieth ieee infocom ( ) - carter and wegman"universal classes of hash functions,journal of computer and system sciences ( ) - cohen and kane"bounds on the independence required for cuckoo hashing,preprint devroye and morin"cuckoo hashingfurther analysis,information processing letters ( ) -