索引集合 [英] indexing a collection

问题描述

我的任务是创建一个DBMS，然后创建3个类，以建立类似于DataTable和DataRow类的层次结构.
实体(T)→表->记录->场
该表是使用反射从实体创建的
为什么以及如何创建它们不是问题.
我现在需要的是根据Records字段对表中的List进行索引，以优化查询"，从而避免对所有Records进行线性探查.
可以说，例如，我需要使用一个名为"unitPrice"的字段进行索引，我需要一个集合
女巫会优化搜索，让其说".. where unitPrice> = 14"
我想到要用字典
字典< K，int>字典
该值是列表中Record的索引，但我需要一个集合除非唯一键外，还要有可能优化范围查询的
所以Dictionary，SortedDictionary，HashTable或SortedList都不可行，因为我需要插入非唯一键，
哈希表对范围查询无济于事，我对可以使用的集合的任何想法将不胜感激

//================================================ ===============================//

我发现我可以使用从列表创建的LookUp女巫，但是我需要一些如何创建一个女巫表达式来给我记录的值作为键(14)以及其他位置的信息这些值可以说(记录15、500、67的单价等于14)

更进一步，我认为哈希表会知道如何处理重复的键....并不是说哈希的全部要点



提前10倍.eran.

my assignment is to create a DBMS iv''e created 3 classes witch build an hierarchy similar to the DataTable and DataRow Classes
Entity (T)-> Table -> Record -> Field
the Table is created from an Entity using Reflection
why and how i created them is not the issue .
what i need now is to index the List inside the Table according the the Records fields in order to optimize "query''s" , so as to avoid a linear probe of all the Records
lets say for example i need to index using a field called "unitPrice" i need a collection
witch would optimize the search for lets say " .. where unitPrice >= 14"
i thought of using a dictionary
Dictionary<K,int> dict
the value being the index of the Record in the list , but i need a collection witch would except non-unique keys as well as would have the possibility to optimize range query''s
so Dictionary , SortedDictionary ,HashTable or SortedList are out of the question because i need non-unique keys to be inserted ,
and a hashtable wouldn''t help with range query''s any ideas of what collection i could use would be most appreciated

//================================================================================//

iv''e found out i could use something called a LookUp witch is created by from a list , but i need to some how create an expression witch would give me the value of the record as the key (14) and the different positions as the values lets say ( records 15 ,500 ,67 hold a unit price witch is equal to 14 )

further more i thought the hashtable would know how to handle duplicate keys .... isn''t that the all point of hashing



10x in advance .eran.

推荐答案

散列和字典的要点是使用唯一键bur，同时也可以通过该键快速搜索，您可以将其称为索引.搜索速度为O(1)，请参见 http://en.wikipedia.org/wiki/Big_O_notation [ ^ ].如果您考虑一下，您将理解非唯一键不能与索引一起使用.但是，可以将具有相同键的对象与Dictionary一起使用.

为此，对于元素类型ELEMENT和键类型KEY，您需要使用组合的集合类型:

The point of hashing and Dictionary is using the unique keys bur also fast search by the key, which you can call indexing. The speed of search is of O(1), see http://en.wikipedia.org/wiki/Big_O_notation[^]. If you think about it, you will understand that a non-unique key cannot be used with indexing. However, you can use objects with the same key with Dictionary.

For this purpose, for an element type ELEMENT and key type KEY you need to use the combined collection type:

System.Collections.Generic.Dictionary<KEY, System.Collections.Generic.List<ELEMENT>>

这不是很清楚吗?这是将元素添加到此类组合集合的方法:

Isn''t this clear? This is how to add an element to such combined collection:

using KeyedCollection = System.Collections.Generic.Dictionary<Key, System.Collections.Generic.List<int>>;
using ElementList = System.Collections.Generic.List<int>;

//..

class Key {/*...*/} //I don't know what do you need -- anything

//..

KeyedCollection Dictionary new KeyedCollection();

void AddKey(Key key, int element) {
    ElementList list;
    if (!Dictionary.TryGetValue(key, out list)) {
       list = new ElementList();
       Dictionary.Add(key, list);
    } //if
    list.Add(element);
}

如果键已在字典中，则将获取字典值(即列表)，并向其中添加元素，否则将添加新列表.

您可以使用SortedDictionary和SortedList做类似的事情.

—SA

If the key is already in dictionary, you get the dictionary value (which is list), and add your element to it, otherwise you add a new list.

You can do the similar thing using SortedDictionary and SortedList.

—SA

这篇关于索引集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！