维护字典中的数据局部性

Question

我正在制作游戏，出于某种原因，我决定给每个游戏对象一个int实体ID，这样我就可以轻松地搜索它们，而不必线性搜索一个列表或更糟的是很多列表。这个想法是受ECS模式启发的，我认为如果确保在销毁int时重用它们，它将有助于使所有数据在内存中保持紧密结合，并稍微减少缓存丢失。 （我知道这更多地取决于访问顺序，只是在这里进行抽象思考）。问题是我现在正在怀疑自己，而且我读了太多书，以至于无法将这些想法摆在脑海中。

我在下面放置了一些示例代码来尝试说明我的想法，但是本质上是如果我不断向Dictionary<int, SomeClass>不断添加编号更高的键，那么速度/内存使用情况是否会比我差？尝试重新使用较低的数字？

注：我觉得答案将是“编写自己的课程”，但我试图避免这种情况，如果我不理解这个概念，我认为我做不好。

public class EntityManager
{
public uint createdEntities { get; private set; }
public uint next { get { return createdEntities++; } }
private LinkedList<int> freeEntities;

public Dictionary<int, GameObject> allTheThings;

int GetNewEntityID()
{
    if (freeEntities.Count > 0)
    {
        int firstFree = freeEntities.First.Value;
        freeEntities.RemoveFirst();
        return firstFree;
    }
    else
    {
        return createdEntities++;
    }
}
}

Answer 1

不，完全没有区别。从MSDN：

Dictionary泛型类提供了从一组键到一组值的映射。字典的每个加法项都包含一个值及其关联的键。使用Dictionary的键检索值非常快，接近O（1），因为Dictionary类是作为哈希表实现的。

因此，速度将始终为O（1），因为它在内部使用哈希表，键的值完全不影响它。

您唯一可以面对的问题是，如果您达到int.MaxValue，这取决于您的场景。

Answer 2

好吧，这是我自己的最大努力，如果我发现任何错误，我们深表歉意。

简短回答：否。如果添加更高的数字，它们只会卡在阵列中的某个位置，直到充满为止。解决此示例问题的方法是仅将字典替换为GameObject数组，然后将int用作索引，并在必要时编写一个类来对其进行扩展。

更长的答案：我认为我的困惑来自阅读某处字典只是一对并行数组之类的东西。我猜是对的，但是由于它是由哈希码索引的，因此不适合连续的索引值。因此，它正在做大量多余的工作来处理我永远不会用它的情况。