If the keys are not unique, then we can simply construct a set of mO(1). However, if each element of the collection has some other distinguishing feature (other than its key), and if the maximum number of duplicates is n, then searching for a specific element is _{dup}^{max}O(n. If duplicates are the exception rather than the rule, then _{dup}^{max})n is much smaller than _{dup}^{max}n and a direct address table will provide good performance. But if n approaches _{dup}^{max}n, then the time to find a specific element is O(n) and a tree structure will be more efficient. lists and store the heads of these lists in the direct address table. The time to find an element matching an input key will still be |

The range of the key determines the size of the direct address table and may be too large to be practical. For instance it's not likely that you'll be able to use a direct address table to store elements which have arbitrary 32-bit integers as their keys for a few years yet!

Direct addressing is easily generalised to the case where there is a function,

**h(k)**=> (1,

**m**)

**k**, to the range (1,

**m**). In this case, we place the element in

**T[h(k)]**rather than

**T[k]**and we can search in

**O(1)**time as before.