HashMap- Universe of keys small

[TobiasF]

Homework Statement

[/B]
"Direct addressing is a simple technique that works well when the universe U of
keys is reasonably small. Suppose that an application needs a dynamic set in which
each element has a key drawn from a not too large universe U. We shall assume that no two elements have the same key.
To represent the dynamic set, we use an array, or direct-address table, denoted
by T =[0, ...m-1]. Why can't the size of the universe be very large?"

Homework Equations

The Attempt at a Solution

I am entertaining the possibility that storing a large set of keys might be heavy on memory. However, I am not quite convinced: If we know that we are going to need a lot of keys for an application, then storing a large array is going to be resource-draining anyway.

 

[jedishrfu]

What is large? are you storing 10, 100, 1000 or 10,000 keys in memory? how big is each key?

There are many database engines that store whole tables in memory for faster access and they are on the order of 10,000 rows or more limited only by available memory.

In general, I use the 10,000 value as a tipping point between in-memory and disk based storage or between using a simple structure like a hash table (or properties object in Java) and switching to a database strategy.

With respect to your key universe not being large, it may have something to do with hash collisions where two elements have the same hash key and so now you have to add additional logic to handle the collision ie use a list object to hold both elements.