多键数据结构
本文关键字:数据结构 | 更新日期: 2023-09-27 17:51:18
我正在寻找一种可以用多个键搜索的数据结构。用一个例子更容易解释:
var myDataStructure = new MultiKeyDataStructure<int, string, MyType>();
myDataStructure.Add(1, "some string 1", new MyType());
myDataStructure.Add(2, "some string 2", new MyType());
var myType = new MyType();
myDataStructure.Add(3, "some string 3", myType);
Tuple<string, MyType> t1 = myDataStructure[1];
Tuple<int, MyType> t2 = myDataStructure["some string 1"];
Tuple<int, string> t3 = myDataStructure[myType];
这样的事情是否可能,如果是这样,是否已经存在任何可以做到这一点的东西?您将如何实现将所有内容视为键并通过搜索其中任何一个返回所有相关键的东西?
理想情况下,您还可以使用任意数量和/或类型的参数:
var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>();
所以这里有一个正好适用于三个键。 您可以按照列出的模式为 4、5、6 等键制作一个。 这将是很多代码,但不是一个特别困难的任务(只是乏味(。
请注意,由于密钥的每个部分都有一个字典,它将占用相当多的内存;这是您为从任何密钥进行非常事实访问的灵活性而付出的代价。
public class MultiKeyDictionary<T1, T2, T3>
{
private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>();
private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>();
private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>();
public void Add(Tuple<T1, T2, T3> values)
{
if (!firstLookup.ContainsKey(values.Item1) &&
!secondLookup.ContainsKey(values.Item2) &&
!thirdLookup.ContainsKey(values.Item3))
{
firstLookup.Add(values.Item1, values);
secondLookup.Add(values.Item2, values);
thirdLookup.Add(values.Item3, values);
}
else
{
//throw an exeption or something.
}
}
public Tuple<T1, T2, T3> GetFirst(T1 key)
{
return firstLookup[key];
}
public Tuple<T1, T2, T3> GetSecond(T2 key)
{
return secondLookup[key];
}
public Tuple<T1, T2, T3> GetThird(T3 key)
{
return thirdLookup[key];
}
public void RemoveFirst(T1 key)
{
var values = GetFirst(key);
firstLookup.Remove(values.Item1);
secondLookup.Remove(values.Item2);
thirdLookup.Remove(values.Item3);
}
public void RemoveSecond(T2 key)
{
var values = GetSecond(key);
firstLookup.Remove(values.Item1);
secondLookup.Remove(values.Item2);
thirdLookup.Remove(values.Item3);
}
public void RemoveThird(T3 key)
{
var values = GetThird(key);
firstLookup.Remove(values.Item1);
secondLookup.Remove(values.Item2);
thirdLookup.Remove(values.Item3);
}
}
下面是一个完全不同的方法。 它不是填充每个键的查找,而是将所有值存储在单个集合中,并执行线性搜索以查找给定键的项。 它将有 O(n( 搜索/删除时间,但 O(1( 添加。 前面的实现有 O(1( 添加、删除和搜索,但占用了更多的内存来执行此操作。
public class MultiKeyDictionary2<T1, T2, T3>
{
private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>();
private HashSet<T1> firstKeys = new HashSet<T1>();
private HashSet<T2> secondKeys = new HashSet<T2>();
private HashSet<T3> thirdKeys = new HashSet<T3>();
public void Add(Tuple<T1, T2, T3> values)
{
if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) ||
object.Equals(multiKey.Item2, values.Item2) ||
object.Equals(multiKey.Item3, values.Item3)))
{
//throw an exception or something
}
else
{
lookup.Add(values);
}
}
public Tuple<T1, T2, T3> GetFirst(T1 key)
{
return lookup.FirstOrDefault(values => object.Equals(values.Item1, key));
}
public Tuple<T1, T2, T3> GetSecond(T2 key)
{
return lookup.FirstOrDefault(values => object.Equals(values.Item2, key));
}
public Tuple<T1, T2, T3> GetThird(T3 key)
{
return lookup.FirstOrDefault(values => object.Equals(values.Item3, key));
}
public void RemoveFirst(T1 key)
{
var values = GetFirst(key);
if (values != null)
lookup.Remove(values);
}
public void RemoveSecond(T2 key)
{
var values = GetSecond(key);
if (values != null)
lookup.Remove(values);
}
public void RemoveThird(T3 key)
{
var values = GetThird(key);
if (values != null)
lookup.Remove(values);
}
}
既然你说你想要编译时类型安全,那么你必须放弃很多东西:
- 具有任意数量的参数的能力(C# 没有可变参数泛型(
- 具有多个相同类型的键的能力(编译器会抱怨不明确的重载(
这两个限制可以通过使用基于反射的方法来解决,但这样您将失去编译时类型安全性。
因此,根据您的约束,这是您将使用的解决方案(仅当所有泛型类型都不同时才有效!
class TripleKeyDictionnary<TKey1, TKey2, TKey3>
{
public Tuple<TKey2, TKey3> this[TKey1 key]
{
get
{
return _key1Lookup[key];
}
}
public Tuple<TKey1, TKey3> this[TKey2 key]
{
get
{
return _key2Lookup[key];
}
}
public Tuple<TKey1, TKey2> this[TKey3 key]
{
get
{
return _key3Lookup[key];
}
}
private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>();
private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>();
private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>();
public void Add(TKey1 key1, TKey2 key2, TKey3 key3)
{
_key1Lookup.Add(key1, Tuple.Create(key2, key3));
_key2Lookup.Add(key2, Tuple.Create(key1, key3));
_key3Lookup.Add(key3, Tuple.Create(key1, key2));
}
}
首先,不幸的是,没有内置的东西,所以你必须手动实现一些东西。
这里的问题是你不能有一个具有未指定数量的泛型类型定义的类,即不存在这样的东西:
class MultiKeyDictionary<T1, ...>
{}
因此,您可以决定实现某些情况(2 键、3 键等,使用类似于Tuple<>
实现的方法(,或者您应该放弃类型安全。
如果您决定使用第一种方法,您应该执行以下操作(使用 3 个键的示例(:
class ThreeKeysDict<T1,T2,T3>
{
var dict1 = new Dictionary<T1,Tuple<T2,T3>>();
var dict2 = new Dictionary<T2,Tuple<T1,T3>>();
var dict3 = new Dictionary<T3,Tuple<T1,T2>>();
public void Add(T1 key1,T2 key2, T3 key3)
{
dict1.Add(key1,Tuple.Create(key2,key3));
dict2.Add(key2,Tuple.Create(key1,key3));
dict3.Add(key3,Tuple.Create(key1,key2));
}
public Tuple<T2,T3> GetByKey1(T1 key1)
{
return dict1[key1];
}
public Tuple<T1,T3> GetByKey2(T2 key2)
{
return dict2[key2];
}
public Tuple<T1,T2> GetByKey3(T3 key3)
{
return dict3[key3];
}
}
非通用版本如下所示:
class MultiKeyDict
{
Dictionary<object, object[]>[] indexesByKey;
public MultiKeyDict(int nKeys)
{
indexesByKey = new Dictionary<object, object[]>[nKeys];
}
public void Add(params object[] values)
{
if (values.Length != indexesByKey.Length)
throw new ArgumentException("Wrong number of arguments given");
var objects = values.ToArray();
for (int i = 0; i < indexesByKey.Length; i++)
this.indexesByKey[i].Add(values[i], objects);
}
public object[] Get(int keyNum, object key)
{
return this.indexesByKey[keyNum][key];
}
}
如果不同键的数量增加,这两种方法都会使用大量内存(因为它们为每个键采用一个字典(。
免責聲明:
代码片段未经测试,缺乏空/超出范围检查等。
他们只是给你一个整体的想法。
当我遇到这种情况时,我只使用两个字典,而不是尝试提出一些新的数据结构。每个字典都有一个映射到该值的可能键。
如果你真的希望它被抽象化,你总是可以创建一个在内部使用两个或多个字典的类,这取决于你需要多少不同类型的键。
你能得到的最接近的东西可能是HashSet<Tuple<int, string, MyType>>
。 HashSet 会自动检查重复项,Tuple
检查其值的等效性。
class MultiKey<T1, T2, T3> : HashSet<Tuple<T1, T2, T3>>
{
public bool Add(T1 t1, T2 t2, T3 t3)
{
return this.Add(Tuple.Create(t1, t2, t3));
}
public T1 Get(T2 t2, T3 t3)
{
var match = this.SingleOrDefault(x => x.Item2.Equals(t2) && x.Item3.Equals(t3));
if (match == null) return default(T1);
else return match.Item1;
}
public T2 Get(T1 t1, T3 t3)
{
var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item3.Equals(t3));
if (match == null) return default(T2);
else return match.Item2;
}
public T3 Get(T1 t1, T2 t2)
{
var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item2.Equals(t2));
if (match == null) return default(T3);
else return match.Item3;
}
}
用法:
key.Add(1, "Foo", new MyType("foo"));
key.Add(2, "Bar", new MyType("bar"));
key.Add(2, "Bar", new MyType("bar")); // Does not add, because it already exists.
var key1 = key.Get("Bar", new Foo("bar")); // Returns 2
var defaultKey = key.Get("Bar", new Foo("foo")); // Returns 0, the default value for an int
var key2 = key.Get(1, new Foo("foo")); // returns "Foo"
您需要确保MyType
通过其值比较相等,如果您将其与大量new
一起使用。 否则,创建一个新的将保证唯一的值。
怎么样
class MultiKeyLookup<A, B, C> : IEnumerable<Tuple<A, B, C>>
{
private readonly ILookup<A, Tuple<B, C>> a;
private readonly ILookup<B, Tuple<A, C>> b;
private readonly ILookup<C, Tuple<A, B>> c;
private readonly IEnumerable<Tuple<A, B, C>> order;
public MultiKeyLookup(IEnumerable<Tuple<A, B, C>> source)
{
this.order = source.ToList();
this.a = this.order.ToLookup(
o => o.Item1,
o => new Tuple<B, C>(o.Item2, o.Item3));
this.b = this.order.ToLookup(
o => o.Item2,
o => new Tuple<A, C>(o.Item1, o.Item3));
this.c = this.order.ToLookup(
o => o.Item3,
o => new Tuple<A, B>(o.Item1, o.Item2));
}
public ILookup<A, Tuple<B, C>> Item1
{
get
{
return this.a
}
}
public ILookup<B, Tuple<A, C>> Item2
{
get
{
return this.b
}
}
public ILookup<C, Tuple<A, B>> Item3
{
get
{
return this.c
}
}
public IEnumerator<Tuple<A, B, C>> GetEnumerator()
{
this.order.GetEnumerator();
}
public IEnumerator IEnumerable.GetEnumerator()
{
this.order.GetEnumerator();
}
}
你会像这样使用,
var multiKeyLookup = new MultiKeyLookup(
new[] {
Tuple.Create(1, "some string 1", new MyType()),
Tuple.Create(2, "some string 2", new MyType())});
var intMatches = multiKeyLookup.Item1[1];
var stringMatches = multiKeyLookup.Item2["some string 1"];
var typeMatches = multiKeyLookup.Item3[myType];
我不确定是否存在任何这样的数据结构,但您可以创建一个。
假设键/子键是唯一的
以下是MultiKeyDictionary
(使用 2 个内部字典,一个用于键(如object
(,一个用于值(。
public class MultiKeyDictionary<TValue>
{
private Dictionary<Guid, TValue> values;
private Dictionary<Object, Guid> keys;
public MultiKeyDictionary()
{
keys = new Dictionary<Object,Guid>();
values = new Dictionary<Guid,TValue>();
}
public IEnumerable<Object> Keys
{
get { return keys.Keys.AsEnumerable();} // May group according to values here
}
public IEnumerable<TValue> Values
{
get { return values.Values;}
}
public TValue this[object key]
{
get
{
if (keys.ContainsKey(key))
{
var internalKey = keys[key];
return values[internalKey];
}
throw new KeyNotFoundException();
}
}
public void Add(TValue value,object key1, params object[] keys) // key1 to force minimum 1 key
{
Add(key1 , value);
foreach( var key in keys)
{
Add (key, value);
}
}
private void Add(Object key, TValue value)
{
var internalKey = Guid.NewGuid();
keys.Add( key, internalKey);
values.Add(internalKey, value);
}
}
它可以用作
MultiKeyDictionary<string> dict = new MultiKeyDictionary<string>();
dict.Add("Hello" , 1,2,3,"StringKey"); // First item is value, remaining all are keys
Console.WriteLine(dict[1]); // Note 1 is key and not intex
Console.WriteLine(dict[2]); // Note 2 is key and not index
Console.WriteLine(dict["StringKey"]);
System.Tuple
,并牢记将其用作字典键。用法:
var dict = new Dictionary<Tuple<string, int>, DateTime>();
dict.Add(Tuple.Create("Louis", 14), new DateTime(1638, 9, 5));
尽管元组语法很麻烦,但静态工厂方法在创建站点上承担了大部分痛苦。