hashing empty table after after after after after figure hash table with double hashingafter each insertion as hash (xr ( mod )with prime smaller than tablesizewill work well if we choose then figure shows the results of inserting the same keys as before the first collision occurs when is inserted hash ( so is inserted in position hash ( so is inserted at location finally collides and is inserted at distance hash ( - away if we tried to insert in position we would have collision since hash ( we would then try positions and then until an empty spot is found it is generally possible to find some bad casebut there are not too many here as we have said beforethe size of our sample hash table is not prime we have done this for convenience in computing the hash functionbut it is worth seeing why it is important to make sure the table size is prime when double hashing is used if we attempt to insert into the tableit would collide with since hash ( and the table size is we essentially have only one alternative locationand it is already taken thusif the table size is not primeit is possible to run out of alternative locations prematurely howeverif double hashing is correctly implementedsimulations imply that the expected number of probes is almost the same as for random collision resolution strategy this makes double hashing theoretically interesting quadratic probinghoweverdoes not require the use of second hash function and is thus likely to be simpler and faster in practiceespecially for keys like strings whose hash functions are expensive to compute rehashing if the table gets too fullthe running time for the operations will start taking too longand insertions might fail for open addressing hashing with quadratic resolution this can happen if there are too many removals intermixed with insertions solutionthenis to build another table that is about twice as big (with an associated new hash functionand scan down the entire original hash tablecomputing the new hash value for each (nondeletedelement and inserting it in the new table