Solved

Getting a random element from a hashtable

Posted on 2003-11-05
23
1,284 Views
Last Modified: 2008-02-26
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
Comment
Question by:zacbell
  • 7
  • 7
  • 3
  • +2
23 Comments
 
LVL 92

Assisted Solution

by:objects
objects earned 50 total points
ID: 9692370
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
 
LVL 15

Expert Comment

by:jimmack
ID: 9692718
Collection c = theHashtable.values();
Object[] contents = c.toArray();

Then you can access random elements in the contents array.
0
 
LVL 92

Expert Comment

by:objects
ID: 9692760
Isn't that what I just said (array=indexed collection) :)
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 86

Accepted Solution

by:
CEHJ earned 50 total points
ID: 9693612
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
 
LVL 9

Expert Comment

by:Ovi
ID: 9693730
Going with CEHJ
0
 
LVL 15

Expert Comment

by:jimmack
ID: 9694007
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 9694050
>>but the questioner asks for something with constant time for access.

Don't see how that could be possible irrespective of capacity
0
 
LVL 15

Expert Comment

by:jimmack
ID: 9694101
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
 

Author Comment

by:zacbell
ID: 9695395
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 9695476
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
 
LVL 9

Expert Comment

by:Ovi
ID: 9695587
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
 

Author Comment

by:zacbell
ID: 9695632
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
 
LVL 92

Expert Comment

by:objects
ID: 9697169
> 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
 
LVL 86

Expert Comment

by:CEHJ
ID: 9697385
>>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
 
LVL 92

Expert Comment

by:objects
ID: 9697409
> 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
 
LVL 86

Expert Comment

by:CEHJ
ID: 11435340
I don't think zacbell need have any reservations about my code that he's currently using
0
 
LVL 92

Expert Comment

by:objects
ID: 11441479
Except that it does not meet the specs :)
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 11441511
>>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
 
LVL 92

Expert Comment

by:objects
ID: 11441548
Not at all, it just involves a tradeoff.
0
 

Author Comment

by:zacbell
ID: 11442562
Thanks for the help. Objects and CEHJ were both helpful, so I awarded each the original point value.
0
 
LVL 92

Expert Comment

by:objects
ID: 11442664
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 11444229
:-)
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question