When is a hash table better to use than a search tree?

Question

When is a hash table better to use than a search tree?

Answer 1

Depends on what you want to do with the data structure.

Operation         Hash table  Search Tree
Search            O(1)        O(log(N))
Insert            O(1)        O(log(N))
Delete            O(1)        O(log(N))
Traversal         O(N)        O(N)
Min/Max-Key       -hard-      O(log(N))
Find-Next-Key     -hard-      O(1)

• Insert, search on a Hashtable depends on the load factor of the hash of the table and its design. Poorly designed hastables can have O (N) lookup and insertion. The same is true for your search tree.

• Deleting in a hash table can be cumbersome depending on your collision.

• Moving a container, searching for Min / Max, searching for the next / previous type of operation is better in the search tree because of its ordering.

• All search tree ratings are higher for "balanced" search trees.

Answer 2

, . , -, , , log n, log n , n, . , . , , , , , -.

, , , , , , n , . n - , log n 40, 40 . n, 50, .

++, , - , , , .

Answer 3

:

Operation                  Hash table(1)  SBB Search Tree(2)
.find(obj) -> obj          O(1)           O(1)*

.insert(obj)               O(1)           O(log(N))

.delete(obj)               O(1)           O(log(N))

.traverse / for x in...    O(N)           O(N)

.largerThan(obj) -> {objs} unsupported    O(log(N))
                                           \
                                            union right O(1) + parent O(1)

.sorted() -> [obj]         unsupported    no need
                                           \
                                            already sorted so no need
                                            to print out, .traverse() is O(N)

.findMin() -> obj          unsupported**  O(log(N)), maybe O(1)
                                           \
                                            descend from root, e.g.:
                                            root.left.left.left...left -> O(log(N))
                                            might be able to cache for O(1)

.findNext(obj) -> obj      unsupported    O(log(N))
                                           \
                                            first perform x=.find(obj) which is O(1)
                                            then descend from that node, e.g.:
                                            x.right.left.left...right -> O(log(N))

(1) http://en.wikipedia.org/wiki/Hash_table

(2) http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree, . http://en.wikipedia.org/wiki/Tango_tree http://en.wikipedia.org/wiki/Splay_tree

(*) - , . . O(log(N)).

(**) , , O(1).

.

:

, .

Answer 4

, -. , , , , -, , , , .