해시 관련 용어 정리
해시 함수 (Hash Function): 임의의 데이터를 일정한 크기의 해시값으로 변환하는 함수.
해시 (Hash): 해시 함수의 결과물이며, 저장소에서 값(value)과 매칭되어 저장된다
해시 테이블 (Hash Table): key-value 쌍을 저장하고 검색하기 위해 해시 함수를 사용하는 자료구조.
해싱 (Hashing): 데이터를 해시 함수로 변환하여 해시 테이블에 저장하거나 검색하는 과정.
위의 그림에서 인덱스 주소와 값이 저장되는 곳을 버킷 또는 슬롯 이라고 합니다.
위의 버킷에는 아래와 같은 데이터가 저장됩니다.
이미지 출처
해시 함수(Hash Function)
- 임의의 크기를 가진 데이터를 고정된 크기의 해시 값(hash value)으로 변환하는 함수
- 특징
- 결정적 성질: 동일한 입력 값(key)에 대해 항상 동일한 출력 값(hash)이 생성됩니다.
- 충돌 가능성: 서로 다른 키(key)가 같은 해시(hash) 값을 가지는 경우 해시 충돌(Hash Collision)이 일어나게 됩니다.
해시 테이블(Hash Table)
- 해시 함수를 사용하여 키(Key)를 해시 값(Hash Value)으로 변환하고, 이를 인덱스로 사용하여 데이터를 저장하는 자료구조
- 자바에서는
java.util.HashMap클래스를 사용하여 해시 테이블을 구현할 수 있다. - 시간 복잡도: 검색, 삽입, 삭제 O(1), 충돌 발생 시 최악의 경우 O(n)
- 장단점
- 장점: 빠른 검색이 가능하다
- 단점: 순서가 필요한 데이터에는 어울리지 않으며, 좋은 해시 함수를 선택하지 않으면 충돌이 빈번해질 수 있고, 성능이 저하될 수 있다.
해시 충돌(Hash Collision)
서로 다른 키(key)가 같은 해시(hash) 값을 가지는 경우 발생하는 현상
충돌 해결 방법
1. 체이닝(Chaining) - Java가 사용하는 방식
각 버킷을 연결 리스트로 만들어, 동일한 인덱스에 저장되는 키-값 쌍들을 연결합니다.
충돌이 발생하면 해당 버킷의 연결 리스트에 새로운 키-값 쌍을 추가합니다.
2. 개방 주소법(Open Addressing)
해당 방식은 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장하는데, 이를 위해 여러 가지 탐색 방법이 적용됩니다.
선형 탐색(Linear Probing): 충돌이 발생한 버킷의 다음 버킷(+1)이나 일정 간격(n개)을 건너뛰어 비어있는 버킷에 데이터를 저장합니다.
제곱 탐색(Quadratic Probing): 충돌이 발생한 버킷의 제곱 간격으로 이동하여 비어있는 버킷에 데이터를 저장합니다.
이중 해싱(Double Hashing): 다른 해시 함수를 한 번 더 적용하여 얻은 해시 값을 사용해 비어있는 버킷에 데이터를 저장합니다.
ref.
https://growth-msleeffice.tistory.com/93
https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table해시-해싱-해시테이블-자료구조의-이해-6ijyonph6o
https://hazel-developer.tistory.com/2
