Hash란?
해시 함수에 의해 얻어지는 값을 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.
hash function이란?
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
위에 그림으로 예시를 들자면, 0부터 3까지의 index가 있다고 해보자. 각 사람의 이름은 해시 함수를 이용하여 하나의 index로 맵핑이 된다. 수학적으로는 일대일 맵핑이라 할 수 있다.
f(x) = z // Hash function
f(John Smith) = 1
f(Lisa Smith) = 0
f(Sam Doe) = 3
f(Sandra Dee) = 2같은 입력 값에 대해서는 같은 출력 값이 보장된다. 예를들어 0부터 10000 까지 데이터를 담을 수 있는 리스트가 있다고 해보자. 'elly'라는 이름에 해시 함수를 적용하여 200이라는 index가 생성되면, 리스트의 200 index에 'elly'를 저장하는 방식이다.
해시 함수는 언제나 동일한 해시 값을 반환하기 때문에 'elly'를 입력하면 항상 200 index가 나오므로 굳이 정렬하지 않고도 바로 찾을 수 있게 된다.
이러한 목적으로 사용하는 해시 함수는 해시 값을 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 한다. 그렇지 않다면 해시 함수를 사용하는 의미가 없다.
해시 충돌(Hash Collision)
서로 다른 두 개의 키가 같은 index로 hashing(hash function을 통해 계산됨을 의미)되어 저장할 수 없게 된 상태
하지만, 어설픈 hash function을 통해서 key 값들을 결정한다면 다른 입력값에 대해 동일한 결과값이 도출 될 수 있다. 이렇게 되면 동일한 key값에 복수 개의 데이터가 존재하게 되는데, 이를 해시 충돌(Hash Collision)이라고 한다.
Hash Function의 조건
- 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 낸다. (키가 어떤 특성을 가지고 있느냐에 따라 다름)
- hash function을 무조건 1:1로 만드는 것 보다 충돌을 최소화 하는 방향으로 설계하고, 발생하는 충돌에 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능 하기도 하지만 그런 해시 함수를 만들어 봤자 array와 다를 바 없어지게 되고 메모리를 너무 차지하게 된다.
hashable이란?
정수형 해시 값을 만들어 낼 수 있는 타입을 말한다.
- String, Integer, Bool과 같은 자료형들은 모두 hashable을 따르고 있다.
- struct의 경우 모든 저장 프로퍼티들은 반드시 hashable을 따르고 있어야 한다.
- enum의 경우 모든 값들은 hashable을 따르고 있어야 한다.
Custom 클래스를 만들고 해당 클래스를 Key로 사용하기 위해서는 Custom Class가 Hashable 해야한다. 클래스의 인스턴스를 비교할 수 있어야 하며, hash function을 가지고 있어야 한다는 것을 의미한다.
Hashable은 서로 같은 인스턴스인지 확인하는 Equatable을 상속받고 있다. Hashable을 따르기 위해서는 두 가지 메소드를 구현해야 하는 것이다.
예시
struct GridPoint {
var x: Int
var y: Int
}extension GridPoint: Hashable {
// Equatable protocol method
static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
return lhs.x == rhs.x && lhs.y == rhs.y
}
func hash(into hasher: inout Hasher) {
hasher.combine(x)
hasher.combine(y)
}
}참고
https://namu.wiki/w/%ED%95%B4%EC%8B%9C
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#hash-table
