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?
zacbellAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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
Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.