해시 테이블(Hash Table)과 시간복잡도 관계

**해시 테이블이란?**
- 키(Key)를 값(Value)에 매핑하는 자료구조
- 해시 함수를 사용하여 키를 배열의 인덱스로 변환
- 평균적으로 O(1)의 시간복잡도로 데이터 접근 가능

**시간복잡도**

기본 연산:
1. 삽입(Insert): O(1) 평균, O(n) 최악
2. 삭제(Delete): O(1) 평균, O(n) 최악
3. 검색(Search): O(1) 평균, O(n) 최악

```python

# 해시 테이블 구현 예시
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash_function(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self.hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])

**해시 충돌 해결 방법**

1. 체이닝(Chaining)
- 같은 인덱스에 여러 값을 연결 리스트로 저장
- 장점: 구현이 간단
- 단점: 메모리 오버헤드

2. 개방 주소법(Open Addressing)
- 선형 탐사(Linear Probing)
- 이차 탐사(Quadratic Probing)
- 이중 해싱(Double Hashing)

**성능에 영향을 주는 요소**
1. 로드 팩터(Load Factor)
- α = n/m (n: 저장된 항목 수, m: 버킷 수)
- α가 증가하면 충돌 가능성 증가

2. 해시 함수의 품질
- 균등한 분포
- 계산 속도
- 충돌 최소화

**실제 사용 사례**
- 데이터베이스 인덱싱
- 캐싱 시스템
- 중복 제거
- 암호화

**주요 라이브러리/언어별 구현**
```python
# Python
dict_example = {'key': 'value'}

# Java
HashMap<String, String> map = new HashMap<>();

# JavaScript
const map = new Map();
```

해시 테이블은 빠른 데이터 접근이 필요한 경우에 매우 유용하며, 대부분의 현대 프로그래밍 언어에서 기본 자료구조로 제공됩니다.