in open addressingifduring insertionone block is found to be fullthe algorithm inserts the new record in neighboring block in linear probing this is the next blockbut it could also be selected using quadratic probe or double hashing in separate chainingspecial overflow blocks are made availablewhen primary block is found to be fullthe new record is inserted in the overflow block full blocks are undesirable because an additional disk access is necessary for the second blockthis doubles the access time howeverthis is acceptable if it happens rarely we've discussed only the simplest hash table implementation for external storage there are many more complex approaches that are beyond the scope of this book summary hash table is based on an array the range of key values is usually greater than the size of the array key value is hashed to an array index by hash function an english-language dictionary is typical example of database that can be efficiently handled with hash table the hashing of key to an already-filled array cell is called collision collisions can be handled in two major waysopen addressing and separate chaining in open addressingdata items that hash to full array cell are placed in another cell in the array in separate chainingeach array element consists of linked list all data items hashing to given array index are inserted in that list we discussed three kinds of open addressinglinear probingquadratic probingand double hashing in linear probing the step size is always so if is the array index calculated by the hash functionthe probe goes to xx+ + + and so on the number of such steps required to find specified item is called the probe length in linear probingcontiguous sequences of filled cells appear they are called primary clustersand they reduce performance in quadratic probing the offset from is the square of the step numberso the probe goes to xx+ + + + and so on