Admin
1
Are there any dictionary classes in the .NET base class library which allow duplicate keys to be used? The only solution I've found is to create, for example, a class like:
Dictionary<string, List<object>>
But this is quite irritating to actually use. In Java, I believe a MultiMap accomplishes this, but cannot find an analog in .NET.
If you're using .NET 3.5, use the Lookup class.
EDIT: You generally create a Lookup using Enumerable.ToLookup. This does assume that you don't need to change it afterwards - but I typically find that's good enough.
If that doesn't work for you, I don't think there's anything in the framework which will help - and using the dictionary is as good as it gets :(
The List class actually works quite well for key/value collections containing duplicates where you would like to iterate over the collection. Example:
List<KeyValuePair<string, string>> list = new List<KeyValuePair<string, string>>();
// add some values to the collection here
for (int i = 0; i < list.Count; i++)
{
Print(list[i].Key, list[i].Value);
}
Here is one way of doing this with List< KeyValuePair< string, string > >
public class ListWithDuplicates : List<KeyValuePair<string, string>>
{
public void Add(string key, string value)
{
var element = new KeyValuePair<string, string>(key, value);
this.Add(element);
}
}
var list = new ListWithDuplicates();
list.Add("k1", "v1");
list.Add("k1", "v2");
list.Add("k1", "v3");
foreach(var item in list)
{
string x = string.format("{0}={1}, ", item.Key, item.Value);
}
Outputs k1=v1, k1=v2, k1=v3
If you are using strings as both the keys and the values, you can use System.Collections.Specialized.NameValueCollection, which will return an array of string values via the GetValues(string key) method.
I just came across the PowerCollections library which includes, among other things, a class called MultiDictionary. This neatly wraps this type of functionality.
Very important note regarding use of Lookup:
You can create an instance of a Lookup(TKey, TElement) by calling ToLookup on an object that implements IEnumerable(T)
There is no public constructor to create a new instance of a Lookup(TKey, TElement). Additionally, Lookup(TKey, TElement) objects are immutable, that is, you cannot add or remove elements or keys from a Lookup(TKey, TElement) object after it has been created.
I'd think this would be a show stopper for most uses.
Since the new C# (I belive it's from 7.0), you can also do something like this:
var duplicatedDictionaryExample = new List<(string Key, string Value)> { ("", "") ... }
and you are using it as a standard List, but with two values named whatever you want
foreach(var entry in duplicatedDictionaryExample)
{
// do something with the values
entry.Key;
entry.Value;
}
The NameValueCollection supports multiple string values under one key (which is also a string), but it is the only example I am aware of.
I tend to create constructs similar to the one in your example when I run into situations where I need that sort of functionality.
Do you mean congruent and not an actual duplicate? Otherwise a hashtable wouldn't be able to work.
Congruent means that two separate keys can hash to the equivalent value, but the keys aren't equal.
For example: say your hashtable's hash function was just hashval = key mod 3. Both 1 and 4 map to 1, but are different values. This is where your idea of a list comes into play.
When you need to lookup 1, that value is hashed to 1, the list is traversed until the Key = 1 is found.
If you allowed for duplicate keys to be inserted, you wouldn't be able to differentiate which keys map to which values.
The way I use is just a
Dictionary<string, List<string>>
This way you have a single key holding a list of strings.
Example:
List<string> value = new List<string>();
if (dictionary.Contains(key)) {
value = dictionary[key];
}
value.Add(newValue);
You can create your own dictionary wrapper, something like this one, as a bonus it supports null value as a key:
/// <summary>
/// Dictionary which supports duplicates and null entries
/// </summary>
/// <typeparam name="TKey">Type of key</typeparam>
/// <typeparam name="TValue">Type of items</typeparam>
public class OpenDictionary<TKey, TValue>
{
private readonly Lazy<List<TValue>> _nullStorage = new Lazy<List<TValue>>(
() => new List<TValue>());
private readonly Dictionary<TKey, List<TValue>> _innerDictionary =
new Dictionary<TKey, List<TValue>>();
/// <summary>
/// Get all entries
/// </summary>
public IEnumerable<TValue> Values =>
_innerDictionary.Values
.SelectMany(x => x)
.Concat(_nullStorage.Value);
/// <summary>
/// Add an item
/// </summary>
public OpenDictionary<TKey, TValue> Add(TKey key, TValue item)
{
if (ReferenceEquals(key, null))
_nullStorage.Value.Add(item);
else
{
if (!_innerDictionary.ContainsKey(key))
_innerDictionary.Add(key, new List<TValue>());
_innerDictionary[key].Add(item);
}
return this;
}
/// <summary>
/// Remove an entry by key
/// </summary>
public OpenDictionary<TKey, TValue> RemoveEntryByKey(TKey key, TValue entry)
{
if (ReferenceEquals(key, null))
{
int targetIdx = _nullStorage.Value.FindIndex(x => x.Equals(entry));
if (targetIdx < 0)
return this;
_nullStorage.Value.RemoveAt(targetIdx);
}
else
{
if (!_innerDictionary.ContainsKey(key))
return this;
List<TValue> targetChain = _innerDictionary[key];
if (targetChain.Count == 0)
return this;
int targetIdx = targetChain.FindIndex(x => x.Equals(entry));
if (targetIdx < 0)
return this;
targetChain.RemoveAt(targetIdx);
}
return this;
}
/// <summary>
/// Remove all entries by key
/// </summary>
public OpenDictionary<TKey, TValue> RemoveAllEntriesByKey(TKey key)
{
if (ReferenceEquals(key, null))
{
if (_nullStorage.IsValueCreated)
_nullStorage.Value.Clear();
}
else
{
if (_innerDictionary.ContainsKey(key))
_innerDictionary[key].Clear();
}
return this;
}
/// <summary>
/// Try get entries by key
/// </summary>
public bool TryGetEntries(TKey key, out IReadOnlyList<TValue> entries)
{
entries = null;
if (ReferenceEquals(key, null))
{
if (_nullStorage.IsValueCreated)
{
entries = _nullStorage.Value;
return true;
}
else return false;
}
else
{
if (_innerDictionary.ContainsKey(key))
{
entries = _innerDictionary[key];
return true;
}
else return false;
}
}
}
The sample of usage:
var dictionary = new OpenDictionary<string, int>();
dictionary.Add("1", 1);
// The next line won't throw an exception;
dictionary.Add("1", 2);
dictionary.TryGetEntries("1", out List<int> result);
// result is { 1, 2 }
dictionary.Add(null, 42);
dictionary.Add(null, 24);
dictionary.TryGetEntries(null, out List<int> result);
// result is { 42, 24 }
I changed @Hector Correa 's answer into an extension with generic types and also added a custom TryGetValue to it.
public static class ListWithDuplicateExtensions
{
public static void Add<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, TValue value)
{
var element = new KeyValuePair<TKey, TValue>(key, value);
collection.Add(element);
}
public static int TryGetValue<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, out IEnumerable<TValue> values)
{
values = collection.Where(pair => pair.Key.Equals(key)).Select(pair => pair.Value);
return values.Count();
}
}
i use this simple class:
public class ListMap<T,V> : List<KeyValuePair<T, V>>
{
public void Add(T key, V value) {
Add(new KeyValuePair<T, V>(key, value));
}
public List<V> Get(T key) {
return FindAll(p => p.Key.Equals(key)).ConvertAll(p=> p.Value);
}
}
usage:
var fruits = new ListMap<int, string>();
fruits.Add(1, "apple");
fruits.Add(1, "orange");
var c = fruits.Get(1).Count; //c = 2;
Duplicate keys break the entire contract of the Dictionary. In a dictionary each key is unique and mapped to a single value. If you want to link an object to an arbitrary number of additional objects, the best bet might be something akin to a DataSet (in common parlance a table). Put your keys in one column and your values in the other. This is significantly slower than a dictionary, but that's your tradeoff for losing the ability to hash the key objects.