해시(Hash)

1. 해시 테이블(Hash Table)

• 데이터를 키-값 쌍(key-value pair) 형태로 저장하는 자료구조
• 해시 함수(Hash Function)를 사용해 키를 배열의 인덱스로 변환하고, 그 위치에 값 저장
• 중복되는 키가 있으면 안됨!
• 특징 : 빠른 탐색, 삽입 및 삭제
• 캐시(Cache), 데이터베이스 인덱싱, 키-값 쌍 관리(Map)

구성 요소

• Key: 고유한 식별자
• Value: 저장하려는 데이터
• Hash Function: 키를 인덱스로 변환하는 함수

2. 해시 함수

• 키를 고정된 크기의 해시 값으로 변환하는 함수 → 키를 인덱스로 변환

해시 함수의 주요 조건

1. 결정적이어야 한다: 동일한 키에 대해 항상 동일한 해시 값을 반환해야 합니다.
2. 빠르게 계산되어야 한다: 해시 함수는 매우 빠르게 실행되어야 합니다.
3. 균등한 분포: 모든 인덱스에 값이 균등하게 분포되도록 해야 합니다.

💡 근데 해시함수 돌렸는데 서로 다른 키의 해시값이 같으면 어떻게 하죠,,?

→ collision : 서로 다른 두 키가 같은 해시 값을 갖는 경우 발생 → 아래 두 가지 방법으로 해결

• 개방 주소법(Open Addressing): 충돌이 발생했을 때 다른 빈 공간을 찾아 값을 저장하는 방식.
• 체이닝(Separate Chaining): 같은 인덱스에 여러 값을 저장할 수 있도록 링크드 리스트를 사용하는 방식.

3. 충돌 해결 방법

개방 주소법(Open Addressing)

• 해시 테이블 내에서 다른 빈 인덱스를 탐색해 데이터를 저장하는 방식
• 탐색 방법
  • 선형 탐사(Linear Probing): 충돌이 발생하면, 한 칸씩 다음 인덱스를 확인.
  • 이차 탐사(Quadratic Probing): 충돌이 발생하면, 제곱 단위로 인덱스를 이동하며 빈 공간을 찾음.
  • 이중 해싱(Double Hashing): 두 개의 해시 함수를 사용해 충돌을 해결.
• 추가적인 메모리를 사용하지 않음 → separate chaining방식에 비해 메모리를 적게 사용

체이닝(Separate Chaining)

• 링크드 리스트(Linked List)를 사용하여 같은 인덱스에 여러 개의 값을 저장하는 방식
• 장점
  • 해시 테이블이 꽉 차더라도 충돌 쉽게 처리.
  • 테이블 크기에 덜 의존적
• 검색, 삭제는 n개 길이의 linked List가 생성되므로 최악의 경우엔 시간복잡도 O(n)
• 데이터가 많은 경우, 체이닝 방식이 더 많이 쓰인다고 함

---

해시 테이블	평균 시간 복잡도	최악의 시간 복잡도
삽입 (Insert)	O(1)	O(n)
삭제 (Delete)	O(1)	O(n)
탐색 (Search)	O(1)	O(n)
충돌 처리 방법
- 체이닝 (Chaining)	O(1)	O(n)
- 개방 주소법 (Open Addressing)	O(1)	O(n)