해시 테이블(Hash Table)에 대해서

해시 테이블이란?

해시 테이블(hash table)은 키(key)와 값(value)으로 이루어진 여러 쌍의 데이터를 저장할 수 있는 자료구조(Data Structure)이다. 키를 알고 있으면 'O(1)', 즉 상수 시간에 값을 접근 할 수 있으며 데이터 검색을 최적화하기 위해서 많이 사용한다.

 

해시 테이블은 프로그래밍 언어마다 약간씩 다른 이름으로 불리고 있어서 헷갈릴 수 있는데

대표적으로 C#에서는 사전(Dictionary)가 해시 테이블의 역할을 담당하고, C++에서는 맵(map)이 같은 역할을 한다.

자바에서는 'HashTable' 또는 'HashMap'이 해시 테이블에 해당하는 내장 자료형이다.

 

해시 테이블은 내부적으로 각 키가 값을 가르키는 구조로 되어 있기때문에 값에 접근하든 추가하든 갱신하든 삭제하든 키를 사용하지 않으면 큰 성능 손해를 볼 수 있다. 만약에 해시 테이블을 쓰는데 키로 값을 접근하고 있지 않다면 적합한 자료구조를 사용하고 있지 않다는 증거가 될 수 있다.

 

데이터 추가

해시 테이블에 어떤 값을 저장할 때는 반드시 키가 있어야 한다.

 

예를 들어, 빈 테이블에 'A'를 Key로 '1'을 Value로 저장하면 다음과 같은 모습이 된다.

 

A 👉 1

 

여기에 추가로 'B'를 Key로 '2'를 Value로 저장하면 다음과 같은 모습이 된다.

 

A 👉 1

B 👉 2

 

마찬가지로  'C'를 Key로 '3'를 Value로 저장하면 다음과 같은 모습이 된다.

 

A 👉 1

B 👉 2

C 👉 3

 

해시 테이블은 중복된 값을 저장하는 것을 허용한다.

 

A 👉 1

B 👉 2

C 👉 3

D 👉 3

 

데이터 갱신

반면에 해시 테이블은 중복된 키를 허용하지 않는다. 다시 말해서 하나의 해시 테이블 내에 모든 키들은 유일해야 한다.

대신 키가 가리키고 있는 값은 자유롭게 덮어쓸 수 있다. 그래서 다음과 같이 키 'D'에 해당하는 값을 '4'로 변경할 수 있다.

 

public class Program
{
    static void Main(string[] args)
    {
        var dic = new Dictionary<string, int>() 
            {   {"A", 1},
                {"B", 2},
                {"C", 3},
                {"D", 3}};

        dic["D"] = 4;

        var dic2 = new Dictionary<string, int>()
            {   ["A"] = 1,
                ["B"] = 2,
                ["C"] = 3,
                ["D"] = 3};
    }
}

dic["D"] = 4 처럼 Key값인 "D"를 이용해서 데이터를 갱신하였다.

 

A 👉 1

B 👉 2

C 👉 3

D 👉 4

 

데이터 접근

해시 테이블은 키를 사용해서 값에 접근해야 비로서 빛을 발휘하는 자료구조이다. 값만 알고 있을 때는 해시 테이블에 저장된 값을 하나하나 확인해야하기 때문에 성능이 매우 떨어진다.

 

public class Program
{
    static void Main(string[] args)
    {
        var dic = new Dictionary<string, int>() 
            {   {"A", 1},
                {"B", 2},
                {"C", 3},
                {"D", 3}};

	// key로 검색
        Console.WriteLine(dic["B"]);

	// value로 검색
        foreach(var kv in dic)
        {
            if (kv.Value == 2)
            {
                Console.WriteLine(kv.Key);
            }
        }
    }
}

 

참고 사이트

해시 테이블 (Hash Table) | 알고달레 (algodale.com)