Introduction to hashtable

Hashtable Is a non generic collection , Therefore, boxing and unpacking operations usually occur when retrieving and storing value types . 

 

 

When adding an element to Hashtable when , The element will be put into the bucket according to the hash code of the key , Because it is a hash algorithm, there will be a hash function that can generate the same hash code for two different keys , The subsequent search of the key will use the hash code of the key to search only in a specific bucket , This will greatly reduce the number of key comparisons required to find an element .

 

Hashtable The loading factor of determines the element and Hashtable The maximum ratio of the number of elements that can be owned . The smaller the load factor , The faster the average search speed , But the memory consumption also increases . Default load factor 0.72 Usually provides the best balance between speed and size . When creating a Hashtable when , You can also specify other loading factors .

 

Total elements / Hashtable The number of elements you can have = Load factor  

 

Direction Hashtable When adding elements ,Hashtable The actual loading factor of will increase . When the actual loading factor reaches the specified loading factor ,Hashtable The number of buckets in is automatically increased to greater than the current Hashtable Minimum prime number twice the number of buckets .

 

During capacity expansion, all data needs to be hashed again . although Hash have O(1) Data retrieval efficiency , But it usually costs a lot of space , Is to exchange space for time . therefore Hashtable Suitable for frequent reading operations , Operation types with few write operations .

 

 

 

Code 1 、

    

 

Copy code

 static void Main(string[] args)

 

        {

 

            Hashtable hashtb = new Hashtable();

 

            hashtb.Add(1, "aa");

 

            hashtb.Add(2, "bb");

 

            hashtb.Add(3, "cc");

 

            hashtb.Add(4, "dd"); 

 

            

 

            foreach (DictionaryEntry item in hashtb)

 

            {

 

                Console.WriteLine(item.Value);

 

                item.Value = "ee"; 

 

            }

 

            Console.Read();

 

        }

 

Copy code

 

 

 

 

Compilation error ：item by foreach Iteration variables for , Its members cannot be modified .

 

 

 

reason ： If you run foreach The processing statement attempts to modify the iteration variable value , Or take the variable value as ref Parameter or out Parameter passing , Then compilation errors will occur , The iteration variable is equivalent to a local read-only variable .

 

 

 

Code 2 、

item.Value = "ee"; Change to hashtb[item.Key] = "ee";

 

Operation error reporting ： Set modified ; Enumeration may not be possible .

 

 

 

reason ：.NET Framework Provide enumerators as a simple way to iterate through a collection . Enumerators only read data from the collection , Cannot be used to modify the underlying collection .

 

foreach Statement is used to iterate through a collection , To get the information you need , But it cannot be used to add or remove items from the source collection , Otherwise, unpredictable side effects may occur . If you need to add or remove items from the source collection , Please use for loop .

 

Code three 、

          

 

Copy code

 Thread tr1 = new Thread(new ThreadStart(() =>

 

            {

 

                foreach (DictionaryEntry item in hashtb)

 

                {

 

                    Console.WriteLine(item.Value);

 

                }

 

            }));

 

            tr1.Start();

 

            Thread tr2 = new Thread(new ThreadStart(() =>

 

            {

 

                for (int i = 1; i < 4; i++)

 

                {

 

                    hashtb[i] = "ee";

 

                    Console.WriteLine(hashtb[i]);

 

                }

 

               

 

            }));

 

            tr2.Start();

 

Copy code

 

 

 

 

Threads tr1 To read hashtable, Threads tr2 be used for foreach To enumerate modifications hashtable,

 

Runtime error ： Set modified ; Enumeration may not be possible .

 

Code four 、

       

 

Copy code

  // Read

 

         Thread tr1 = new Thread(new ThreadStart(() =>

 

            {

 

                for (int i = 1; i <= 4; i++)

 

                {

 

                    Console.WriteLine(hashtb[i]);

 

                }

 

            }));

 

            tr1.Start();

 

         Thread tr2 = new Thread(new ThreadStart(() =>

 

            {

 

                for (int i = 1; i <= 4; i++)

 

                {

 

                    Console.WriteLine(hashtb[i]);

 

                }

 

            }));

 

            tr2.Start();

 

 

 

 

 

         // modify

 

            Thread tr3 = new Thread(new ThreadStart(() =>

 

            {

 

                for (int i = 1; i <= 4; i++)

 

                {

 

                    hashtb[i] = "ee";

 

                }

 

               

 

            }));

 

            tr3.Start();

 

Copy code

 

 

 

 

 

 

Running results ： normal

 

explain ：Hashtable It's thread safe , Can be used by multiple reader threads and one write thread . When multithreading , If only one thread writes （ to update ） operation , It is thread safe , This allows unlocked reads （ If the writer is serialized to Hashtable）

 

Code five 、

 

 

Copy code

         Thread tr1 = new Thread(new ThreadStart(() =>

 

            {

 

                lock (hashtb)

 

                {

 

                    foreach (DictionaryEntry item in hashtb)

 

                    {

 

                        Console.WriteLine(item.Value);

 

                    }

 

                }

 

            }));

 

            tr1.Start();

 

            Thread tr2 = new Thread(new ThreadStart(() =>

 

            {

 

                lock (hashtb)

 

                {

 

                    for (int i = 1; i <= 4; i++)

 

                    {

 

                        hashtb[i] = "ee";

 

                    }

 

                }

 

               

 

            }));

 

            tr2.Start();

Copy code

 

 

 

 

  Running results ： normal

 

explain ： Because both threads are added lock (hashtb) So it's thread safe . Enumerating a collection from beginning to end is not a thread safe process in essence . Even if a collection is synchronized , Other threads can still modify the collection , This will cause the enumerator to throw an exception . To ensure thread safety during enumeration , You can lock a collection throughout the enumeration process , Or catch exceptions caused by changes made by other threads .

 

Hashtable Thread safe methods provided

Hashtable Of Synchronized Static methods provide thread safe instances , as follows ：

 

Hashtable ht = Hashtable.Synchronized(new Hashtable());

 

The internal implementation is as follows ：

 

 

 

Copy code

public override void Add(object key, object value)

{

    lock (this._table.SyncRoot)

    {

    　　this._table.Add(key, value);

    }

}

 

Copy code

 

 

 

 

 

 

Output as input

because hashtable The interior is disordered , So the output is not necessarily ,hashtable The mechanism of getting data is not understood . According to the following code, you can realize first in, first out .

 

By controlling ArrayList Inside keys To control hashtable Output , You can also use it SortedDictionary and SortedList Implement sort collection .

 

Copy code

public class NoSortHashtable : Hashtable

     {

        private ArrayList keys = new ArrayList();

 

        public NoSortHashtable()

         {

        }

        

 

        public override void Add(object key, object value)

         {

            base.Add (key, value);

            keys.Add (key);

        }

 

        public override ICollection Keys

         {

            get

             {

                return keys;

            }

        }

 

        public override void Clear()

         {

            base.Clear ();

            keys.Clear ();

        }

 

        public override void Remove(object key)

         {

            base.Remove (key);

            keys.Remove (key);

        }