1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: HashMap- Universe of keys small

  1. Jun 16, 2016 #1
    1. The problem statement, all variables and given/known data
    "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?"

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Jun 21, 2016 #2


    Staff: Mentor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted