词典/急速订购的边缘案例(需要现有的示例)

我已经阅读了有关字典/哈希集和其他无序集合订单问题的官方MSDN DOC和多个SO问题。这个问题有些不同 - 我正在寻找实际实践示例，而不是理论

条件：

只能添加词典/hastable条目
永远不会删除字典/匆忙条目（除非在开始时清除）
词典/hastable仅具有价值类型
除了添加元素以外，词典/hastable永远不会以任何其他方式更改
词典/hastable总是从0开始，并通过简单的代码逻辑保留索引
字典键本身（关键名称）永远不会手动更改

代码示例：

Dictionary<int, int> test = new Dictionary<int, int>();
for (int i = 0; i <= 100000; i++)
{
    test.Add(i,i);
}
var c = 0;
while (c < test.Count)
{
    if (c != test.ElementAt(c).Key)
    {
        Console.WriteLine("Mismatch!");
        break;
    }
    c++;
}
Console.WriteLine("Test passed!");
//Program takes a 2hrs walk, does things, occasionally reads-only values from existing "test" collection
for (int i = 0; i <= 500000; i++)
{
    test[test.Count] = test.Count;
}
c = 0;
while (c < test.Count)
{
    if (c != test.ElementAt(c).Key)
    {
        Console.WriteLine("Mismatch!");
        break;
    }
    c++;
}
Console.WriteLine("Test 2 passed!");
//repeat some stuff

问题：在上面给定的严格规则下 - 当这种字典随机更改其元素顺序时，是否有人遇到过这种情况？我们不是在这里又一次地谈论MT并发收藏，我对理论答案不感兴趣，我已经阅读了它们。

我要寻找的是test.ElementAt(5).key返回key或115的一个示例。

Dictionary<TKey, TValue>的源代码在此处可用。如果您查看Enumerator.MoveNext()，您会看到它通过数组dictionary.entries按顺序迭代：

while ((uint)index < (uint)dictionary.count) {
    if (dictionary.entries[index].hashCode >= 0) {
        current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
        index++;
        return true;
    }
    index++;
}

，如果您查看 private void Insert(TKey key, TValue value, bool add)（在添加和设置项目时称为 CC_8），只要没有免费条目（即没有删除任何内容），您就会看到如果找不到密钥，则位于entries数组的末端，如果找到键，则放置在当前位置：

private void Insert(TKey key, TValue value, bool add) {    
// Snip 
    int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
    int targetBucket = hashCode % buckets.Length;
// Snip 
    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
// Key found.  Set the new value at the old location in the entries array.
            if (add) { 
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
            }
            entries[i].value = value;
            version++;
            return;
        }  
        // Snip 
    }
// Key not found, add to the dictionary.
    int index;
    if (freeCount > 0) {
// Free entries exist because items were previously removed; recycle the position in the entries array.
        index = freeList;
        freeList = entries[index].next;
        freeCount--;
    }
    else {
// No free entries.  Add to the end of the entries array, resizing if needed.
        if (count == entries.Length)
        {
            Resize();
            targetBucket = hashCode % buckets.Length;
        }
        index = count;
        count++;
    }
// Set the key and value in entries array.
    entries[index].hashCode = hashCode;
    entries[index].next = buckets[targetBucket];
    entries[index].key = key;
    entries[index].value = value;
    buckets[targetBucket] = index;
// Snip remainder

最后，如果您检查Resize()，即调用词典的方法，您将看到entries数组的顺序保留了：

    Array.Copy(entries, 0, newEntries, 0, count);

因此，我们可以说在此实现中，只要没有删除任何内容词典保留了添加键的顺序。

，但这只是一个实现细节。单声道上的Dictionary<TKey, TValue>版本（或某些未来.NET版本，例如.NET CORE 3.5或.NET FULL 5.2或其他任何内容）可以被重写，以便重新进行字典更改顺序。文档做出的唯一承诺是返回项目的顺序是不确定的，因此更依赖任何东西是不明智的。

相关内容

最新更新

热门标签：