• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1313
  • Last Modified:

Getting a random element from a hashtable

What's the most efficient way to retrieve a random element from a hashtable? Ideally, I'd like a method which operates in constant time (does not scale with the capacity of the hashtable). Any ideas?
0
zacbell
Asked:
zacbell
  • 7
  • 7
  • 3
  • +2
2 Solutions
 
objectsCommented:
Don't think there is an efficient way to grab a random entry from a Hashtable.
Think your best bet would be to also maintain your elements in a Vector (or some other indexed collection) and use that for grabbing random elements.
0
 
jimmackCommented:
Collection c = theHashtable.values();
Object[] contents = c.toArray();

Then you can access random elements in the contents array.
0
 
objectsCommented:
Isn't that what I just said (array=indexed collection) :)
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
CEHJCommented:
This should theoretically be more efficient, as creating an array should be a functional superset of iterating the collection:


      public static Object randomValue(Hashtable table) {
            Object value = null;
            Collection values = table.values();
            int numElements = values.size();
            int randomIndex = (int)(Math.random() * numElements);
            Iterator iter = values.iterator();
            int index = 0;
            while (iter.hasNext()) {
                  value = iter.next();
                  if (index == randomIndex) {
                        return value;
                  }
                  index++;
            }
            return null;
      }
0
 
OviCommented:
Going with CEHJ
0
 
jimmackCommented:
I agree with the efficiency argument, but the questioner asks for something with constant time for access.

I got the impression from the question that this was more important ;-)
0
 
CEHJCommented:
>>but the questioner asks for something with constant time for access.

Don't see how that could be possible irrespective of capacity
0
 
jimmackCommented:
If zacbel have something along the following lines:

// 1) Fill in Hashtable (10000 elements)

// 2) Do other things

// 3) Display 20 random elements from the Hashtable

Creating the Object array prior to step 3 would allow any of the elements to be retrieved in constant time.

I agree that if he is modifying the Hashtable between "random" accesses, then retrieving the object array before each access is grossly inefficient.

Since the requirement has not been specified in this way, it is impossible to determine at this stage which solution would be more appropriate.
0
 
zacbellAuthor Commented:
I currently use CEHJ's method for retrieving a random element (i.e. iterating for a random number of steps), but I am looking for something faster. Creating a Vector while setting up the hashtable sounds like the most promising approach since I will be drawing multiple random elements over the life of the hashtable. But I was hoping for something faster without that additional overhead (the hashtable holds around 500,000 objects).

Thanks for all suggestions so far.
0
 
CEHJCommented:
Maybe something like this then?

class RandomSelectableHashtable extends Hashtable {
      
      ArrayList selectableValues = new ArrayList();
      
      
      .....
      
      public  Object put(Object key, Object value) {
            super.put(key, value);
            selectableValues.add(value);
      }
      
      public  Object selectRandomValue() {
            return selectableValues((int)(selectableValues.size() * Math.random()));
      }
}      
      
      
            

0
 
OviCommented:
I'm asking myself what's the point of using a hastable if you preffer the list (Vector) soluton? This will bring alot of  content synchronization problems. I suggest you to use the first option offered by CEHJ.
0
 
zacbellAuthor Commented:
I absolutely need constant access by key, and also need efficient random access. The hashtable provides the first requirement, and (so far) the Vector provides the best avenue for the second element. Now it becomes a question of tradeoffs. Do I incur the overhead of setting up the vector while setting up the hashtable to improve the speed of random access, or do I incur the cost of random iteration and avoid overhead if the number of random accesses is small? I can manage this tradeoff. But I was hoping, deep down, that it would be possible to get random access without the treadeoff.
0
 
objectsCommented:
> Maybe something like this then?
> class RandomSelectableHashtable extends Hashtable {

Exactly what I first suggested :)

> Do I incur the overhead of setting up the vector while setting up the
> hashtable to improve the speed of random access

That overhead would be small.

> that it would be possible to get random access without the treadeoff.

Not without writing your own specialised collection class.
0
 
CEHJCommented:
>>Do I incur the overhead of setting up the vector

A Vector would of course have the overhead of synchronization, so you'd be probably better with an ArrayList.
0
 
objectsCommented:
> A Vector would of course have the overhead of synchronization,
> so you'd be probably better with an ArrayList.

Assuming of course that your code is thread safe.

If hashatble is loaded initially and remains static then you'd just need to create an array once it was loaded using jimmack's suggestion.

0
 
CEHJCommented:
I don't think zacbell need have any reservations about my code that he's currently using
0
 
objectsCommented:
Except that it does not meet the specs :)
0
 
CEHJCommented:
>>Except that it does not meet the specs :)

If it doesn't meet the specs then your first (general) comment is wrong is it not?
0
 
objectsCommented:
Not at all, it just involves a tradeoff.
0
 
zacbellAuthor Commented:
Thanks for the help. Objects and CEHJ were both helpful, so I awarded each the original point value.
0
 
objectsCommented:
0
 
CEHJCommented:
:-)
0

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

  • 7
  • 7
  • 3
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now