Summary: Hash Tables Page 1
· All elements have a unique key.
o Insert element with a specified key.
o Search for element by key.
o Delete element by key.
· Random vs. sequential access.
· If we have duplicate keys, need rule to resolve ambiguity.
· What ways could you use to implement a dictionary? (Name in class)
o Ordered array
o Unordered array
o Ordered linked list
o Binary search tree
· Let's use our newly acquired analysis skills to determine which of the following is better.
Let's analyze them for two operations insert and search. This is shown in Table 1.
Method Insert time Search Time
Ordered array 2/n nlog