C \ # 데이터 구조 - dictionary 구현

대신 이 쓴 을 보면 Dictionary 의 내부 실현 에 대해 명확 한 이 해 를 가지 게 되 었 지만 종이 에 있 는 감각 이 얕 고 프로그래머 로 서 스스로 코드 를 디 버 깅 하 는 것 이 기억 에 남 습 니 다. 이 를 위해 C \ # 의 Dictionary 소스 코드 를 복사 합 니 다. 소스 코드 는 보호 등급 의 코드 가 많아 서 직접 실행 할 수 없습니다.다음은 내 가 디 버 깅 에 문제 가 없 는 Dictionary 소스 코드 (일부 코드 는 다시 쓰 지 않 았 음) 를 붙 이 고 공식 호출 인 스 턴 스 를 추가 하여 정지점 디 버 깅 을 편리 하 게 합 니 다.
사전 소스 코드:
using System;
using System.Collections;
using System.Collections.Generic;

namespace StructScript
{
    /// 
    ///               :
    ///                      ,                    ,                    。
    ///   ,              。              :separate chaining(   ) linear probing(     )。
    /// 

    public class DictionaryScript : IDictionary
    {
        protected struct Entry
        {
            public int hashCode;    //31    ,32        ,-1     
            public int next;        //       ,-1    
            public TKey key;        // 
            public TValue value;    // 
        }

        protected int[] buckets;//  hash  ,            
        protected Entry[] entries;//    ,           
        protected int count;//    
        protected int freeList;//     
        protected int freeCount;//        
        protected IEqualityComparer comparer;//         
        protected KeyCollection keys;//   
        protected ValueCollection values;//   
        protected const int MaxPrimeArrayLength = 0x7FEFFFFD;
        //      
        protected static readonly int[] primes = {
            3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
            1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
            17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
            187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
            1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

        //         
        public DictionaryScript() : this(0, null) { }

        public DictionaryScript(int capacity) : this(capacity, null) { }

        public DictionaryScript(int capacity, IEqualityComparer comparer)
        {
            if (capacity < 0)
            {
                throw new ArgumentNullException();
            }
            if (capacity > 0)
            {
                Initialize(capacity);
            }
            this.comparer = comparer == null ? EqualityComparer.Default : comparer;
        }

        /// 
        ///        M         ,                       (0 M-1)     
        ///                         。      ,0 M-1                  
        ///      。           M   ,       k,  k  M   
        ///   M      ,                 ,              。
        /// 
        private void Initialize(int capacity)
        {
            //             ,            
            int size = GetPrime(capacity);
            buckets = new int[size];
            for (int i = 0; i < buckets.Length; i++)
            {
                buckets[i] = -1;
            }
            entries = new Entry[size];
            freeList = -1;
        }

        /// 
        ///              ,            
        /// 
        public int GetPrime(int min)
        {
            if (min < 0)
                throw new ArgumentException();

            for (int i = 0; i < primes.Length; i++)
            {
                int prime = primes[i];
                if (prime >= min) return prime;
            }

            //         
            for (int i = (min | 1); i < Int32.MaxValue; i += 2)
            {
                if (IsPrime(i) && ((i - 1) % 101 != 0))
                    return i;
            }
            return min;
        }

        /// 
        ///      
        /// 
        private bool IsPrime(int candidate)
        {
            if ((candidate & 1) != 0)
            {
                int limit = (int)Math.Sqrt(candidate);
                for (int divisor = 3; divisor <= limit; divisor += 2)
                {
                    if ((candidate % divisor) == 0)
                        return false;
                }
                return true;
            }
            return (candidate == 2);
        }

        /// 
        ///   
        /// 
        private int ExpandPrime(int oldSize)
        {
            int newSize = 2 * oldSize;
            if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
            {
                return MaxPrimeArrayLength;
            }
            return GetPrime(newSize);
        }

        public TValue this[TKey key]
        {
            get
            {
                int i = FindEntry(key);
                if (i >= 0)
                {
                    return entries[i].value;
                }
                else
                {
                    throw new KeyNotFoundException();
                }
            }
            set
            {
                Insert(key, value, false);
            }
        }

        public int Count
        {
            get
            {
                return count;
            }
        }

        public KeyCollection Keys
        {
            get
            {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            }
        }

        public ValueCollection Values
        {
            get
            {
                if (values == null) values = new ValueCollection(this);
                return values;
            }
        }

        IEnumerable IDictionary.Keys
        {
            get
            {
                if (keys == null) keys = new KeyCollection(this);
                return keys;
            }
        }

        IEnumerable IDictionary.Values
        {
            get
            {
                if (values == null) values = new ValueCollection(this);
                return values;
            }
        }

        public void Add(KeyValuePair item)
        {
            Add(item.Key, item.Value);
        }

        public void Add(TKey key, TValue value)
        {
            Insert(key, value, true);
        }

        private void Insert(TKey key, TValue value, bool add)
        {
            //key    ,value    
            if (key == null)
            {
                throw new ArgumentNullException();
            }
            if (buckets == null)
            {
                Initialize(0);
            }
            int collisionCount = 0;
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            // HashCode           
            int bucketIndex = hashCode % buckets.Length;
            //   hash    
            //       bucketIndex    0,  buckets         ,    ,      
            for (int i = buckets[bucketIndex]; i >= 0; i = entries[i].next)
            {
                //     hash         hash   ,     key      ,    ,key    ,    
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                {
                    if (add)
                    {
                        throw new ArgumentException();
                    }
                    entries[i].value = value;
                    return;
                }
                collisionCount++;
            }
            //    
            int index;
            //          0,FreeList     ,               FreeList        ,   FreeCount 1
            if (freeCount > 0)
            {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else
            {
                //      ,   
                if (count == entries.Length)
                {
                    Resize();
                    bucketIndex = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
            entries[index].hashCode = hashCode;
            //     next          
            entries[index].next = buckets[bucketIndex];
            entries[index].key = key;
            entries[index].value = value;
            //         
            buckets[bucketIndex] = index;

            //            ,    Hash 
            if (collisionCount > 100 && IsEqualityComparer(comparer))
            {
                comparer = EqualityComparer.Default;
                Resize(entries.Length, true);
            }
        }

        private bool IsEqualityComparer(object comparer)
        {
            return (comparer == null || comparer == EqualityComparer.Default);
        }

        /// 
        ///     
        /// 
        private void Resize()
        {
            Resize(ExpandPrime(count), false);
        }

        private void Resize(int newSize, bool forceNewHashCodes)
        {
            int[] newBuckets = new int[newSize];
            for (int i = 0; i < newBuckets.Length; i++)
            {
                newBuckets[i] = -1;
            }
            Entry[] newEntries = new Entry[newSize];
            Array.Copy(entries, 0, newEntries, 0, count);
            if (forceNewHashCodes)
            {
                for (int i = 0; i < count; i++)
                {
                    if (newEntries[i].hashCode != -1)
                    {
                        newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
                    }
                }
            }
            for (int i = 0; i < count; i++)
            {
                if (newEntries[i].hashCode >= 0)
                {
                    int bucket = newEntries[i].hashCode % newSize;
                    newEntries[i].next = newBuckets[bucket];
                    newBuckets[bucket] = i;
                }
            }
            buckets = newBuckets;
            entries = newEntries;
        }

        public void Clear()
        {
            if (count > 0)
            {
                for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
                Array.Clear(entries, 0, count);
                freeList = -1;
                count = 0;
                freeCount = 0;
            }
        }

        public bool Contains(KeyValuePair item)
        {
            return ContainsKey(item.Key);
        }

        public bool ContainsKey(TKey key)
        {
            return FindEntry(key) >= 0;
        }

        public bool ContainsValue(TValue value)
        {
            if (value == null)
            {
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0 && entries[i].value == null) return true;
                }
            }
            else
            {
                EqualityComparer c = EqualityComparer.Default;
                for (int i = 0; i < count; i++)
                {
                    if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true;
                }
            }
            return false;
        }

        public void CopyTo(KeyValuePair[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public bool Remove(KeyValuePair item)
        {
            return Remove(item.Key);
        }

        public bool Remove(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException();
            }
            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1;
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
                {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                    {
                        //  key   0,             0  key
                        if (last < 0)
                        {
                            //       bucket       ,   -1
                            buckets[bucket] = entries[i].next;
                        }
                        else
                        {
                            //     ,  key,                                next
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        freeList = i;
                        freeCount++;
                        return true;
                    }
                }
            }
            return false;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            int i = FindEntry(key);
            if (i >= 0)
            {
                value = entries[i].value;
                return true;
            }
            value = default(TValue);
            return false;
        }

        private int FindEntry(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException();
            }

            if (buckets != null)
            {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
                {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this, Enumerator.KeyValuePair);
        }

        IEnumerator> IEnumerable>.GetEnumerator()
        {
            return new Enumerator(this, Enumerator.KeyValuePair);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this, Enumerator.DictEntry);
        }

        public struct Enumerator : IEnumerator>
        {
            private DictionaryScript dictionary;
            private int index;
            private KeyValuePair current;
            private int getEnumeratorRetType;

            internal const int DictEntry = 1;
            internal const int KeyValuePair = 2;

            internal Enumerator(DictionaryScript dictionary, int getEnumeratorRetType)
            {
                this.dictionary = dictionary;
                index = 0;
                this.getEnumeratorRetType = getEnumeratorRetType;
                current = new KeyValuePair();
            }

            public bool MoveNext()
            {
                while ((uint)index < (uint)dictionary.count)
                {
                    if (dictionary.entries[index].hashCode >= 0)
                    {
                        current = new KeyValuePair(dictionary.entries[index].key, dictionary.entries[index].value);
                        index++;
                        return true;
                    }
                    index++;
                }

                index = dictionary.count + 1;
                current = new KeyValuePair();
                return false;
            }

            public KeyValuePair Current
            {
                get { return current; }
            }

            public void Dispose()
            {
            }

            object IEnumerator.Current
            {
                get
                {
                    if (getEnumeratorRetType == DictEntry)
                    {
                        return new DictionaryEntry(current.Key, current.Value);
                    }
                    else
                    {
                        return new KeyValuePair(current.Key, current.Value);
                    }
                }
            }

            void IEnumerator.Reset()
            {
                index = 0;
                current = new KeyValuePair();
            }
        }


        public sealed class KeyCollection : ICollection
        {
            private DictionaryScript dictionary;

            public KeyCollection(DictionaryScript dictionary)
            {
                if (dictionary == null)
                {
                    throw new ArgumentNullException();
                }
                this.dictionary = dictionary;
            }

            public KeyEnumerator GetEnumerator()
            {
                return new KeyEnumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new KeyEnumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new KeyEnumerator(dictionary);
            }

            public int Count
            {
                get { return dictionary.Count; }
            }

            public void Add(TKey item)
            {
                throw new NotSupportedException();
            }

            public void Clear()
            {
                throw new NotSupportedException();
            }

            public bool Contains(TKey item)
            {
                return dictionary.ContainsKey(item);
            }

            public void CopyTo(TKey[] array, int arrayIndex)
            {
                throw new NotSupportedException();
            }

            public bool Remove(TKey item)
            {
                throw new NotSupportedException();
            }
        }

        public struct KeyEnumerator : IEnumerator, IEnumerator
        {
            private DictionaryScript dictionary;
            private int index;
            private TKey currentKey;

            internal KeyEnumerator(DictionaryScript dictionary)
            {
                this.dictionary = dictionary;
                index = 0;
                currentKey = default(TKey);
            }

            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                while ((uint)index < (uint)dictionary.count)
                {
                    if (dictionary.entries[index].hashCode >= 0)
                    {
                        currentKey = dictionary.entries[index].key;
                        index++;
                        return true;
                    }
                    index++;
                }

                index = dictionary.count + 1;
                currentKey = default(TKey);
                return false;
            }

            public TKey Current
            {
                get
                {
                    return currentKey;
                }
            }

            Object IEnumerator.Current
            {
                get
                {
                    if (index <= 0 || (index > dictionary.count))
                    {
                        throw new IndexOutOfRangeException();
                    }

                    return currentKey;
                }
            }

            void IEnumerator.Reset()
            {
                index = 0;
                currentKey = default(TKey);
            }
        }


        public sealed class ValueCollection : ICollection
        {
            private DictionaryScript dictionary;

            public ValueCollection(DictionaryScript dictionary)
            {
                if (dictionary == null)
                {
                    throw new ArgumentNullException();
                }
                this.dictionary = dictionary;
            }

            public ValueEnumerator GetEnumerator()
            {
                return new ValueEnumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new ValueEnumerator(dictionary);
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new ValueEnumerator(dictionary);
            }

            public int Count
            {
                get { return dictionary.Count; }
            }

            public void CopyTo(TValue[] array, int arrayIndex)
            {
                throw new NotSupportedException();
            }

            public void Add(TValue item)
            {
                throw new NotSupportedException();
            }

            public void Clear()
            {
                throw new NotSupportedException();
            }

            public bool Contains(TValue item)
            {
                return dictionary.ContainsValue(item);
            }

            public bool Remove(TValue item)
            {
                throw new NotSupportedException();
            }
        }

        public struct ValueEnumerator : IEnumerator, IEnumerator
        {
            private DictionaryScript dictionary;
            private int index;
            private TValue currentValue;

            internal ValueEnumerator(DictionaryScript dictionary)
            {
                this.dictionary = dictionary;
                index = 0;
                currentValue = default(TValue);
            }

            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                while ((uint)index < (uint)dictionary.count)
                {
                    if (dictionary.entries[index].hashCode >= 0)
                    {
                        currentValue = dictionary.entries[index].value;
                        index++;
                        return true;
                    }
                    index++;
                }
                index = dictionary.count + 1;
                currentValue = default(TValue);
                return false;
            }

            public TValue Current
            {
                get
                {
                    return currentValue;
                }
            }

            Object IEnumerator.Current
            {
                get
                {
                    if (index <= 0 || (index > dictionary.count))
                    {
                        throw new IndexOutOfRangeException();
                    }

                    return currentValue;
                }
            }

            void IEnumerator.Reset()
            {
                index = 0;
                currentValue = default(TValue);
            }
        }
    }
}

Dictionary 공식 호출 인 스 턴 스:
using System;
using System.Collections.Generic;
using System.Collections;

namespace StructScript
{
    public class TestDictionary
    {
        static void Main(string[] args)
        {
            DictionaryScript testDic = new DictionaryScript(6);
            testDic.Add(4, "4");
            //    6    ,  4 11 key,   hashcode     ,      hash     
            testDic.Add(11, "11");

            DictionaryScript test1Dic = new DictionaryScript(6);
            test1Dic.Add(4, "4");
            test1Dic.Add(10, "11");
            test1Dic.Add(9, "11");
            test1Dic.Add(8, "11");
            test1Dic.Add(7, "11");
            test1Dic.Add(6, "11");
            test1Dic.Add(5, "11");
            //             ,            7
            //C#         , DictionaryScript      Initialize      
            //      ,    ,         
            test1Dic.Add(3, "11");
            string value1;
            test1Dic.TryGetValue(2, out value1);
            test1Dic.Remove(3);


            //         
            DictionaryScript openWith = new DictionaryScript();

            openWith.Add("txt", "notepad.exe");
            openWith.Add("bmp", "paint.exe");
            openWith.Add("dib", "paint.exe");
            openWith.Add("rtf", "wordpad.exe");

            // The Add method throws an exception if the new key is 
            // already in the dictionary.
            try
            {
                openWith.Add("txt", "winword.exe");
            }
            catch (ArgumentException)
            {
                Console.WriteLine("An element with Key = \"txt\" already exists.");
            }

            // The Item property is another name for the indexer, so you 
            // can omit its name when accessing elements. 
            Console.WriteLine("For key = \"rtf\", value = {0}.", openWith["rtf"]);

            // The indexer can be used to change the value associated
            // with a key.
            openWith["rtf"] = "winword.exe";
            Console.WriteLine("For key = \"rtf\", value = {0}.",
                openWith["rtf"]);

            // If a key does not exist, setting the indexer for that key
            // adds a new key/value pair.
            openWith["doc"] = "winword.exe";

            // The indexer throws an exception if the requested key is
            // not in the dictionary.
            try
            {
                Console.WriteLine("For key = \"tif\", value = {0}.",
                    openWith["tif"]);
            }
            catch (KeyNotFoundException)
            {
                Console.WriteLine("Key = \"tif\" is not found.");
            }

            // When a program often has to try keys that turn out not to
            // be in the dictionary, TryGetValue can be a more efficient 
            // way to retrieve values.
            string value = "";
            if (openWith.TryGetValue("tif", out value))
            {
                Console.WriteLine("For key = \"tif\", value = {0}.", value);
            }
            else
            {
                Console.WriteLine("Key = \"tif\" is not found.");
            }

            // ContainsKey can be used to test keys before inserting 
            // them.
            if (!openWith.ContainsKey("ht"))
            {
                openWith.Add("ht", "hypertrm.exe");
                Console.WriteLine("Value added for key = \"ht\": {0}",
                    openWith["ht"]);
            }

            // When you use foreach to enumerate dictionary elements,
            // the elements are retrieved as KeyValuePair objects.
            Console.WriteLine();
            foreach (KeyValuePair kvp in openWith)
            {
                Console.WriteLine("Key = {0}, Value = {1}",
                    kvp.Key, kvp.Value);
            }

            // To get the values alone, use the Values property.
            DictionaryScript.ValueCollection valueColl =
                openWith.Values;

            // The elements of the ValueCollection are strongly typed
            // with the type that was specified for dictionary values.
            Console.WriteLine();
            foreach (string s in valueColl)
            {
                Console.WriteLine("Value = {0}", s);
            }

            // To get the keys alone, use the Keys property.
            DictionaryScript.KeyCollection keyColl =
                openWith.Keys;

            // The elements of the KeyCollection are strongly typed
            // with the type that was specified for dictionary keys.
            Console.WriteLine();
            foreach (string s in keyColl)
            {
                Console.WriteLine("Key = {0}", s);
            }

            // Use the Remove method to remove a key/value pair.
            Console.WriteLine("
Remove(\"doc\")"); openWith.Remove("doc"); if (!openWith.ContainsKey("doc")) { Console.WriteLine("Key \"doc\" is not found."); } Console.ReadLine(); } } }

좋은 웹페이지 즐겨찾기