is at most /mand when adding into table with itemsthe probability of collision at the initial point is at most /mor the load factor the use of universal hash function for separate chaining or hopscotch hashing would be sufficient to meet the assumptions used in the analysis of those data structures howeverit is not sufficient for cuckoo hashingwhich requires stronger notion of independence in cuckoo hashingwe first see if there is vacant locationif there is notand we do an evictiona different item is now involved in looking for vacant location this repeats until we find the vacant locationor decide to rehash [generally within (log nstepsin order for the analysis to workeach step must have collision probability of / independentlywith different item being subject to the hash function we can formalize this independence requirement in the following definition definition family of hash functions is -universalif for any   xk yk the number of hash functions in for which ( ( ) ( ( )and (xk (yk is at most | |/mk with this definitionwe see that the analysis of cuckoo hashing requires an (log )universal hash function (after that many evictionswe give up and rehashin this section we look only at universal hash functions to design simple universal hash functionwe will assume first that we are mapping very large integers into smaller integers ranging from to let be prime larger than the largest input key our universal family will consist of the following set of functionswhere and are chosen randomlyh {ha, ( ((ax bmod pmod mwhere < < < < for examplein this familythree of the possible random choices of (abyield three different hash functionsh , ( (( mod pmod , ( (( mod pmod , ( (( xmod pmod observe that there are ( possible hash functions that can be chosen theorem the hash family {ha, ( ((ax bmod pmod mwhere < < < < is universal proof let and be distinct valueswith ysuch that ha, (xha, (yclearly if (ax bmod is equal to (ay bmod pthen we will have collision howeverthis cannot happensubtracting equations yields ( (mod )which would mean that divides or divides ysince is prime but neither can happensince both and are between and so let (ax bmod and let (ay bmod pand by the above argumentr  thus there are possible values for rand for each rthere are possible