Hashtable

Hashtable (System.Collections)

• 해시테이블의 구조
  
  Index는 해시테이블의 각 칸을 나타내며, 키를 해시 함수에 넣었을 때 나온 해시값에 따라서 결정된다.
  Chaining : index1에 보면 하나의 인덱스의 여러 개의 키-값 쌍이 저장되고 있는데 이들은 연결리스트로 관리된다. k1-v1은 첫번째 키-값 쌍이고, 다음 노드들은 추가적인 키-값 쌍이다.

체이닝 방식은 해시 충돌이 발생했을 때 동일 인덱스에 저장된 데이터들을 연결리스트로 연결하여 관리하는 방법이다. 이렇게 하면 해시충돌이 발생해도 여러 데이터를 효율적으로 저장하고 검색할 수 있다.

해시테이블은 키-값의 쌍으로 정보를 저장한다. 각 키는 해시테이블 내에서 유일해야한다.

해시테이블의 시간복잡도는 O(logN)이다. 근데 이것은 해시 충돌 (두개 이상의 키가 동일한 해시값을 가지는 경우)이 일어날 경우를 다 고려한 것으로 평균적인 경우에는 O(1)로 상수시간이다.

해시 충돌 발생시에 탐색이 시간복잡도 O(N)에 점점 수렴한다고 한다. 그러나 해시 충돌이 없는 상태에서는 트리나 구조보다도 탐색이 빠르다.

Hash collision 해시충돌

해시 함수로 인해서 여러 키들이 매핑되는 중에 서로 다른 키가 같은 공간에 배치되는 경우 발생하는 문제

예시코드

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        // Hashtable 생성
        Hashtable ht = new Hashtable();

        // 데이터 추가
        // 키는 해시테이블에서 유일해야한다
        ht.Add("id", 1);
        ht.Add("name", "홍길동");
        ht.Add("email", "gildong@example.com");

        // 데이터 접근
        Console.WriteLine($"이름: {ht["name"]}");
        Console.WriteLine($"이메일: {ht["email"]}");

        // 데이터 업데이트 
        // 데이터 값 업데이트는 동일한 키를 사용하면 된다.
        ht["email"] = "new_email@example.com";

        // 업데이트된 이메일 출력
        Console.WriteLine($"업데이트된 이메일: {ht["email"]}");

        // 데이터 삭제
        ht.Remove("id");

        // Hashtable의 내용을 순회하며 출력
        foreach (DictionaryEntry entry in ht)
        {
            Console.WriteLine($"{entry.Key}: {entry.Value}");
        }
    }
}

Hashtable의 모든 요소를 순회하려면 foreach 루프와 DictionaryEntry를 사용한다. 이것은 해시테이블이 DictionaryEntry 개체의 컬렉션으로 구성되어있기 때문이다.