hash tables folding another reasonable hash function involves breaking the key into groups of digits and adding the groups this ensures that all the digits influence the hash value the number of digits in group should correspond to the size of the array that isfor an array of , itemsuse groups of three digits each for examplesuppose you want to hash nine-digit social security numbers for linear probing if the array size is , you would divide the nine-digit number into three groups of three digits if particular ssn was you would calculate key value of + + you can use the operator to trim such sums so the highest index is in this case % if the array size is you would need to break the nine-digit key into four two-digit numbers and one onedigit number + + + + and % it' easier to imagine how this works when the array size is multiple of howeverfor best results it should be prime numberas we've seen for other hash functions we'll leave an implementation of this scheme as an exercise hashing efficiency we've noted that insertion and searching in hash tables can approach ( time if no collision occursonly call to the hash function and single array reference are necessary to insert new item or find an existing item this is the minimum access time if collisions occuraccess times become dependent on the resulting probe lengths each cell accessed during probe adds another time increment to the search for vacant cell (for insertionor for an existing cell during an accessa cell must be checked to see whether it' emptyand--in the case of searching or deletion-whether it contains the desired item thusan individual search or insertion time is proportional to the length of the probe this is in addition to constant time for the hash function the average probe length (and therefore the average access timeis dependent on the load factor (the ratio of items in the table to the size of the tableas the load factor increasesprobe lengths grow longer we'll look at the relationship between probe lengths and load factors for the various kinds of hash tables we've studied open addressing the loss of efficiency with high load factors is more serious for the various open addressing schemes than for separate chaining