[swift]TIL_Hashable

오늘은 알고리즘 문제에서 마주하게된 Hash에 대해서 공부해 보았다.

# Hash

Hash(해쉬) : 데이터를 고유하게 식별하기 위해 고정된 길이의 값(해시값)을 생성하는 과정으로 Swift에서는 주로 컬렉션 타입(Set, Dictionary)에서 객체를 비교하거나, 데이터를 빠르게 검색하고 저장하기 위해 사용한다.
원본 데이터를 특정 규칙에 따라 처리하여 간단한 숫자로 만든것을 해쉬값이라고 한다. 정확히는 원본 데이터(객체)를 해쉬 함수(Hash function)을 사용하여 64bit의 Int값으로 변환한 것이다.

Hash의 이점 및 활용

• 빠른 검색 및 저장이 가능해 데이터의 고유한 식별값을 이용해 시간이 단축된다.
• 해시값만을 저장하기 때문에 메모리 효율성이 올라간다.
• 서로 다른 데이터가 동일한 해시값을 생성할 수 있기에 충돌 가능성이 크기에 주의해야한다.
• swift에서는 Dictionary, Set에서 사용이되며, 데이터베이스의 인덱싱으로도 사용이된다.
  배열보다 딕셔너리를 이용한 hash값으로 검색하는게 0부터 n번째까지 하나하나 접근하는것보다 빠르다.

Hash Function

• 어떤 숫자/글 등을 input으로 사용해 어떤 알고리즘을 통해 고정된 길이의 숫자/ 글자이면서 유일한 값이 나오는 함수이고 우리는 이 함수가 어떤 알고리즘인지는 중요하지 않다.
• ex) "apple", "banana", "orange" -> hash value값 12345, 63743, 13647와 같이 각각 다른 값이 나온다.
  "apple"을 입렵해야 12345가 나오고 "banana"를 입력해야 63743이 나온다. 조금이라도 다르게 Input을 받으면 아예 다른 값이 나오게 된다.

예시 코드

• 2개의 테이터를 비교할 때, 데이터가 동일하면 각 데이터의 해쉬값도 동일하다.
  하지만 데이터가 조금이라도 다르면, 완전히 다른 해쉬값을 가진다. 즉 해쉬값을 통해 원본 데이터를 유추할 수는 없다고 할 수 있다.
  

# Hashable

Hashable은 Swift에서 Hash를 지원하기 위한 프로토콜로, 해시값을 계산할 수 있는 타입을 정의한다.
Set이나 Dictionary의 키로 사용되는 타입은 Hashable을 준수해야한다.

• 어떤 타입이 Hashable하다는 것은 해시함수에서 input으로 쓰일 수 있는 "타입" 이라는 것이다.(Hashable)하다

  • Swift의 기본 데이터 타입(Int, String, Double 등)은 기본적으로 Hashable을 준수하고 있다.
  • 사용자 정의 타입은 Hashable을 채택하여 해시값 계산을 구현해야 한다

• Hashable의 구현 원칙
  구조체, 열거형의 경우 Hashable프로토콜 채택시 모든 저장속성(열거형은 모든 연관값)이 Hashable프로토콜을 채택한 타입이라면 hash(:into)메서드 자동 구현된다.

• 예외

  • 클래스는 인스턴스의 유일성을 갖게 하기 위해서는 hash(into:) 메서드 직접 구현해야함.
  • 클래스는 원칙적으로 Hashable 지원 불가하다고 한다.
  • 열거형의 경우 연관값이 없다면 기본적으로 Equatable/Hashable하기 때문에 Hashable 프로토콜을 채택하지 않아도 된다.

Hashable을 사용하는 이유

• Set과 Dictionary에서 사용 가능 : Hashable을 준수하면 Set의 요소나 Dictionary의 키로 사용할 수 있다.

 let peopleSet: Set<Person> = [person1, person2, person3]
 print(peopleSet.count)  // 중복 제거 결과 출력

• 효율적인 데이터 검색 : 해시값을 기반으로 데이터를 바로 참조하므로 검색 속도가 빠르다.
• 중복 방지 : Set과 같은 자료구조는 동일한 해시값을 가지는 객체를 중복으로 허용하지 않는다.