Searching and Hashing

It is important to understand what search is and when it is appropriate. This page explains sequential and binary search, and their implementation. There is also the matter of hashing as a storage and search technique. In so doing, we introduce the unordered map and how to implement a map abstract data type using hashing. Read Sections 6.1-6.5. You may also find Sections 6.6-6.11 useful for practice.

5. Hashing

5.4. Analysis of Hashing

We stated earlier that in the best case hashing would provide a $O (1)$ , constant time search technique. However, due to collisions, the number of comparisons is typically not so simple. Even though a complete analysis of hashing is beyond the scope of this text, we can state some well-known results that approximate the number of comparisons necessary to search for an item.

The most important piece of information we need to analyze the use of a hash table is the load factor, $λ$ . Conceptually, if $λ$ is small, then there is a lower chance of collisions, meaning that items are more likely to be in the slots where they belong. If $λ$

is large, meaning that the table is filling up, then there are more and more collisions. This means that collision resolution is more difficult, requiring more comparisons to find an empty slot. With chaining, increased collisions means an increased number of items on each chain.

As before, we will have a result for both a successful and an unsuccessful search. For a successful search using open addressing with linear probing, the average number of comparisons is approximately $\frac{1}{2} (1 + \frac{1}{1 - λ})$ and an unsuccessful search gives $\frac{1}{2} (1 + {(\frac{1}{1 - λ})}^{2})$ If we are using chaining, the average number of comparisons is $1 + \frac{λ}{2}$ for the successful case, and simply $λ$ comparisons if the search is unsuccessful.