Get A random keyValue from Hashtable

Question

I Have a Hashtable that I dont know What is the content of .

now I want to get one Key and value from it;

I use hashtable because of its speed because content of hashtable is over 4,500,000 KeyValuePair so I cant use GetEnumerator its reduce program speed

Answer 1

You use a List<TKey>:

Dictionary<string, string> dict = ... your hashtable which could be huge

List<string> keys = new List<string>(dict.Keys);
int size = dict.Count;
Random rand = new Random();
string randomKey = keys[rand.Next(size)];

We are just creating a List<TKey> whose elements are pointing to the same location in memory as the keys of your hashtable and then we pick a random element from this list.

And if you want to get a random element value from the hashtable, this should be pretty straightforward given a random key.

string randomeElement = dict[randomKey];

Answer 2

I cant use GetEnumerator its reduce program speed"

Well that's a problem. You've accepted an answer which does iterate over all the entries, and also copies the keys into a new list, so it's not clear whether you've abandoned that requirement.

An approach which will certainly be more efficient in memory and potentially in speed as well is to iterate over the whole dictionary, but retaining a random element at any one time, with an optimization for collections where we can obtain the count cheaply. Here's an extension method which will do that for any generic sequence in .NET:

public static T RandomElement<T>(this IEnumerable<T> source,
                                 Random rng)
{
    // Optimize for the "known count" case.
    ICollection<T> collection = source as ICollection<T>;
    if (collection != null)
    {
        // ElementAt will optimize further for the IList<T> case
        return source.ElementAt(rng.Next(collection.Count));
    }

    T current = default(T);
    int count = 0;
    foreach (T element in source)
    {
        count++;
        if (rng.Next(count) == 0)
        {
            current = element;
        }            
    }
    if (count == 0)
    {
        throw new InvalidOperationException("Sequence was empty");
    }
    return current;
}

So for a Dictionary<TKey, TValue> you'd end up with a KeyValuePair<TKey, TValue> that way - or you could project to Keys first:

var key = dictionary.Keys.RandomElement(rng);

(See my article on Random for gotchas around that side of things.)

I don't believe you'll be able to do any better than O(n) if you want a genuinely pseudo-random key, rather than just an arbitrary key (which you could get by taking the first one in the sequence, as stated elsewhere).

Note that copying the keys to a list as in Darin's answer allows you to get multiple random elements more efficiently, of course. It all depends on your requirements.

Answer 3

Hashtable.Keys will give you a pointer to the internal list of keys. That is speedy. Also removing an item from a Hashtable is an O(1) operation, so this will also be speedy, even with large amounts of items.

You could do a loop like this (I see no reason to use random in your question);

var k = Hashtable.Keys(); // Will reflect actual contents, even if changes occur

while (k.Count > 0 )
{
 var i = Keys.First();
 {
       Process(i);
       Hashtable.Remove(i)  
 }
}

Answer 4

with Linq you can do:

Dictionary<string, string> dicto = new Dictionary<string, string>();

Random rand = new Random();

int size = dicto.Count;

int randNum = rand.Next(0, size);

KeyValuePair<string, string> randomPair = dicto.ElementAt( randNum );

string randomVal = randomPair.Value;

For instance,

string tmp = dicto.ElementAt( 30 ).Value;

Would copy the value of the thirtieth item in the Dicto to the string tmp.

Internally, I think it walks through the keypairs one at a time, till it gets to the thirtieth, instead of copying them all, so you don't need to load all the elements into memory.

I'm not sure what you meant by not knowing what the content is.

You don't know the types in the KeyValuePair of the dicto? Or just don't know what values will be in the dicto?

Answer 5

Well, if you know which version of the .NET BCL you'll be targeting (i.e., if it's fixed), you could always plumb the internals of Dictionary<TKey, TValue> to figure out how it stores its keys privately and use that to pluck a random one.

For example, using the version of Mono I currently have installed on my work laptop, I see that the Dictionary<TKey, TValue> type has a private field called keySlots (I assume this will be different for you if you're on Windows). Using this knowledge you could implement a function looking something like this:

static readonly Dictionary<Type, FieldInfo> KeySlotsFields = new Dictionary<Type, FieldInfo>();

public static KeyValuePair<TKey, TValue> GetRandomKeyValuePair<TKey, TValue>(this Random random, Dictionary<TKey, TValue> dictionary, Random random = null)
{
    // Here's where you'd get the FieldInfo that you've identified
    // for your target version of the BCL.
    FieldInfo keySlotsField = GetKeySlotsField<TKey, TValue>();

    var keySlots = (TKey[])keySlotsField.GetValue(dictionary);

    var key = (TKey)keySlots[random.Next(keySlots.Length)];

    // The keySlots field references an array with some empty slots,
    // so we need to loop until we come across an existing key.
    while (key == null)
    {
        key = (TKey)keySlots[random.Next(keySlots.Length)];
    }

    return new KeyValuePair<TKey, TValue>(key, dictionary[key]);
}

// This happens to work for me on Mono; you'd almost certainly need to
// rewrite it for different platforms.
public FieldInfo GetKeySlotsField<TKey, TValue>()
{
    Type keyType = typeof(TKey);

    FieldInfo keySlotsField;
    if (!KeySlotsFields.TryGetValue(keyType, out keySlotsField))
    {
        KeySlotsFields[keyType] = keySlotsField = typeof(Dictionary<TKey, TValue>).GetField("keySlots", BindingFlags.Instance | BindingFlags.NonPublic);
    }

    return keySlotsField;
}

This could be an appropriate solution in your case, or it could be a horrible idea. Only you have enough context to make that call.

As for the example method above: I personally like adding extension methods to the Random class for any functionality involving randomness. That's just my choice; obviously you could go a different route.

Answer 6

How random does the random key have to be?

Hash tables don't define an order for their items to be stored in, so you could just grab the first item. It's not really random, but it's not insertion order or sorted order either. Would that be random enough?

Dictionary<string, string> dict = GetYourHugeHashTable();

KeyValuePair<string, string> randomItem = dict.First();
DoAComputation(randomItem.Key, randomItem.Value);
dict.Remove(randomItem.Key);