해시 테이블

✅ 1. 해시 테이블(Hash Table)이란?

• 해시 테이블은 Key-Value 구조의 자료구조입니다.
• 주요 특징은 탐색(Search), 삽입(Insert), 삭제(Delete) 모두 평균적으로 O(1)의 시간 복잡도를 가진다는 점입니다.
• 내부적으로는 해시 함수(Hash Function)를 이용해 키를 버킷 인덱스로 변환하고, 이 인덱스를 기반으로 데이터를 저장합니다.

📌 비교:

• 이진 탐색 트리(Binary Search Tree): O(log N)
• 해시 테이블(Hash Table): O(1) (단, 충돌이 적을 경우)

---

🧠 2. 해시 함수와 버킷 구조

• 해시 함수란 키 값을 고정된 범위 내의 해시값(Index)으로 변환하는 함수입니다.
• 이 인덱스를 통해 테이블(배열) 내 위치를 빠르게 찾아 접근할 수 있습니다.

int key = userId % 1000;  // 단순한 해시 함수 예시

• 효율적인 이유:
  • 키를 직접 비교할 경우 O(N)
  • 해시값으로 직접 접근 시 O(1)

---

⚠️ 3. 해시 충돌(Hash Collision)과 해결 방법

3.1 오픈 어드레싱(Open Addressing)

• 충돌 발생 시 빈 버킷을 탐색하여 데이터를 저장합니다.

📍 선형 조사법 (Linear Probing)

hash(key) + 1 ➜ hash(key) + 2 ➜ ...

📍 이차 조사법 (Quadratic Probing)

hash(key) + 1² ➜ hash(key) + 2² ➜ ...

3.2 체이닝(Chaining)

• 하나의 버킷에 여러 데이터를 리스트 형태로 저장하는 방식.
• 같은 인덱스에 여러 개의 데이터가 저장될 수 있음.

---

🔀 4. std::map vs std::unordered_map (C++ STL 비교)

항목	std::map	std::unordered_map
내부 구조	Red-Black Tree	Hash Table
시간 복잡도	O(log N)	평균 O(1), 최악 O(N)
정렬 여부	자동 정렬됨	정렬되지 않음
메모리 사용	적음	비교적 많음
C# Dictionary와 유사	❌	✅

💡 해시 기반의 구조는 속도는 빠르지만, 메모리 사용량이 증가하고 충돌 관리가 필요합니다.

---

🧪 5. 실전 코드 분석

🧩 5.1 테이블 직접 인덱싱 방식 (비효율적)

void TestTable() {
    struct User { int userId = 0; string username; };
    vector<User> users(1000);
    users[777] = {777, "Rookiss"};
    cout << users[777].username << endl;  // O(1)
}

✅ 빠르지만, ❌ 메모리 낭비 심함 (미사용 인덱스까지 확보)

---

🧩 5.2 해시 인덱싱 방식 (기본 해시 테이블)

void TestHash() {
    struct User { int userId = 0; string username; };
    vector<User> users(1000);
    int userId = 123456789;
    int key = userId % 1000;
    users[key] = {userId, "Rookiss"};

    User& user = users[key];
    if (user.userId == userId)
        cout << user.username << endl;
}

⚠️ 단점: 동일 key 충돌 시 데이터 덮어쓰기 발생

---

🧩 5.3 체이닝 방식 (충돌 해결)

void TestHashTableChaining() {
    struct User { int userId = 0; string username; };
    vector<vector<User>> users(1000);

    int userId = 123456789;
    int key = userId % 1000;

    users[key].push_back({userId, "Rookiss"});
    users[789].push_back({789, "FakeID"});  // 충돌 예시

    for (User& user : users[key])
        if (user.userId == userId)
            cout << user.username << endl;
}

✅ 체이닝 방식은 충돌에도 안전
❌ 단, 탐색시 최악의 경우 O(N)

---

🔒 해시와 보안

• 해시는 비밀번호 저장 시에도 사용됩니다.

입력: "qwer1234"  
해시: "asdf123!@asdfasdf1234"

• 서버는 실제 비밀번호가 아닌 해시값만 저장합니다.
• 비밀번호 찾기 시 기존 비밀번호를 복구하지 않고 새 비밀번호 설정을 유도하는 이유!

---