goes to xx+ + + + and so on quadratic probing eliminates primary clusteringbut suffers from the less severe secondary clustering secondary clustering occurs because all the keys that hash to the same value follow the same sequence of steps during probe all keys that hash to the same value follow the same probe sequence because the step size does not depend on the keybut only on the hash value in double hashing the step size depends on the keyand is obtained from secondary hash function if the secondary hash function returns value in double hashingthe probe goes to xx+sx+ sx+ sx+ sand so onwhere depends on the keybut remains constant during the probe the load factor is the ratio of data items in hash table to the array size the maximum load factor in open addressing should be around for double hashing at this load factorsearches will have an average probe length of search times go to infinity as load factors approach in open addressing it' crucial that an open-addressing hash table does not become too full load factor of is appropriate for separate chaining at this load factor successful search has an average probe length of and an unsuccessful search probe lengths in separate chaining increase linearly with load factor string can be hashed by multiplying each character by different power of constantadding the productsand using the modulo (%operator to reduce the result to the size of the hash table to avoid overflowthe modulo operator can be applied at each step in the processif the polynomial is expressed using horner' method hash table sizes should generally be prime numbers this is especially important in quadratic probing and separate chaining hash tables can be used for external storage one way to do this is to have the elements in the hash table contain disk-file block numbers heaps overview we saw in "stacks and queues,that priority queue is data structure that offers convenient access to the data item with the smallest (or largestkey this is useful when key values indicate the order in which items should be accessed