24.12.31 TIL 해시테이블

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

해시테이블은 키(Key)를 통해 데이터를 값(Value)과 매핑하는 자료구조입니다. 내부적으로 해시 함수(Hash Function)를 사용하여 키를 특정 위치(버킷)에 저장합니다.

---

2. 해시테이블의 특징

1. 빠른 검색 속도: 평균적으로 O(1)의 시간 복잡도로 데이터 검색, 삽입, 삭제 가능
2. 키-값 쌍 저장: 데이터를 키와 값으로 저장해 원하는 값을 빠르게 찾을 수 있음
3. 충돌 처리 필요: 해시 함수가 동일한 버킷을 반환할 경우 충돌이 발생

---

3. 해시 함수

• 해시 함수: 입력받은 키를 특정 정수로 변환하여 배열의 인덱스를 생성
• 좋은 해시 함수의 조건:
  • 고르게 분포된 값을 생성
  • 계산이 빠름
  • 동일한 키는 동일한 값을 반환

---

4. 충돌 해결 방법

1) 체이닝(Chaining)

충돌이 발생한 데이터를 연결 리스트로 저장

• 장점: 해시 공간을 효율적으로 활용 가능
• 단점: 데이터가 많아지면 연결 리스트 탐색 속도 느려짐

2) 오픈 어드레싱(Open Addressing)

빈 공간을 찾아 충돌 데이터를 다른 위치에 저장

• 종류: 선형 탐사, 이차 탐사, 이중 해싱
• 장점: 별도의 추가 자료구조가 필요 없음
• 단점: 빈 공간이 부족하면 성능 저하

---

5. 해시테이블의 장단점

장점	단점
평균 O(1)의 빠른 검색, 삽입, 삭제 속도	해시 충돌로 인한 성능 저하 가능성
키-값 저장으로 효율적인 데이터 관리	메모리 사용량이 많을 수 있음
데이터 순서와 상관없이 동작	순차 데이터 탐색에는 비효율적

---

6. 해시테이블 예제 코드

import java.util.Hashtable;

public class HashTableExample {
    public static void main(String[] args) {
        // 해시테이블 생성
        Hashtable<Integer, String> hashTable = new Hashtable<>();

        // 데이터 삽입
        hashTable.put(1, "Apple");
        hashTable.put(2, "Banana");
        hashTable.put(3, "Cherry");

        // 데이터 검색
        System.out.println("Key 2: " + hashTable.get(2)); // Output: Banana

        // 데이터 삭제
        hashTable.remove(1);
        System.out.println("After removal: " + hashTable);

        // 데이터 확인
        if (hashTable.containsKey(3)) {
            System.out.println("Key 3 exists with value: " + hashTable.get(3));
        }
    }
}

---

7. 해시테이블의 활용

• 데이터베이스 인덱싱: 데이터 검색 속도를 높이기 위해 사용
• 캐싱(Cache): 반복적으로 사용하는 데이터를 저장
• 중복 검사: 데이터 중복 여부 확인
• 키-값 매핑: 사용자 정보 저장, 환경 설정 관리

---

8. 마무리

해시테이블은 데이터를 효율적으로 저장하고 빠르게 검색할 수 있어 검색 중심의 시스템에서 매우 유용하다는 것을 알게 되었고 충돌을 효과적으로 처리하는 것이 성능에 중요한 영향을 미친다는 점도 느꼈습니다.