Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Custom Hashtable C#

Posted on 2009-04-29
21
Medium Priority
?
3,690 Views
Last Modified: 2013-12-17
Hello Experts!

I would like to reasonably quickly lookup objects by NON-UNIQUE values in a collection.

Naturally I tried at Hashtables and Dictionaries, but because they rely on key's uniqueness, I couldn't really use them.

&By the way, if you know an alternative way, I don't mind what "collection" to use.  Any collection that would be quick for storing extra large collection (1 million objects), and looking them up. The type of each VALUE to lookup is long.

Hence the idea of custom Hashtable..  I thought of implementing a custom hashable solution which would in effect use chaining and not rehashing (http://en.wikipedia.org/wiki/Hash_table)

I wanted to ask if you know of a good (fast!?) implementation of this, or if not, if you could look at my code and suggest how it can be improved/completed please?

If you think it's a good idea, how would you implement the rest?

It implements just one nonunique key lookup (but there may be more).



Thank you,
Dmitri

// ************************************************************
//  This is just a section which is supposed to generate the "CustomHash" collection.
//
// The general idea is that you'd follow this path to get back an object:
// HashListHeader  ->  Bucket_keys -> BucketObjects
// By the way, I have been using the following to test the speed of this block:
/*
            public static System.Diagnostics.Stopwatch s = new System.Diagnostics.Stopwatch();
            s.Reset();
            s.Start();
            for (int i = 0; i < 10; i++)
            {
                HashListOfLists(1000000);
                
            }
            s.Stop();
            textBox1.Text += ("result = " + s.Elapsed + Environment.NewLine);
*/
// ************************************************************
 
        // 4294967298 - the value required to get hash int from hash long  (you can also get it by maxlong / maxint!)
        // 7700 - trial and error figure - seems to provide optimum balance for hash collisions, between the length of collision list and length of hash list
        static long long2int_denominator = (4294967298 * 7700);
 
        public static int GetNewArraySize(int OldSize, int nextIndex)
        {
            double incrementer = 0.0;
            if (OldSize < 100) incrementer = 2;
            else incrementer = 1.5;
 
            int newSize = (int)((double)OldSize + ((double)OldSize * incrementer));
 
            if (nextIndex >= newSize)
            {
                newSize = (int)((double)nextIndex + ((double)nextIndex * incrementer));
            }
            return newSize;
        }
 
        public static void HashListOfLists(int new_terations)
        {
            int[] HashListHeader = new int[278894];  // the size of this would never go higher than 278894
                                                                               // because 2147483647 (aka int!) / 7700 = 278893
                                                                               // see long2int_denominator defenition...
            List<List<long>> Bucket_keys = new List<List<long>>();
            List<List<string>> Bucket_objects = new List<List<string>>();   // to be replaced with the object...
            
            //populate the list with new lists.
            int while_loop1 = 0;
            while (while_loop1 < new_terations)
            {
                Bucket_keys.Add(new List<long>());
                Bucket_objects.Add(new List<string>());
                while_loop1++;
            }
 
            Random r = new Random();
            int current_list;           // create some random stuff to test this
            long value;
            int int_hash_value;
            for (int i = 0; i < new_terations; i++)
            {
                value = (long)((r.NextDouble() * 2.0 - 1.0) * long.MaxValue);  // create some random value to test
                int_hash_value = (int)(Math.Abs(value) / long2int_denominator); // get the hashed value ready to be inserted into the hash list header.
 
                current_list = HashListHeader[int_hash_value];
                if (current_list == null || current_list == 0)
                {
                    HashListHeader[int_hash_value] = i;
                    current_list = i;
                }
                Bucket_objects[current_list].Add(i.ToString());
                Bucket_keys[current_list].Add(value);
            }
        }

Open in new window

0
Comment
Question by:CallConnection
  • 9
  • 8
  • 3
  • +1
21 Comments
 
LVL 26

Expert Comment

by:Anurag Thakur
ID: 24259231
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
0
 

Author Comment

by:CallConnection
ID: 24259282
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?
0
 
LVL 26

Expert Comment

by:Anurag Thakur
ID: 24259392
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
0
Free recovery tool for Microsoft Active Directory

Veeam Explorer for Microsoft Active Directory provides fast and reliable object-level recovery for Active Directory from a single-pass, agentless backup or storage snapshot — without the need to restore an entire virtual machine or use third-party tools.

 

Author Comment

by:CallConnection
ID: 24259450
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?
0
 
LVL 6

Expert Comment

by:alex_paven
ID: 24260152
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).
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24262024
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
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24262106
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.
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24262473
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.
0
 
LVL 26

Expert Comment

by:Anurag Thakur
ID: 24264280
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
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24274942
"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
0
 

Author Comment

by:CallConnection
ID: 24315921
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();
        }
 
 
 
    }
}

Open in new window

CustomHashtable.txt
0
 

Author Comment

by:CallConnection
ID: 24315959
..I have noticed that the formatting went a bit wrong once I submitted the post..

The attached attempt covers List > Dictionary > List

Thanks,
  Dmitri
0
 
LVL 37

Accepted Solution

by:
gregoryyoung earned 2000 total points
ID: 24316210
I am not suprised wtf are you using reflection in it?

Why is this a responsibility of your MKD at all? Why is your MKD handling locking etc? This is the responsibility of other code.

Start simple ... profile the add/get of a "MKD" using a Dictionary<T, List<V>> I will even write it for you. (included). Filling it out should not take long.


Cheers,

Greg
public MKD<T, V>
   private readonly Dictionary<T, List<V>> dictionary;
 
   public MKD() { dictionary = new Dictionary<T, List<V>>(); }
 
   public Add(T key, V item) {
       List<V> entry;
       if(!dictionary.TryGetValue(key, out entry)) { 
           entry = new List<V>();
           dictionary.Add(entry);
       }
       entry.Add(entry);
   }
 
   public void Remove(T key) {
       dictionary.Remove(key);
   }
 
   public void Clear() {
       dictionary.Clear();
   }
 
   public void Remove(T key, K 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
   }
}

Open in new window

0
 

Author Comment

by:CallConnection
ID: 24318079
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
0
 

Author Comment

by:CallConnection
ID: 24319562
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
        }
    }

Open in new window

0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24319636
no worries, sorry for any typos I just typed it in here.
0
 

Author Comment

by:CallConnection
ID: 24327002
**** 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;
        }
    }

Open in new window

0
 

Author Comment

by:CallConnection
ID: 24327085
..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);
            }

Open in new window

0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24327632
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
0
 

Author Comment

by:CallConnection
ID: 24336210
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
0
 
LVL 37

Expert Comment

by:gregoryyoung
ID: 24336968
Glad it worked for you.

Good luck.

Greg
0

Featured Post

Become an Android App Developer

Ready to kick start your career in 2018? Learn how to build an Android app in January’s Course of the Month and open the door to new opportunities.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.
This article shows how to deploy dynamic backgrounds to computers depending on the aspect ratio of display
The viewer will learn how to implement Singleton Design Pattern in Java.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question