Comparison

We have seen several ways to construct dictionaries: hash tables, unbalanced binary search trees, red-black trees, and skip lists. There are several factors that influence the choice of an algorithm:

Table 3-2: Comparison of Dictionaries
method statements average time worst-case time
hash table 26 O(1) O(n)
unbalanced tree 41 O(lgn) O(n)
red-black tree 120 O(lgn) O(lgn)
skip list 55 O(lgn) O(n)

Average time for insert, search, and delete operations on a database of 65,536 (216) randomly input items may be found in Table 3-3. For this test the hash table size was 10,009 and 16 index levels were allowed for the skip list. Although there is some variation in the timings for the four methods, they are close enough so that other considerations should come into play when selecting an algorithm.

Table 3-3: Average Time (µs), 65536 Items, Random Input
method insert search delete
hash table 18 8 10
unbalanced tree 37 17 26
red-black tree 40 16 37
skip list 48 31 35

Table 3-4 shows the average search time for two sets of data: a random set, where all values are unique, and an ordered set, where values are in ascending order. Ordered input creates a worst-case scenario for unbalanced tree algorithms, as the tree ends up being a simple linked list. The times shown are for a single search operation. If we were to search for all items in a database of 65,536 values, a red-black tree algorithm would take .6 seconds, while an unbalanced tree algorithm would take 1 hour.

Table 3-4: Average Search Time (µs)
random
input
count hash table unbalanced tree red-black tree skip list
16 4 3 2 5
256 3 4 4 9
4,096 3 7 6 12
65,536 8 17 16 31
ordered
input
16 3 4 2 4
256 3 47 4 7
4,096 3 1,033 6 11
65,536 7 55,019 9 15