I have just begun looking at ADT's and was wondering if there are any

advantages or disadvantages of using Hash Tables over using Binary Search

Trees?

Quote:

>From the documentation to libavl at <URL:http://www.msu.edu/~pfaffben/avl>:

Consider some techniques that can be used to find a particular item

in an ordered data set. Typical methods include sequential

searching, binary searching, digital searches, and hash

tables. Sequential searching is simple, but slow (O(n)). Digital

searching requires that the entire data set be known in advance,

and memory efficient implementations are also slow.

Hash tables are fast (O(1)) for static data sets, but they require

expensive table enlargements if table size can't be predicted in

advance, and they can be wasteful of memory. In addition, it can be

difficult and time-consuming to choose an effective hash

function. Some hash tables variants also make deletion an expensive

operation.

Binary search techniques work almost as quickly (O(log(n)) on an

ordered table, or on a binary tree. Plus, binary trees are

efficient for insertion, deletion, and searching, if data are

inserted in random. But if data are inserted in order then ordinary

binary searching can degenerate to a sequential search.

One further advantage of binary trees is that they allow easy

iteration over the data in the tree in sorted order. With hash

tables it is necessary to sort the data before iterating, and after

sorting the data is no longer in hash form.

By the way, comp.programming is probably a better place to ask this

question.

--