[자료구조] 해시테이블(Hash Table), Dictionary

해시테이블

-Hash는 키 값을 Hash Function으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다.

-키 값이 많아지면 매우 많은 배열 공간이 필요한데, 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용한다.

-해시 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다.

 

Hashtable 클래스

-.NET에 Hashtable 클래스는 Non-Generic 클래스다.

-Hashtable은 key값과 value값 모두 object 타입을 받아들여 박싱/언박싱이 일어난다.

-Hashtable은 Double Hashing 방식을 사용하여 Collision Resolution을 하게 된다.

-즉 해시 함수를 사용하여 key가 collision(충돌)이 발생하면, 다른 해시 함수를 계속 사용하여 빈 버켓을 찾게된다.

 

해시 함수 충돌

-서로 다른 키가 동일한 해시 테이블 버켓 위치를 가리킬때 collision이 발생했다 한다.

-이를 해결하기 위해 collision resolution 방식이 사용되는데, 이 방식으론 chaining, linear probing, quadratic probing, double hashing등 여러가지 방식이 있다.

 

해시테이블 시간 복잡도

-추가, 삭제, 검색 O(1) 시간 소요

 

Dictionary<Tkey, Tvalue> 클래스

-.NET에 Generic 방식으로 해시테이블을 구현한 클래스가 Dictionary 클래스다.

-key값과 value값 모두 Strong type을 받아들여 박싱/언박싱이 일여나지 않는다.

-Dictionary는 collision resolution으로 chaining 방식을 이용한다.

 

Dictionary<Tkey, Tvalue> 클래스 시간 복잡도

-추가, 삭제, 검색 O(1) 시간 소요

 

사용 예제

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        Hashtable hashTable = new Hashtable();
        Dictionary<int, string> dictionary = new Dictionary<int,string>();
        
        hashTable.Add("Dev", "재밌다");
        hashTable.Add("Hugh", "개발자다");
        dictionary.Add(1, "안녕하세요");
        dictionary.Add(2, "안녕못해요");
        
        if(hashTable.Contains("Dev"))
        {
            Console.WriteLine(hashTable["Dev"]); //재밌다 출력
        }
        
        string greetings = dictionary[2];
        Console.WriteLine(greetins); //안녕못해요 출력
    }
}