hashing in we discussed the search tree adtwhich allowed various operations on set of elements in this we discuss the hash table adtwhich supports only subset of the operations allowed by binary search trees the implementation of hash tables is frequently called hashing hashing is technique used for performing insertionsdeletionsand finds in constant average time tree operations that require any ordering information among the elements are not supported efficiently thusoperations such as findminfindmaxand the printing of the entire table in sorted order in linear time are not supported the central data structure in this is the hash table we will see several methods of implementing the hash table compare these methods analytically show numerous applications of hashing compare hash tables with binary search trees general idea the ideal hash table data structure is merely an array of some fixed size containing the items as discussed in generally search is performed on some part (that isdata memberof the item this is called the key for instancean item could consist of string (that serves as the keyand additional data members (for instancea name that is part of large employee structurewe will refer to the table size as tablesizewith the understanding that this is part of hash data structure and not merely some variable floating around globally the common convention is to have the table run from to tablesize we will see why shortly each key is mapped into some number in the range to tablesize and placed in the appropriate cell the mapping is called hash functionwhich ideally should be simple to compute and should ensure that any two distinct keys get different cells since there are finite number of cells and virtually inexhaustible supply of keysthis is clearly impossibleand thus we seek hash function that distributes the keys evenly among the cells figure is typical of perfect situation in this examplejohn hashes to phil hashes to dave hashes to and mary hashes to