Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Avoiding Collisions

Ideally, given a set of tex2html_wrap_inline62202 distinct keys, tex2html_wrap_inline62204, the set of hash values tex2html_wrap_inline62206 contains no duplicates. In practice, unless we know something about the keys chosen, we cannot guarantee that there will not be collisions. However, in certain applications we have some specific knowledge about the keys that we can exploit to reduce the likelihood of a collision. For example, if the keys in our application are telephone numbers, and we know that the telephone numbers are all likely to be from the same geographic area, then it makes little sense to consider the area codes in the hash function, the area codes are all likely to be the same.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.