hash tables dewitt white bercerra chong appleby decosta milano freeman keys hash to array indices block lang milano danzig full figure block chong leblanc empty smith full external hashing all records with keys that hash to the same value are located in the same block to find record with particular keythe search algorithm hashes the keyuses the hash value as an index to the hash tablegets the block number at that indexand reads the block this process is efficient because only one block access is necessary to locate given item the downside is that considerable disk space is wasted because the blocks areby designnot full to implement this schemewe must choose the hash function and the size of the hash table with some care so that limited number of keys hash to the same value in our examplewe want only eight records per keyon the average full blocks even with good hash functiona block will occasionally become full this situation can be handled using variations of the collision-resolution schemes discussed for internal hash tablesopen addressing and separate chaining