Custom Hashtable C#

you are talking about a million objects and in this scenario a database will be tbe best option because a million objects in dictionary/hashtable will consume a lot of memory and will decrease the performance

True, and I know that, but database is not an option in my case. But forgetting million, how would you deal with a large collection?

i will prefer a dictionary over hashtable because at least the overhead of boxing and unboxing will not occur

The Dictionary class has the same functionality as the Hashtable class. A Dictionary of a specific type (other than Object) has better performance than a Hashtable for value types because the elements of Hashtable are of type Object and, therefore, boxing and unboxing typically occur if storing or retrieving a value type. - this from the following link
http://msdn.microsoft.com/en-us/library/4yh14awz(VS.80).aspx

Thank you ragi.  As I mentioned, I tried Hashtables and Dictionaries, that's why I suggested a custom solution. How would you deal with duplicates in Key field?

I remembered that there was a specialized collection that does pretty much what you described in Collections.Specialized, namely NameValueCollection, but it's no good since it uses only strings.
A quick search turned up this, don't know if it will help you or not, but may be another take on the idea (you could easily modify it to accept generic keys, I think).

a million objects is nothing to keep in memory ...

What is your duplciation like as a percentage? whats the highest count of dduplications you expect?

Greg

rags: just to be clear in this example a million (gasp objects) as say ints would take up a whopping 4 mb of memory! even once we add the overhead of the hash table's extra size (fill factor) we might be at 6? Oh Noez. Even with small objects say an address we would still be < 100 mb which again is nothing.

Not surprisingly the cost to make an out of process call to the database is about a million times larger than checking our value in memory.

there are certainly some archtitectural situations where you would want to keep the hash in memory.

oh well no response so here are the answers.

If your number of duplicates is low just make a Dictionary<whatever, List<whatevervalue>> almost as efficient as chainging and avoids the overhead of writing your own Dictionary (though writing one isn't that hard just meet the Idictionary<T,V> interface (I am sure we all wrote one at some point)..

If you expect a high number of duplicates then chaining or using the list<> as above would really suck instead use a Dictionary<T, Dictionary<T, V>> where the internal dictionary has a different hashing algorithm than the first one.

It really depends how many duplicates you expect to be seeing on average and whether or not the checking of the duplicates in a chain/list has a higher cost than running a hash function on your key.

the aurhor has never mentioned what kind of objects are being delt with - so if they are going to contain even a single stirng object the its a bad design to keep it in memory

as dictionary is also a key value pair i totally agree with your approach of keeping the key in the dictionayr and values in a generic list

"the aurhor has never mentioned what kind of objects are being delt with - so if they are going to contain even a single stirng object the its a bad design to keep it in memory"

Not at all.

You seem to be woefully ignorant of this thing called context. As I explained previously keeping them in memory allows for searches that are many order of magnitude faster than hitting an out of process call. If you need fast searching then its perfectly fine to be doing as a design decision.

Also keeping millions of objects in memory really is not that big of a deal. As an example I created some time ago a program that kept the entire state of the Toronto Stock Exchange in memory (orders and all). This was 3-5 million objects in memory at any given point (and they were not simple objects). The application ran in about a gig of memory but do to our other requirements (like needing to process 20k+ changes to the data per second) using something like a database would not have been a cost effective solution.

It is in fact quite common to put millions of objects in memory for performance reasons (with a horizontal partitioning plan) for when you run out of memory on a given machine. For reference see a "prevalence layer"

Be more careful in the future when you just call things "bad design" without having a context.

Cheers,

Greg

Thank you all for your replies!!!

I'm really encouraged by your estimates for size, and also the fact that you do agree that it's a reasonable approach to take.
Makes me feel like I'm not alone in my quest, and that, hopefully, I'll be able to solve it.

Unfortunately I don't know exactly how many duplicates I'm going to get, but I would guess that it would constitute aroud 5% of total.
It's important to say that the keys might duplicate, but not whole obejcts ( - a bit similar to postcode (key) vs person (value) scenaio), so I cannot throw any "duplicates" away.

gregoryyoung:

I have looked into doing a Dictionary> structure; in fact as I was looking to implement *multiple* keys,
so I attempeted to use List>> ..

I have attached the code I used for Dictionary approach... The thing was that it seemed quite slow. I suspect it might be because on adding each object I tried to translate the "object" to "keys". What do you think?

In the mean time I have tried to persue my original goal of custom hashtable - I have attached the file with my second attempt to solve it...
It seems reasonably quick to insert, but it seems a bit slow to lookup... Is it not worth persuing?

Cheers again for your answers - looking forward to hearing from you!

Regards,
Dmitri

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
 
namespace DataTypeSpeedTests
{
    public class MKD<K, V>
    {
        //internal readonly List<Dictionary<K, V>> DictionaryList = new List<Dictionary<K, V>>();
        //internal readonly List<Dictionary<K, V>> DictionaryList = new List<Dictionary<K, V>>();
        //internal readonly List<Dictionary<K, Dictionary<K, V>>> ListOfDictionaries = new List<Dictionary<K, Dictionary<K, V>>>();
        //internal readonly Dictionary<int, string> TopLevelInt2String = new Dictionary<int, string>();
        //internal readonly List<K> 
        //internal int TopLevelCount = 0;
 
        //internal readonly Dictionary<string, Dictionary<K, List<V>>> MultiKeyDictionary = new Dictionary<string, Dictionary<K, List<V>>>();
 
        internal readonly List<Dictionary<K, List<V>>> MultiKeyDictionary = new List<Dictionary<K, List<V>>>();
        public readonly List<string> TopLevelKeyNameList = new List<string>();
        public readonly Dictionary<string, int> TopLevelKeyNoList = new Dictionary<string, int>();
        
 
        //internal readonly PropertyInfo[] ValueProperties = typeof(V).GetProperties();
        //internal readonly List<K> TopLevelKeyObjectList = new List<K>();
 
 
        readonly object lockObject = new object();
 
        /// <summary>
        /// Gets or sets the Value.
        /// </summary>
        /// <value>The Value.</value>
        public V Value
        {
            get;
            set;
        }
 
        /// <summary>
        /// Gets or sets the Key.
        /// </summary>
        /// <value>The Key.</value>
        public K Key
        {
            get;
            set;
        }
 
        /// <summary>
        /// Gets the value from Keys and List Index
        /// </summary>
        /// <remarks></remarks>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListPosition">Position In The Value List.</param>
        public V this[string TopLevelDicName, K BottomLevelKey, int ListPosition]
        {
            get
            {
                V value;
                if (TryGetValue(TopLevelDicName, BottomLevelKey, ListPosition, out value))
                    return value;
                else
                    throw new KeyNotFoundException("Not found: " + TopLevelDicName.ToString() + " " + BottomLevelKey.ToString() + " " + ListPosition.ToString());
            }
        }
 
        /// <summary>
        /// Gets the value from Keys and List Index
        /// </summary>
        /// <remarks></remarks>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListPosition">Position In The Value List.</param>
        public V this[int TopLevelDicNo, K BottomLevelKey, int ListPosition]
        {
            get
            {
                V value;
                if (TryGetValue(TopLevelDicNo, BottomLevelKey, ListPosition, out value))
                    return value;
                else
                    throw new KeyNotFoundException("Not found: " + TopLevelDicNo.ToString() + " " + BottomLevelKey.ToString() + " " + ListPosition.ToString());
            }
        }
 
        /// <summary>
        /// Gets the list of values from Keys and List Index
        /// </summary>
        /// <remarks></remarks>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        public List<V> this[string TopLevelDicName, K BottomLevelKey]
        {
            get
            {
                List<V> ListValue;
                if (TryGetValueList(TopLevelDicName, BottomLevelKey, out ListValue))
                    return ListValue;
                else
                    throw new KeyNotFoundException("Not found: " + TopLevelDicName.ToString() + " " + BottomLevelKey.ToString());
            }
        }
 
        /// <summary>
        /// Gets the list of values from Keys and List Index
        /// </summary>
        /// <remarks></remarks>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        public List<V> this[int TopLevelDicNo, K BottomLevelKey]
        {
            get
            {
                List<V> ListValue;
                if (TryGetValueList(TopLevelDicNo, BottomLevelKey, out ListValue))
                    return ListValue;
                else
                    throw new KeyNotFoundException("Not found: " + TopLevelDicNo.ToString() + " " + BottomLevelKey.ToString());
            }
        }
 
        /// <summary>
        /// MKD Class constructor
        /// </summary>
        /// <remarks></remarks>
        /// <param name="Keys">The list of keys to be used; </param>
        /// <param name="newClassValue">An instance of the item - does not need to contain a value; just important to establish the type</param>
        /// <typeparam name="V">
        /// The type of the object that should be stored
        /// </typeparam>
        /// <typeparam name="K">
        /// All the keys must be of the same type (K).
        /// </typeparam>
        public MKD(List<K> Keys, V newClassValue) //string Property2Dictionary
        {
            int i = 0;
            foreach (K key in Keys)
            {
                if (newClassValue.GetType().GetProperty(key.ToString()) != null)
                {
                    try
                    {
                        MultiKeyDictionary.Add(new Dictionary<K, List<V>>());
                        //TopLevelKeyObjectList.Add(key);
                        TopLevelKeyNameList.Add(key.ToString());
                        TopLevelKeyNoList.Add(key.ToString(),i);
                        i++;
                        //TopLevelInt2String.Add(MultiKeyDictionary.Count, key.ToString());
                    }
                    catch (Exception e)
                    {
                        throw e;
                    }
                }
                else
                    throw new System.Exception(key.ToString() + " is not in the " + newClassValue.ToString() + " class; correct the list which is used in the constructor.");
            }
        }
 
        /// <summary>
        /// Get Top Level Dictionary Name By It's "Number"
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        public string GetTopLevelDictionaryName(int TopLevelDicNo)
        {
            return TopLevelKeyNameList[TopLevelDicNo];
        }
 
        /// <summary>
        /// Verify That Top Level Dictionary Exists By It's Name
        /// </summary>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        public bool ContainsTopLevelKey(string TopLevelDicName)
        {
            return TopLevelKeyNameList.Contains(TopLevelDicName);
                //MultiKeyDictionary.ContainsKey(TopLevelDicName);
        }
 
        /// <summary>
        /// Verify That Top Level Dictionary Exists By It's Number
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        public bool ContainsTopLevelKey(uint TopLevelDicNo)
        {
            return (TopLevelDicNo <= TopLevelKeyNameList.Count);
                //MultiKeyDictionary.ContainsKey(TopLevelKeyNameList[TopLevelDicNo]);
        }
 
        /// <summary>
        /// Verify That Bottom Level Dictionary Exists
        /// </summary>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        public bool ContainsBottomLevelKey(string TopLevelDicName, K key)
        {
            lock (lockObject)
            {
                if (ContainsTopLevelKey(TopLevelDicName)) //MultiKeyDictionary.ContainsKey(TopLevelDicName)
                {
                    if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].ContainsKey(key))
                    {
                        //return true; -- return at the end to unlock the object
                    }
                    else
                        return false;
                }
                else
                    return false;
            }
            return true;
        }
 
        /// <summary>
        /// Verify That Bottom Level Dictionary Exists
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        public bool ContainsBottomLevelKey(int TopLevelDicNo, K key)
        {
            return ContainsBottomLevelKey(TopLevelKeyNameList[TopLevelDicNo], key);
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value
        /// </summary>
        /// <remarks>
        /// It's a bit more efficient than other override alternatives.
        /// </remarks>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="value">The Value (object).</param>
        public bool ContainsValue(string TopLevelDicName, K key, V value)
        {
            lock (lockObject)
            {
                if (ContainsTopLevelKey(TopLevelDicName))
                {
                    if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].ContainsKey(key))
                    {
                        if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]][key].Contains(value))
                        {
                            //return true; -- return at the end to unlock the object
                        }
                        else
                            return false;
                    }
                    else
                    {
                        return false;
                    }
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="value">The Value (object).</param>
        public bool ContainsValue(int TopLevelDicNo, K key, V value)
        {
            return ContainsValue(TopLevelKeyNameList[TopLevelDicNo], key, value);
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value
        /// </summary>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="value">The Value (object).</param>
        public bool ContainsValue(string TopLevelDicName, V value)
        {
            lock (lockObject)
            {
                if (ContainsTopLevelKey(TopLevelDicName))
                {
                    foreach (KeyValuePair<K, List<V>> kvp in MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]])
                    {
                        if (kvp.Value.Contains(value))
                            //return true; -- break instead and unlock the object...
                            break;
                    }
                    return false;
                }
                else
                    return false;
            }
            return true; // unreachable code is a fib, because of the break in the foreach loop.
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="value">The Value (object).</param>
        public bool ContainsValue(int TopLevelDicNo, V value)
        {
            return ContainsValue(TopLevelKeyNameList[TopLevelDicNo], value);
        }
 
        
 
        /// <summary>
        /// Verify That Dictionary Contains Value; Get First Value - And The List Of Values.
        /// </summary>
        /// <remarks>
        /// Hopefully the overhead of doing this would not be too high...
        /// </remarks>
        /// <returns>The Count Of Values In The List</returns>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="value">(output) - The Value (object).</param>
        /// <param name="ListVal">(output) - The List Of Values (object list).</param>
        public uint TryGetValueAndValueList(string TopLevelDicName, K key, out V value, out List<V> ListVal)
        {
            lock (lockObject)
            {
                if (ContainsTopLevelKey(TopLevelDicName))//.TryGetValue(TopLevelDicName, out Ds)
                {
                    if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].ContainsKey(key))
                    {
                        if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].TryGetValue(key, out ListVal))
                        {
                            value = ListVal[0];
                            return (uint)ListVal.Count;
                        }
                        else
                        {
                            ListVal = default(List<V>);
                            value = default(V);
                            return 0;
                        }
                    }
                    else
                    {
                        ListVal = default(List<V>);
                        value = default(V);
                        return 0;
                    }
                }
                else
                {
                    ListVal = default(List<V>);
                    value = default(V);
                    return 0;
                }
            }
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value; Get First Value - And The List Of Values.
        /// </summary>
        /// <remarks>
        /// Hopefully the overhead of doing this would not be too high...
        /// </remarks>
        /// <returns>The Count Of Values In The List</returns>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="value">(output) - The Value (object).</param>
        /// <param name="ListVal">(output) - The List Of Values (object list).</param>
        public uint TryGetValueAndValueList(int TopLevelDicNo, K key, out V value, out List<V> ListVal)
        {
            lock (lockObject)
            {
                if (TopLevelDicNo >= 0 && TopLevelDicNo <= TopLevelKeyNameList.Count)
                {
                    if (MultiKeyDictionary[TopLevelDicNo].ContainsKey(key))
                    {
                        if (MultiKeyDictionary[TopLevelDicNo].TryGetValue(key, out ListVal))
                        {
                            value = ListVal[0];
                            return (uint)ListVal.Count;
                        }
                        else
                        {
                            ListVal = default(List<V>);
                            value = default(V);
                            return 0;
                        }
                    }
                    else
                    {
                        ListVal = default(List<V>);
                        value = default(V);
                        return 0;
                    }
                }
                else
                {
                    ListVal = default(List<V>);
                    value = default(V);
                    return 0;
                }
            }
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value and Get Value.
        /// </summary>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListPosition">Position In The Value List.</param>
        /// <param name="value">(output) - The Value (object).</param>
        public bool TryGetValue(string TopLevelDicName, K key, int ListPosition, out V value)
        {
            lock (lockObject)
            {
                if (ListPosition >= 0 && ContainsTopLevelKey(TopLevelDicName))//.TryGetValue(TopLevelDicName, out Ds)
                {
                    if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].ContainsKey(key))
                    {
                        if (ListPosition <= MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]][key].Count) // .TryGetValue(key, out ListVal))
                        {
                            value = MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]][key][ListPosition];
                            return true; // return true at the end to unlock object???
                        }
                        else
                        {
                            value = default(V);
                            return false;
                        }
                    }
                    else
                    {
                        value = default(V);
                        return false;
                    }
                }
                else
                {
                    value = default(V);
                    return false;
                }
            }
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value and Get The Value.
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListPosition">Position In The Value List.</param>
        /// <param name="value">(output) - The Value (object).</param>
        public bool TryGetValue(int TopLevelDicNo, K key, int ListPosition, out V value)
        {
            lock (lockObject)
            {
                if (ListPosition >= 0 && ListPosition <= TopLevelKeyNameList.Count)//.TryGetValue(TopLevelDicName, out Ds)
                {
                    if (MultiKeyDictionary[TopLevelDicNo].ContainsKey(key))
                    {
                        if (ListPosition <= MultiKeyDictionary[TopLevelDicNo][key].Count) // .TryGetValue(key, out ListVal))
                        {
                            value = MultiKeyDictionary[TopLevelDicNo][key][ListPosition];
                            return true; // return true at the end to unlock object???
                        }
                        else
                        {
                            value = default(V);
                            return false;
                        }
                    }
                    else
                    {
                        value = default(V);
                        return false;
                    }
                }
                else
                {
                    value = default(V);
                    return false;
                }
            }
            //return TryGetValue(TopLevelKeyNameList[TopLevelDicNo], key, ListPosition, out  value);
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value and Get First Value.
        /// </summary>
        /// <remarks>
        /// Major Weakness - there may be more elements in the list...
        /// </remarks>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListPosition">Position In The Value List.</param>
        /// <param name="value">(output) - The Value (object).</param>
        public bool TryGetFirstValue(string TopLevelDicName, K key, out V value)
        {
            return TryGetValue(TopLevelDicName, key, 0, out value);
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value and Get Value List.
        /// </summary>
        /// <param name="TopLevelDicName">Top Level Dictionary's Name</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListVal">(output) - The Value List (List Of Value Objects).</param>
        public bool TryGetValueList(string TopLevelDicName, K key, out List<V> ListVal)
        {
            lock (lockObject)
            {
                if (ContainsTopLevelKey(TopLevelDicName))//.TryGetValue(TopLevelDicName, out Ds)
                {
                    if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].ContainsKey(key))
                    {
                        if (MultiKeyDictionary[TopLevelKeyNoList[TopLevelDicName]].TryGetValue(key, out ListVal))
                        {
                            return true; // return true at the end to unlock object???
                        }
                        else
                        {
                            ListVal = default(List<V>);
                            return false;
                        }
                    }
                    else
                    {
                        ListVal = default(List<V>);
                        return false;
                    }
                }
                else
                {
                    ListVal = default(List<V>);
                    return false;
                }
            }
        }
 
        /// <summary>
        /// Verify That Dictionary Contains Value and Get Value List.
        /// </summary>
        /// <param name="TopLevelDicNo">Top Level Dictionary's Number</param>
        /// <param name="key">Bottom Level Key</param>
        /// <param name="ListVal">(output) - The Value List (List Of Value Objects).</param>
        public bool TryGetValueList(int TopLevelDicNo, K key, out List<V> ListVal)
        {
            lock (lockObject)
            {
                if (TopLevelDicNo >= 0 && TopLevelDicNo <= TopLevelKeyNameList.Count)
                {
                    if (MultiKeyDictionary[TopLevelDicNo].ContainsKey(key))
                    {
                        if (MultiKeyDictionary[TopLevelDicNo].TryGetValue(key, out ListVal))
                        {
                            return true; // return true at the end to unlock object???
                        }
                        else
                        {
                            ListVal = default(List<V>);
                            return false;
                        }
                    }
                    else
                    {
                        ListVal = default(List<V>);
                        return false;
                    }
                }
                else
                {
                    ListVal = default(List<V>);
                    return false;
                }
            }
        }
 
        /// <summary>
        /// Add Value To All Dictionaries.
        /// </summary>
        /// <param name="value">The Value (Of Type V) To Be Added.</param>
        public void AddItem(V value)
        {
            lock (lockObject)
            {
                for (int i = 0; i < TopLevelKeyNameList.Count; i++)
                {
                    List<V> ListValues;
                    K KeyFromValue = default(K);
                    object o = value.GetType().GetProperty(TopLevelKeyNameList[i]).GetValue(value, null);
                    if (o != null)
                    {
                        KeyFromValue = (K)o;
                        if (MultiKeyDictionary[i].TryGetValue(KeyFromValue, out ListValues)) //ContainsKey(KeyFromValue))
                        {
                            ListValues.Add(value);
                        }
                        else
                        {
                            ListValues = new List<V>();
                            ListValues.Add(value);
                            MultiKeyDictionary[i].Add(KeyFromValue, ListValues);
                        }
                    }
                }
            }
        }
 
 
 
        /// <summary>
        /// Add Value To All Dictionaries.
        /// </summary>
        /// <param name="value">The Value (Of Type V) To Be Added.</param>
        public void AddItemNew(V value)
        {
            for (int i = 0; i < TopLevelKeyNameList.Count; i++)
            {
                try
                {
                    K KeyFromValue = (K)value.GetType().GetProperty(TopLevelKeyNameList[i]).GetValue(value, null);
                    try
                    {
                        MultiKeyDictionary[i].Add(KeyFromValue, new List<V>(new V[]{value}));
                    }
                    catch
                    {
                        // the key already exists...
                        try
                        {
                            MultiKeyDictionary[i][KeyFromValue].Add(value);
                        }
                        catch
                        {
                            throw;
                        }
                    }
                }
                catch
                {
                    // no object in value, ignore...
                }
            }
        }
 
 
 
 
        /// <summary>
        /// Remove Value From All Dictionaries.
        /// </summary>
        /// <param name="value">The Value (Of Type V) To Be Removed.</param>
        public void RemoveItem(V value)
        {
            lock (lockObject)
            {
                for (int i = 0; i < TopLevelKeyNameList.Count; i++)
                {
                    List<V> ListValues = default(List<V>);
                    K KeyFromValue = default(K);
                    object o = value.GetType().GetProperty(TopLevelKeyNameList[i]).GetValue(value, null);
                    if (o != null)
                    {
                        KeyFromValue = (K)o;
                        if (MultiKeyDictionary[i].TryGetValue(KeyFromValue, out ListValues)) //ContainsKey(KeyFromValue))
                        {
                            int cnt_before_removing = ListValues.Count;
                            ListValues.Remove(value); // todo - need to check that removing the value in THIS list does not remove it in OTHER lists.
                            // if this was the only value in this dictionary, remove key from dictionary too.
                            if (cnt_before_removing == 1)
                                MultiKeyDictionary[i].Remove(KeyFromValue);
                        }
                        else
                        {
                            //do nothing...
                        }
                    }
                }
                value = default(V);
            }
        }
 
 
        /// <summary>
        /// Removes All Keys And Values From MKD Dictionary.
        /// </summary>
        public void Clear()
        {
            lock (lockObject) 
                MultiKeyDictionary.Clear();
        }
 
 
 
    }
}

Select allOpen in new window

CustomHashtable.txt

..I have noticed that the formatting went a bit wrong once I submitted the post..

The attached attempt covers List > Dictionary > List

Thanks,
  Dmitri

Hey Greg,

Well, to be honest I am not hugely experienced on this front (and most certainly not comparing to some guys here).

But this is why I'm here - and experience is really what gives *you* the edge (and might explains some questions you had)..

I used reflection to map object fields to keys, which I agree is not really necessary.

I took the object locking idea from the article which did a similar job  
( http://www.codeproject.com/KB/recipes/multikey-dictionary.aspx ), but I can also see it's not needed.

Thank you for time, and I'll give it a go soon...

Cheers,
  Dmitri

Hi Greg,

Well, I believe you've got it.. I updated the code very very slightly - for the benefit of others who might read this..

I will try it a bit more before I close up the post, but I really appreciate what you did.

Thanks again,
  Dmitri

    public class MKD2<T, V>
    {
        private readonly Dictionary<T, List<V>> dictionary;
 
        public MKD2() { dictionary = new Dictionary<T, List<V>>(); }
 
        public void Add(T key, V item) 
        {
           List<V> entry;
           if(!dictionary.TryGetValue(key, out entry)) 
           { 
               entry = new List<V>();
               dictionary.Add(key, entry);
           }
           entry.Add(item);
        }
 
        public void Remove(T key) 
        {
           dictionary.Remove(key);
        }
 
        public void Clear() 
        {
           dictionary.Clear();
        }
 
        public void Remove(T key, V value) 
        {
           List<V> entry;
           if(dictionary.TryGetValue(key, out entry)) { 
                entry.Remove(value);
           }
        }
 
        public IEnumerable<V> Get(T key) 
        {
           List<V> entry;
           if(!dictionary.TryGetValue(key, out entry)) throw new Exception("Bad key");
           return entry; //might want to use .ToArray() here in multi threaded code
        }
    }

Select allOpen in new window

no worries, sorry for any typos I just typed it in here.

**** Brilliant ****

I have successfully tested the structure and it's quick for simple and even reasonably complex objects, both for storing, enumerating (hurray!).

Testing conditions: I have roughly 1 gb of free memory.

Using simple objects I managed to store up to 5.9 mil (with one key dymention).
Using fairly large objects I managed to store up to 1.5 mil (with one key dymention).
Using fairly large objects, with 10 key dymentions I managed to store up to 900 thousand.

Times it took:
Adding small obejects 1 dim, 1 mil - next to no time (less than 2 seconds)
Adding Large objects 1 dim, 1.5 mil - 17 seconds
Adding Large objects 2 dim, 1.5 mil - 28 seconds
Adding Large objects 10 dim - 1min 14 seconds

    public class MKD2<K, V>
    {
        private readonly Dictionary<K, List<V>>[] dictionary;
 
        public byte DymentionCount
        {
            get;
            set;
        }
 
        public MKD2() 
        {
            DymentionCount = 1;
            dictionary = new Dictionary<K, List<V>>[1];
            dictionary[0] = new Dictionary<K, List<V>>(); 
        }
 
        public MKD2(byte dymentionCount)
        {
            if (dymentionCount == 0) dymentionCount = 1;
            DymentionCount = dymentionCount;
            dictionary = new Dictionary<K, List<V>>[DymentionCount];
            for (int i = 0; i < DymentionCount; i++)
            {
                dictionary[i] = new Dictionary<K, List<V>>();
            }
        }
 
        public int GetDimentionLength(byte dymention)
        {
            if (dictionary[dymention] == null)
                return 0;
            else
                return dictionary[dymention].Count;
        }
 
        public void Add(K key, V item)
        {
            List<V> entry;
            if (!dictionary[0].TryGetValue(key, out entry))
            {
                entry = new List<V>();
                dictionary[0].Add(key, entry);
            }
            entry.Add(item);
        }
 
        public void Add(K key, V item, byte dymention)
        {
            List<V> entry;
            if (!dictionary[dymention].TryGetValue(key, out entry))
            {
                entry = new List<V>();
                dictionary[dymention].Add(key, entry);
            }
            entry.Add(item);
        }
 
        public void Remove(K key)
        {
            dictionary[0].Remove(key);
        }
 
        public void Remove(K key, byte dymention)
        {
            dictionary[dymention].Remove(key);
        }
 
        public void Clear()
        {
            dictionary[0].Clear();
        }
 
        public void Clear(byte dymention)
        {
            dictionary[dymention].Clear();
        }
 
        public void Remove(K key, V value)
        {
            List<V> entry;
            if (dictionary[0].TryGetValue(key, out entry))
            {
                entry.Remove(value);
            }
        }
 
        public void Remove(K key, V value, byte dymention)
        {
            List<V> entry;
            if (dictionary[dymention].TryGetValue(key, out entry))
            {
                entry.Remove(value);
            }
        }
 
        public List<V> Get(K key) //IEnumerable<V>
        {
            List<V> entry;
            if (!dictionary[0].TryGetValue(key, out entry)) throw new Exception("Bad key");
            return entry; //might want to use .ToArray() here in multi threaded code
        }
 
        public List<V> Get(K key, byte dymention) //IEnumerable<V>
        {
            List<V> entry;
            if (!dictionary[dymention].TryGetValue(key, out entry)) throw new Exception("Bad key");
            return entry; //might want to use .ToArray() here in multi threaded code
        }
 
        public List<V> GetFlatDymentionValueList(byte dymention)
        {
            List<V> full_list = new List<V>();
            foreach (KeyValuePair<K,List<V>> kvp in dictionary[dymention])
	        {
                full_list.AddRange(kvp.Value);
	        }
            return full_list;
        }
 
        public List<K> GetFlatDimentionKeyList(byte dymention)
        {
            List<K> full_list = new List<K>();
            foreach (KeyValuePair<K, List<V>> kvp in dictionary[dymention])
            {
                full_list.Add(kvp.Key);
            }
            return full_list;
        }
    }

Select allOpen in new window

..However one nagging problem is removing items from the collection; the memory doesn't appear to clear when I:
1) Add items to the collection (- a good 1.5 million)
2) Remove items;
3) Add some more items.

Debugging through the steps I can see hash collection is empty. So why doesn't the memory get released?

I have attached the code I used to remove the elelments...

Thanks,
  Dmitri

            foreach (KeyValuePair<long, List<ActivityDetails_HashedLib>> item in cht.GetKVPList(0))
            {
                foreach(ActivityDetails_HashedLib hl in item.Value)
                {
                    cht.Remove(item.Key, hl, 0);
                }
                cht.Remove(item.Key);
            }

Select allOpen in new window

This code should just be


            foreach (KeyValuePair<long, List<ActivityDetails_HashedLib>> item in cht.GetKVPList(0))
            {
                cht.Remove(item.Key);
            }

No?


How are you measuring that the "memory was not freed"?

Cheers,

Greg

Yes, I tried that first of all, but it didn't work at the time..

It was because I used foreach instead of a for loop. I now get a list of keys first and iterate - and for loop works just fine. :)

Cheers,
  Dmitri

Glad it worked for you.

Good luck.

Greg