具有O(1)查找时间的数据结构，允许重复查找
我的目标是创建一个实现IList<T>接口的数据结构，通过牺牲内存来实现O(1)元素查找时间。
背景，如您所知，所有基于数组的IList<T>实现(如List<T> )都有O(n)元素查找时间。这意味着像int IndexOf(T element)或bool Contains(T element)这样的操作在底层数组中迭代，直到找到匹配的数组。
众所周知的想法是使用列表和哈希表的组合作为底层数据结构。值保存在列表中。哈希表将把索引保持为值，将列表的值保留为键。因此，可以使用哈希表执行查找。
这正是KeyedCollection<TKey, TItem> 见MSDN的实现方式。
到目前为止我尝试过的
internal class MyList<T> : KeyedCollection<T, T>
{
protected override T GetKeyForItem(T item)
{
return item;
}
}到目前为止，除了一个问题外，这是可行的。这个数据结构并不完全模仿List<T>所期望的行为。关键是List<T>允许复制，而MyList不允许复制。
问题
是否已经准备好使用数据结构，或者您是否可以推荐一种实现IList<T>的优雅方法，以便：
- 查找操作有
O(1)时间。 - 所有其他操作的
O()性能与List<T>相同。 - 内存可能会受到哈希表开销(
constantA + constantB * n字节)的影响。 - 必须允许副本
- 允许空是可选的(可以将它们装箱到空对象中)
回答 4
Stack Overflow用户
发布于 2012-11-29 18:38:19
在Ryan Bennett提议的基础上，我认为最好的方法是创建一个实现IList的类，然后在内部实现如下内容：
class MyList<T> : IList<T>
{
Dictionary<T, List<int>> _indexMap;
List<T> _items;
public int IndexOf(T item)
{
List<int> indices;
if(_indexMap.TryGetValue(item, out indices))
{
return indices[0];
}
return -1;
}
public void Add(T item)
{
List<int> indices;
if(!_indexMap.TryGetValue(item, out indices))
{
indices = new List<int>();
_indexMap[item] = indices;
}
indices.Add(_items.Count);
_items.Add(item);
}
// Attempt at a Remove implementation, this could probably be improved
// but here is my first crack at it
public bool Remove(T item)
{
List<int> indices;
if(!_indexMap.TryGetValue(item, out indices))
{
// Not found so can just return false
return false;
}
int index = indices[0];
indices.RemoveAt(0);
if (indices.Count == 0)
{
_indexMap.Remove(item);
}
for(int i=index+1; i < _items.Count; ++i)
{
List<int> otherIndexList = _indexMap[_items[i]];
for(int j=0; j < otherIndexList.Count; ++j)
{
int temp = otherIndexList[j];
if (temp > index)
{
otherIndexList[j] = --temp;
}
}
}
return _items.RemoveAt(index);
}
// ... Other similar type functions here
}编辑：
刚刚意识到，当你做Remove的时候，事情会变得很棘手。您必须遍历索引集合，并使用值>删除项的索引更新任何索引。您现在增加了“删除”时间。你也让这件事变得很棘手。如果您想要实现这样的东西，我会在这个集合周围抛出大量的单元测试。
我知道你在说明订单是重要的，所以我假设这就是为什么你不使用排序列表的方法，这将允许重复，并给你O(log )操作时间。
编辑2:另一种簿记类型方法
我只是在脑海中弹出这个，所以我只会给出一些粗略的伪代码，但是您可能会采取一种方法，您可以使用一种方法，即您只需要将一个项字典映射到一个索引列表，而另一个字典将索引映射到项目。如果添加T是类的限制，则只需支付引用的两个存储库的开销。然后，您需要维护当前的“最后一项”，以便您可以轻松地向集合中添加一个新项。这应该会使删除操作变得更干净一些。它仍然是O(n)，因为您必须用索引>删除项来更新任何内容。在最初的设想中，这似乎是一个潜在的解决方案，它将使你接近你想要达到的目标(如果我正确理解目标的话)。
Stack Overflow用户
发布于 2012-11-29 18:22:41
我唯一能看到这一点的方法就是使用一本列表字典。按下键会给出创建该特定键的所有重复项的列表。只要总是接受第一个。
Stack Overflow用户
发布于 2012-11-29 18:25:15
哈希表应包含每个键的索引列表。我想这就是你所需要的，不是吗？
https://stackoverflow.com/questions/13632070
复制相似问题
腾讯云开发者
