HashMap- Universe of keys small

  • #1
1
0

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.
 

Answers and Replies

  • #2
12,482
6,264
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.
 

Related Threads on HashMap- Universe of keys small

Replies
2
Views
818
Replies
2
Views
12K
  • Last Post
Replies
0
Views
12K
  • Last Post
Replies
22
Views
1K
Replies
2
Views
1K
  • Last Post
Replies
0
Views
4K
Replies
4
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
3
Views
2K
Replies
4
Views
7K
Top