Dictionary 와 HashTable, SortedDictionary 차이

Dictionary와 HashTable은 모두 Key-Value 저장하는 자료구조이다.

 

몇 가지 차이점이 존재한다.

차이점

Dictionary :

- 제너릭 타입을 사용한다. 키와 값을 명시적으로 지정해야한다.

Hashtable

- object 타입으로 키와 값을 저장한다.

- 타입의 안정성을 제공하지 않음으로 런타임 에러가 발생할 수 있다.

- 박싱, 언박싱이 발생 할 수 있다.

 

HashTable의 문제점을 개선한 것이 Dictionary 자료 구조이다.

 

Dictionary 내부 자료 구조는 HashTable을 사용한다.

private int FindEntry(TKey key) 
{
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    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;
}

 

그리고 SortedDictionary 은 TreeSet<T> 이라는 자료구조를 사용하고 있는데 TreeSet은 SortedSet<T>을 상속 받아서 사용된다.

    [Serializable]
    internal class TreeSet<T> : SortedSet<T> {
 
        public TreeSet()
            : base() { }
 
        public TreeSet(IComparer<T> comparer) : base(comparer) { }
 
        public TreeSet(ICollection<T> collection) : base(collection) { }
 
        public TreeSet(ICollection<T> collection, IComparer<T> comparer) : base(collection, comparer) { }
 
        public TreeSet(SerializationInfo siInfo, StreamingContext context) : base(siInfo, context) { }
 
        internal override bool AddIfNotPresent(T item) {
            bool ret = base.AddIfNotPresent(item);
            if (!ret) {                
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);                
            }
            return ret;
        }
 
    }

 

SortedSet<T> 의 내부 알고리즘을 보게 되면 Red-Black Tree를 사용하고 있다.

//
// A binary search tree is a red-black tree if it satisfies the following red-black properties:
// 1. Every node is either red or black
// 2. Every leaf (nil node) is black
// 3. If a node is red, then both its children are black
// 4. Every simple path from a node to a descendant leaf contains the same number of black nodes
// 
// The basic idea of red-black tree is to represent 2-3-4 trees as standard BSTs but to add one extra bit of information  
// per node to encode 3-nodes and 4-nodes. 
// 4-nodes will be represented as:          B
//                                                              R            R
// 3 -node will be represented as:           B             or         B     
//                                                              R          B               B       R
// 
// For a detailed description of the algorithm, take a look at "Algorithms" by Robert Sedgewick.
//