blocks|key|1177202|text|我唯一能看到这一点的方法就是使用一本列表字典。按下键会给出创建该特定键的所有重复项的列表。只要总是接受第一个。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1177203|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The only way I could see this is using a dictionary of lists. Hitting the key gives you a list of all duplicates that create that particular key. Just always take the first one.

blocks|key|1891030|text|如果你能用O(1)搜索时间开发一个结构，你会发现自己变得非常富有：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1891031|基本上这种类型的结构不存在，与此最接近的是一个哈希表|offset|length|1891032|C#有一个内置哈希表类型-+C~+Hash表|1891033|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Hash_table|1|http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx^0|0|N|3|0|0|E|8|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

If you can develop a structure with O(1) search time you will find yourself becoming very very rich :p

Basically this type of structure doesn't exist, the closest this to this is a <a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow">Hash table</a>

C# has a built in hash table type - <a href="http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx" rel="nofollow">C~ Hash Table</a>

blocks|key|1174729|text|哈希表应包含每个键的索引列表。我想这就是你所需要的，不是吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1174730|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The hash table should hold a list of indices for each key. And I think this is all you need, no?

blocks|key|1177224|text|在Ryan+Bennett提议的基础上，我认为最好的方法是创建一个实现IList的类，然后在内部实现如下内容：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1177225|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%2B1;+i+<+_items.Count;+%2B%2Bi)
++++++++{
++++++++++++List<int>+otherIndexList+=+_indexMap[_items[i]];
++++++++++++for(int+j=0;+j+<+otherIndexList.Count;+%2B%2Bj)
++++++++++++{
++++++++++++++++int+temp+=+otherIndexList[j];
++++++++++++++++if+(temp+>+index)
++++++++++++++++{
++++++++++++++++++++otherIndexList[j]+=+--temp;
++++++++++++++++}
++++++++++++}
++++++++}

++++++++return+_items.RemoveAt(index);
++++}

++++//+...+Other+similar+type+functions+here
}|code-block|syntax|javascript|1177226|编辑：|1177227|刚刚意识到，当你做Remove的时候，事情会变得很棘手。您必须遍历索引集合，并使用值>删除项的索引更新任何索引。您现在增加了“删除”时间。你也让这件事变得很棘手。如果您想要实现这样的东西，我会在这个集合周围抛出大量的单元测试。|1177228|我知道你在说明订单是重要的，所以我假设这就是为什么你不使用排序列表的方法，这将允许重复，并给你O(log+)操作时间。|1177229|编辑2:另一种簿记类型方法|1177230|我只是在脑海中弹出这个，所以我只会给出一些粗略的伪代码，但是您可能会采取一种方法，您可以使用一种方法，即您只需要将一个项字典映射到一个索引列表，而另一个字典将索引映射到项目。如果添加T是类的限制，则只需支付引用的两个存储库的开销。然后，您需要维护当前的“最后一项”，以便您可以轻松地向集合中添加一个新项。这应该会使删除操作变得更干净一些。它仍然是O(n)，因为您必须用索引>删除项来更新任何内容。在最初的设想中，这似乎是一个潜在的解决方案，它将使你接近你想要达到的目标(如果我正确理解目标的话)。|1177231|entityMap^0|1|C|0|0|0|9|6|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@]|D|@]|E|$]]|$1|M|3|N|5|6|7|11|8|@$9|12|A|13|B|C]]|D|@]|E|$]]|$1|O|3|P|5|6|7|14|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|15|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|16|8|@]|D|@]|E|$]]|$1|U|3|-4|5|6|7|17|8|@]|D|@]|E|$]]]|V|$]]

Building on what <code>Ryan Bennett</code> has proposed, I think the best you are going to come up with (as you state order is important) is to create a class that implements IList and then internally has something like this:

<pre><code>class MyList&lt;T&gt; : IList&lt;T&gt;
{
 Dictionary&lt;T, List&lt;int&gt;&gt; _indexMap;
 List&lt;T&gt; _items;


 public int IndexOf(T item)
 {
 List&lt;int&gt; indices;
 if(_indexMap.TryGetValue(item, out indices))
 {
 return indices[0];
 }
 return -1;
 }

 public void Add(T item)
 {
 List&lt;int&gt; indices;
 if(!_indexMap.TryGetValue(item, out indices))
 {
 indices = new List&lt;int&gt;();
 _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&lt;int&gt; 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 &lt; _items.Count; ++i)
 {
 List&lt;int&gt; otherIndexList = _indexMap[_items[i]];
 for(int j=0; j &lt; otherIndexList.Count; ++j)
 {
 int temp = otherIndexList[j];
 if (temp &gt; index)
 {
 otherIndexList[j] = --temp;
 }
 }
 }

 return _items.RemoveAt(index);
 }

 // ... Other similar type functions here
}
</code></pre>

Edit:

Just realized that things get real sticky here when you do a <code>Remove</code>. You will have to walk the collection of indices and update any index with a value > the index of the item you remove. You have now increased the "remove" time. You have also made it tricky to get correct. I would throw a massive amount of unit tests around this collection if you were going to try to implement something like this.

I know you are stating order is important so I am assuming that is why you are not going wtih a Sorted list approach which would allow the duplicates and give you O(log n) operation times.

Edit 2: Another book keeping type approach 
I am just bouncing this one around in my head and so I will only give some rough pseudo code but you could possibly take an approach where you just have a dictionary of items mapped to a list of indices and a second dictionary that maps indices to items. If you add the restriction that T is a class then you are only paying the overhead of two storages of the reference. You then need to maintain a current "last" so that you can easily add a new item into the collection. This should make the remove operation a bit cleaner. It is still O(n) because you have to update anything with an index > the removed item. In first imaginings, this seems like a potential solution that will get you close to what you want to achieve (if I am understanding the goals correctly).

My goal is to create a data structure implementing <code>IList&lt;T&gt;</code> interface which will achieve <code>O(1)</code> element lookup time by compromising memory.

Background
As you know all array based <code>IList&lt;T&gt;</code> implementations like <code>List&lt;T&gt;</code> have <code>O(n)</code> element lookup time. It means that the operations like <code>int IndexOf(T element)</code> or <code>bool Contains(T element)</code> iterate through the underlaying array until they find a match.

Well known idea achive that is to use a combination of a list and hashtable as underlaying data structures. Values are kept in a list. The hashtable will keep indexes as values and values of list as keys. So lookup can be performed using hashtable.

That's exactly how the <code>KeyedCollection&lt;TKey, TItem&gt;</code> <a href="http://msdn.microsoft.com/en-us/library/ms132438.aspx" rel="nofollow">see MSDN</a> is implemented.

What I have tried so far

<pre><code>internal class MyList&lt;T&gt; : KeyedCollection&lt;T, T&gt;
{
 protected override T GetKeyForItem(T item)
 {
 return item;
 }
}
</code></pre>

This worked so far except one problem. This data structure does not mimic the behavior expected behind <code>List&lt;T&gt;</code> exactly. The point is that the <code>List&lt;T&gt;</code> allows duplicates, <code>MyList</code> does not.

Question

Is there any ready to use data structure or can you recommend an elegant way of implementing the <code>IList&lt;T&gt;</code> so that:

<ol>
<li>Lookup operations have <code>O(1)</code> time.</li>
<li>All other operations have same <code>O()</code> performance as <code>List&lt;T&gt;</code></li>
<li>Memory can be compromised by hashtable overhead (<code>constantA + constantB * n</code> bytes).</li>
<li>Duplicates must be allowed</li>
<li>Allowing nulls is optional (they can be boxed into null objects)</li>
</ol>

Data structure with O(1) lookup time which will allow duplicates

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我的目标是创建一个实现IList<T>接口的数据结构，通过牺牲内存来实现O(1)元素查找时间。背景，如您所知，所有基于数组的IList<T>实现(如List<T> )都有O(n)元素查找时间。这意味着像int IndexOf(T element)或bool Contains(T element)这样的操作在底层数组中迭...

问具有O(1)查找时间的数据结构，允许重复查找
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问具有O(1)查找时间的数据结构，允许重复查找EN