hash tables in this introduction to hashing open addressing separate chaining hash table is data structure that offers very fast insertion and searching when you first hear about themhash tables sound almost too good to be true no matter how many data items there areinsertion and searching (and sometimes deletioncan take close to constant timeo( in big notation in practice this is just few machine instructions for human user of hash tablethis is essentially instantaneous it' so fast that computer programs typically use hash tables when they need to look up tens of thousands of items in less than second (as in spelling checkershash tables are significantly faster than treeswhichas we learned in the preceding operate in relatively fast (logntime not only are they fasthash tables are relatively easy to program hash tables do have several disadvantages they're based on arraysand arrays are difficult to expand after they've been created for some kinds of hash tablesperformance may degrade catastrophically when table becomes too fullso the programmer needs to have fairly accurate idea of how many data items will need to be stored (or be prepared to periodically transfer data to larger hash tablea time-consuming processalsothere' no convenient way to visit the items in hash table in any kind of order (such as from smallest to largestif you need this capabilityyou'll need to look elsewhere howeverif you don' need to visit items in orderand you can predict in advance the size of your databasehash tables are unparalleled in speed and convenience hash functions hashing efficiency hashing and external storage