hashing theorem if quadratic probing is usedand the table size is primethen new element can always be inserted if the table is at least half empty proof let the table sizetablesizebe an (oddprime greater than we show that the first tablesize/ alternative locations (including the initial location ( )are all distinct two of these locations are (xi (mod tablesizeand (xj (mod tablesize)where <ij <tablesize/ supposefor the sake of contradictionthat these locations are the samebut  then (xi (xj (mod tablesizei = (mod tablesizei - = (mod tablesize( )( (mod tablesize since tablesize is primeit follows that either ( jor ( jis equal to (mod tablesizesince and are distinctthe first option is not possible since <ij <tablesize/ the second option is also impossible thusthe first tablesize/ alternative locations are distinct if at most tablesize/ positions are takenthen an empty spot can always be found if the table is even one more than half fullthe insertion could fail (although this is extremely unlikelythereforeit is important to keep this in mind it is also crucial that the table size be prime if the table size is not primethe number of alternative locations can be severely reduced as an exampleif the table size were then the only alternative locations would be at distances or away standard deletion cannot be performed in probing hash tablebecause the cell might have caused collision to go past it for instanceif we remove then virtually all the remaining find operations will fail thusprobing hash tables require lazy deletionalthough in this case there really is no laziness implied the class interface required to implement probing hash tables is shown in figure instead of an array of listswe have an array of hash table entry cells the nested class hashentry stores the state of an entry in the info memberthis state is either activeemptyor deleted we use standard enumerated type enum entrytype activeemptydeleted }constructing the table (fig consists of setting the info member to empty for each cell contains( )shown in figure invokes private member functions isactive and findpos the private member function findpos performs the collision resolution we ensure in the insert routine that the hash table is at least twice as large as the number of elements in the tableso quadratic resolution will always work in the implementation if the table size is prime of the form and the quadratic collision resolution strategy ( +- is usedthen the entire table can be probed the cost is slightly more complicated routine