具有O(1)查找时间的数据结构,这将允许重复

Question

我的目标是创建一个实现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>以便:

1. 查找操作有O(1)时间.
2. 所有其他操作具有相同的O()性能List<T>
3. 内存可能受哈希表开销(constantA + constantB * n字节)的影响.
4. 必须允许重复
5. 允许空值是可选的(它们可以装入空对象)

Answer 1

基于所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 n) 操作时间。

编辑2：另一种簿记类型方法
我只是在脑海中反复思考这个方法，所以我只会给出一些粗略的伪代码，但您可能会采取一种方法，其中您只有一个映射到索引列表的项目字典，并且将索引映射到项目的第二个字典。如果添加 T 是类的限制，那么您只需支付两次引用存储的开销。然后，您需要维护当前的“最后一个”，以便可以轻松地将新项目添加到集合中。这应该会使删除操作更加干净一些。它仍然是 O(n)，因为您必须使用索引 > 已删除的项目来更新任何内容。在第一印象中，这似乎是一个潜在的解决方案，可以让您接近您想要实现的目标（如果我正确理解目标）。