4

我有一个我不知道的 Hashtable 的内容是什么。

现在我想从中获得一个 Key 和 value；

我使用 hashtable 是因为它的速度，因为 hashtable 的内容超过 4,500,000 KeyValuePair 所以我不能使用 GetEnumerator 它降低程序速度

4

6 回答 6

6

你使用一个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)];

我们只是创建一个List<TKey>其元素指向内存中与哈希表的键相同的位置，然后我们从该列表中选择一个随机元素。

如果你想从哈希表中获取一个随机元素值，这应该很简单，给定一个随机键。

string randomeElement = dict[randomKey];
于 2012-08-14T21:28:03.277 回答
4

我不能使用 GetEnumerator 降低程序速度”

那是个问题。您已经接受了一个遍历所有条目的答案，并且还将键复制到一个新列表中，因此尚不清楚您是否已经放弃了该要求。

一种在内存和速度上肯定会更有效的方法是迭代整个字典，但在任何时候保留一个随机元素，并优化我们可以廉价获得计数的集合。这是一个扩展方法，它将对.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;
}

因此，对于Dictionary<TKey, TValue>您最终会以KeyValuePair<TKey, TValue>这种方式结束-或者您可以Keys先进行投影：

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

（有关这方面的问题，请参阅我的文章Random。）

如果您想要一个真正的伪随机密钥，而不仅仅是一个任意密钥（您可以通过获取序列中的第一个密钥来获得，那么我认为您不会比 O(n) 做得更好）另有说明）。

请注意，将键复制到列表中，如 Darin 的回答，当然可以更有效地获取多个随机元素。这一切都取决于您的要求。

于 2012-08-23T07:28:32.940 回答
2

随机密钥必须有多随机？

哈希表没有定义存储它们的项目的顺序，所以你可以抓住第一个项目。它不是真正随机的，但也不是插入顺序或排序顺序。这会足够随机吗？

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

KeyValuePair<string, string> randomItem = dict.First();
DoAComputation(randomItem.Key, randomItem.Value);
dict.Remove(randomItem.Key);
于 2012-08-14T21:50:31.250 回答
2

使用 Linq，您可以：

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;

例如，

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

将 Dicto 中第三十项的值复制到字符串 tmp。

在内部，我认为它一次遍历一个密钥对，直到它到达第三十个，而不是全部复制它们，因此您不需要将所有元素加载到内存中。

我不确定你不知道内容是什么意思。

你不知道dicto的KeyValuePair中的类型吗？或者只是不知道dicto中的值是什么？

于 2012-08-15T00:12:01.623 回答
1

Hashtable.Keys 会给你一个指向内部键列表的指针。那是快速的。从 Hashtable 中删除一个项目也是一个 O(1) 操作，因此即使有大量项目，这也会很快。

你可以做一个这样的循环（我认为没有理由在你的问题中使用随机）；

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)  
 }
}
于 2012-08-15T13:20:48.300 回答
0

好吧，如果您知道您将针对哪个版本的 .NET BCL（即，如果它已修复），您总是可以深入了解它的内部结构，Dictionary<TKey, TValue>以找出它如何私下存储其密钥并使用它来随机抽取一个。

例如，使用我目前在工作笔记本电脑上安装的 Mono 版本，我看到该Dictionary<TKey, TValue>类型有一个名为的私有字段keySlots（我假设如果您使用的是 Windows，这对您来说会有所不同）。使用这些知识，您可以实现如下所示的函数：

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;
}

在您的情况下，这可能是一个合适的解决方案，或者它可能是一个可怕的想法。只有您有足够的上下文来进行该调用。

至于上面的示例方法：我个人喜欢将扩展方法添加到Random类中，以实现任何涉及随机性的功能。那只是我的选择；显然你可以走不同的路线。

于 2012-08-15T01:06:34.737 回答