Hash Tables vs. Binary Search vs. Search Trees

Hash Tables:  in regular use, the fastest BY FAR.

Binary Search and balanced search trees are O(lg n) time and they never screw up.

Hash tables are O(1) time under normal circumstances...but if the unforeseen happens, they could run in O(n) time.

Binary Search is read only.  You would only use these if you know that you aren't going to be adding or deleting records.  Under this restriction, binary search (of a sorted array) is guaranteed fast.

Balanced Search Trees allow for adding and deleting and searching in O(lg n) time.  Not as strictly fast as binary search.

Max # of lookups in binary search is:  ceil (lg(n+1))

For an AVL tree, the max number of lookups is about 1.6 * # of binary search lookups.

For a red-black tree, the max number of lookups is about 2 * # of binary search lookups.

For hash table, "usually" the number of lookups is about 1 or 2, even for large data sets.

The big downside of hash tables is that they are not remotely sorted.  So, in a sorted array or a search tree, you can easily say what records come before and after a searched record.

E.G.  "DOG" is not in the file, but it would come between "CAT" and "ELEPHANT."

Hash tables can tell you whether something is there,  yes or no, but it is not easy to tell what a desired record would come between alphabetically because the Hash Table uses nothing even remotely close to alphabetical order.