are many approaches to hashing and it is easy to devise an inefficient implementation hashing is suitable for both in-memory and disk-based searching and is one of the two most widely used methods for organizing large databases stored on disk (the other is the -treewhich is covered in as simple (though unrealisticexample of hashingconsider storing recordseach with unique key value in the range to in this simple casea record with key can be stored in ht[ ]and the hash function is simply (kk to find the record with key value ksimply look in ht[ktypicallythere are many more values in the key range than there are slots in the hash table for more realistic examplesuppose that the key can take any value in the range to , ( the key is two-byte unsigned integer)and that we expect to store approximately records at any given time it is impractical in this situation to use hash table with , slotsbecause most of the slots will be left empty insteadwe must devise hash function that allows us to store the records in much smaller table because the possible key range is larger than the size of the tableat least some of the slots must be mapped to from multiple key values given hash function and two keys and if ( ( where is slot in the tablethen we say that and have collision at slot under hash function finding record with key value in database organized by hashing follows two-step procedure compute the table location ( starting with slot ( )locate the record containing key using (if necessarya collision resolution policy hash functions hashing generally takes records whose key values come from large range and stores those records in table with relatively small number of slots collisions occur when two records hash to the same slot in the table if we are careful--or lucky--when selecting hash functionthen the actual number of collisions will be few unfortunatelyeven under the best of circumstancescollisions are nearly unavoidable for exampleconsider classroom full of students what is the the exception to this is perfect hashing perfect hashing is system in which records are hashed such that there are no collisions hash function is selected for the specific set of records being hashedwhich requires that the entire collection of records be available before selecting the hash function perfect hashing is efficient because it always finds the record that we are looking for exactly where the hash function computes it to beso only one access is required selecting perfect hash function can be expensive but might be worthwhile when extremely efficient search