해시 함수란, 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수이다.
해싱이란, 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것이며,
이를 통해 데이터를 가능한 빠르게 저장하고 검색할 수 있다.

해시 함수의 특징

• 해시 함숫값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

그 외

해시 함수는 체크섬, 손실 압축, 무작위화 함수, 암호 등과도 관련이 깊다.
그러나 서로 용도와 요구사항이 다른 만큼 각각 다르게 설계되고 최적화 된다.

해시 테이블 (Hash Table)

해시 테이블은 키-값 쌍을 저장하는 선형 자료구조이다.
해시 함수를 사용하여 키를 해시값으로 변환하고, 이 해시값을 인덱스로 사용하여 값을 배열에 저장한다.

해시 테이블의 주요 연산:

1. Insert: 키-값 쌍을 해시 테이블에 추가
2. Search: 주어진 키에 해당하는 값 검색
3. Delete: 주어진 키에 해당하는 값 제거

해시 테이블의 특징

• 빠른 데이터 접근
  • 평균적으로 O(1) 시간 복잡도로 데이터 삽입, 검색, 삭제 가능
• 용도
  • 데이터를 빠르게 삽입하고 검색해야 할 때 사용
• 구현
  • 해시 함수와 연결 리스트를 사용하여 구현 가능

해시의 충돌 (Hash Collision)

해시 충돌은 두 개 이상의 키가 동일한 해시값을 가질 때 발생한다.
해싱 과정에서 서로 다른 키가 동일한 해시값을 가지게 되면, 같은 위치에 값을 저장하려는 문제를 의미한다.

개별 연결법 (Separate Chaining)

해시 버킷을 연결 리스트로 구현하여, 충돌이 발생하면 해당 버킷의 리스트에 키-값 쌍을 추가한다.

• 장점
  • 간단한 구현
  • 해시 테이블의 로드 팩터가 높아져도 충돌을 효과적으로 처리 가능
• 단점
  • 연결 리스트의 오버헤드
  • 최악의 경우(모든 키가 동일한 버킷에 할당된 경우), 탐색 시간이 O(n)

개방 주소법 (Open Addressing)

모든 키-값 쌍을 해시 테이블 자체에 저장한다.
충돌이 발생하면, 다른 버킷을 찾아 키-값 쌍을 저장한다.
선형 탐사법(Linear Probling), 이중 해싱(Double Hashing) 등 다양한 방법으로 구현 가능하다.

• 장점
  • 버킷 외부에 별도의 저장 공간이 필요 없다
• 단점
  • 클러스터링 문제 발생 가능
  • 로드 팩터(해시 테이블에 저장된 데이터 갯수를 버킷의 갯수로 나눈 값) 증가에 따하 성능 저하

셋 (Set)

셋은 중복을 허용하지 않는 데이터의 집합을 관리하는 추상 데이터 타입이다.
셋은 수학적인 집합의 개념을 컴퓨터 과학에 도입한 것으로, 각 요소가 고유함을 보장한다.

셋의 주요 연산:

1. Insert: 요소를 셋에 추가
2. Search: 주어진 요소 검색
3. Delete: 주어진 요소 제거

셋의 특징

• 고유성
  • 각 요소가 모두 고유함
• 용도
  • 중복을 허용하지 않는 요소의 집합을 관리할 때 사용
• 구현
  • 해시 테이블이나 트리 구조를 사용하여 구현 가능
  • 해시 테이블
    • 비교적 빠른 연산 속도, 요소 비정렬
  • 트리 구조
    • 비교적 느린 연산 속도, 요소 정렬

---

참고 문헌

• 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)
• 자바 알고리즘 인터뷰 with 코틀린