🌐 해시테이블(Hash Table)

1. 해시테이블이란?

해시 테이블은 키(Key)를 해시 함수(Hash Function)에 넣어 계산된 인덱스(Index)에 값(Value)을 저장하는 자료구조

• 장점: 빠른 검색, 삽입, 삭제가 가능
• 평균적으로 시간복잡도는 O(1)

---

1.1 해시 테이블의 동작 원리

1. 해시 함수를 통해 Key를 숫자로 변환
2. 변환된 숫자를 배열의 인덱스로 매핑
3. 해당 인덱스에 Value 저장

ex) Key → 해시 함수 → 인덱스 → 배열[인덱스] = Value

---

2. 키 충돌(Collision) 및 해결 방안

💥 키 충돌이란?

서로 다른 키들이 같은 해시 값을 갖는 현상
➡ 즉, 같은 인덱스를 가리키는 경우

---

2.1 체이닝(Chaining)

• 하나의 버킷에 여러 값을 리스트 형태로 저장
• 충돌이 발생하면 해당 인덱스에 값을 연결 리스트 등으로 체인처럼 이어붙임

---

2.2 개방 주소법(Open Addressing)

➡ C#에서 사용되는 방식

충돌 시 다음 인덱스를 탐색하여 빈 자리에 저장

1️⃣ 선형 탐사(Linear Probing)

• 충돌 시 +1, +2, +3... 순차적으로 다음 인덱스 탐색

2️⃣ 제곱 탐사(Quadratic Probing)

• 충돌 시 +1², +2², +3²... 제곱 형태로 인덱스 탐색

3️⃣ 이중 해싱(Double Hashing)

• 두 개의 해시 함수를 사용하여 탐색 간격을 결정

---

3. C#에서의 해시테이블: Dictionary<TKey, TValue>

C#에서는 System.Collections.Generic.Dictionary<TKey, TValue>를 사용하여 해시 테이블을 구현함.

 // Dictionary<key 값, value값> 변수 = new Dictionary<key,value)();
 Dictionary<string,Monster> monsterDic = new Dictionary<string, Monster>();

✅ 주요 특징

• 제너릭 컬렉션
• 내부적으로 개방 주소법을 이용해 충돌 처리
• O(1)에 가까운 성능으로 빠른 데이터 접근 가능

---

🔧 주요 메서드

📌 Add : O(1)

• 새 키와 값을 추가
• 동일한 키가 존재할 경우 예외(Exception) 발생

Dictionary<string, int> dict = new Dictionary<string, int>();
dict.Add("Apple", 100);
// dict.Add("Apple", 200); → 예외 발생

📌 TryAdd (C# 7.0 이후)

• 키가 존재하지 않을 경우만 추가
• 중복 키 무시

📌 ContainsKey
특정 키 존재 여부 확인

{
    Console.WriteLine("Key exists!");
}

📌 Remove

• 키 제거

dict.Remove("Apple");

📌 TryGetValue

• 키 값을 안전하게 가져오기

if (dict.TryGetValue("Apple", out int value))
{
    Console.WriteLine($"Value: {value}");
}