해시
- 키를 통해 값을 찾을 수 있음
- 그러나 값을 통해 키를 찾을 수는 없음.
- 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없음.
- 값을 익덱스로 활용하려면 적절한 변환 과정을 거쳐야함.
해시 테이블
- 키와 대응한 값이 저장되어 있는 공간
- 해시 테이블의 각 데이터를 버킷이라고 부름.
해시 함수
코딩테스트에서 해시 함수를 직접 구현하라는 문제가 나오는 경우는 거의 없음.
Swift의 STL은 이미 Dictionary 를 제공하는데, 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있음.
해시 함수에 의해 얻어지는 값을 해시값, 해시코드, 해시 체크섬으로도 부름.
해시 함수를 구현할 때 고려해야할 부분
- 첫째, 해시 함수가 변환한 값은 인덱스로 활용해야 함. 따라서, 해시 테이블의 크기를 넘으면 안됨.
- 둘째, 해시 함수가 변환한 값의 충돌*은 최대한 적게 발생해야함. (충돌이 아예 발생하지 않는 해시 함수는 거의 없음)
자주 사용하는 해시 함수
- 나눗셈법
- 곱셈법
- 문자열 해싱
충돌
서로 다른 키에 대해 해시 함수의 결과값이 같으면 충돌이라고 함.
충돌 처리
- 하나의 버킷에 1개를 초과한 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야함.
- 체이닝과 개방주소법
체이닝으로 충돌 처리하기
충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결함.
- 충돌 문제를 링크드리스트로 간단히 해결할 수 있음.
- 해시 테이블 공간 활용성이 떨어짐.
- 검색 성능이 떨어짐. (링크드 리스트는 임의 접근이 안됨)
개방주소법으로 충돌 처리하기
충돌이 발생하면 빈 버킷을 찾아 데이터를 삽입함.
- 남는 공간을 최대한 활용하므로 체이닝기법 보다 메모리를 더 효율적으로 사용함.
- 버킷을 선택하는 방법에 따라 Linear Probing, Quadratic Probing, Double Hashing으로 구분됨.
1) 선형 탐사 방식 (linear probing)
- 충돌이 발생한 위치 정보를 참조하므로, 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동. (보통 간격은 1로 하는 것이 일반적)
- 클러스터*를 형성하면 해시값은 겹칠 확률이 더 올라감. 이를 방지하기 위해 간격을 제곱수만큼으로 두는 방법도 있음.
2) 이중 해싱 방식
- 해시 함수를 2개 사용함
클러스터
해시 충돌이 발생한 값끼리 모이는 영역
Swift에서의 해시
코딩 테스트 문제에서 해시 문제의 핵심 " 키와 값을 매핑하는 과정 "
Swift에서는 Dictionary라는 자료구조 구조체가 있음.
- Dictionary의 Key는 Hashable 프로토콜을 준수해야함.
Hashable
정수 hash값(hashValue)을 제공하는 프로토콜 타입
- Hashable 프로토콜을 준수하면 Set, Dictionary Key로 사용가능.
- Hasher는 hashValue를 생성해주는 해시함수가 있는 구조체.
- Hasher는 combine 메서드를 제공함. 이 메서드를 사용하여 식별할 수 있는 identifier를 hasher에게 념겨주면 됨.
- Hashable을 준수하는 원시타입: String, Integer, Float, Boolean
- 연관 값(associated value)없는 Enum은 Hashable을 따로 채택하지 않아도 자동으로 구현됨.
- 구조체의 저장 프로퍼티들이 모두 Hashable을 준수한다면, Hashable을 채택하였을때 hash(into: ) 메서드는 컴파일러가 자동으로 제공해줌.
- Hashable 프로토콜은 Equatable 프로토콜을 준수하고 있음.
Equatable
값이 동일한 지 비교할 수 있음을 명시하는 프로토콜 타입
이 프로토콜을 준수하는 타입은 == 혹은 !=을 사용하여 동등여부를 비교할 수 있음.
💡 주관적으로 생각해보기
Q. Swift에서 Hashable은 왜 Equatable을 준수하도록 했을까?
A. 해시 값은 유일하지 않을 수 있다. 해시 값이 충돌했을때, 원 데이터를 비교(==)하여 충돌 회피를 할 수 있어야한다.
Q. Dictionary의 데이터 검색 시간복잡도는 항상 O(1)일까?
A. hashValue가 충돌할 경우 충돌회피 알고리즘에 따라 시간 복잡도가 달라질 수 있다. 따라서 hashValue의 충돌이 적게 발생하도록 해시함수를 구성하는 편이 좋다.