해시(Hash)

해시(Hash)

정의

입력 데이터를 고정된 길이의 데이터로 변환하는 것

• swift에서 해시를 지원하는 자료구조 : Set, Dictionary

해시함수

정의

입력받은 데이터를 해시 값으로 출력시키는 알고리즘

• 해시함수를 어떻게 구현하느냐에 따라 성능과 용도가 달라짐. 암호, 블록체인에도 사용됨.

해시 테이블

정의

해시함수를 사용해 변환한 값을 색인(index)로 삼아 저장하는 key, value의 형태를 갖는 자료구조

• 예시를 들자면, 전화번호부와 같다(이름을 통해 전화번호를 찾는것). key, value의 구조가 아니면 처음부터 끝까지 검색해야되기 때문에 비효율적이게 된다.

장단점

• 장점
  • 검색 속도가 빠르다. O(1)
  • 키에 대한 데이터 중복 확인이 쉽다.
• 단점
  • 저장공간이 많이 필요하다. 충돌(collison)이 발생할 경우 부가적인 저장공간이 더 필요하게 됨.

충돌(collision)

• 충돌의 2가지 경우

  1. 다른 키를 사용했지만 중복되는(동일한) 해시코드를 갖게되는 경우
  2. 코드는 다른데 인덱스 환산시 동일한 인덱스를 가지게 됐을 때

• 충돌 해결 방법

  1. 체이닝 기법(Chaining) : Open Hashing. 연결 리스트를 사용해 동일한 해시주소값을 연결해줌.
     (해시테이블 저장공간 외의 공간을 활용하는 방법)
  2. Linear Probing 기법 - 해시 테이블 안에서 해결하는 방법. 충돌이 일어나면 해시 저장공간을 처음부터 순회해서 남는 공간에 저장

Hashable

정의

integer 해시값을 생성하기 위해 해시될 수 있는 타입

• Hashable 프로토콜을 준수하는 모든 타입을 key로 사용 가능하다
• swift의 기본 타입들은 모두 Hashable하다
• 만약 class, struct, enum으로 사용자가 직접 만든 타입으로 Hashable하려면 Hashable 프로토콜을 채택해야 한다.

struct Person: Hashable {
    let name: String
    let age: Int
}

---

https://developer.apple.com/documentation/swift/hashable
https://developer.apple.com/documentation/swift/hashable/hash(into:)