Hash / Hashable / Hasher / HashTable

⎮ Hash는 왜 필요할까?

     아주 많은 데이터를 빠르게 찾아야하는 순간이 있습니다

   B는 Blue라고 하자는 약속을 정했습니다

   누군가 "B가 뭐야?" 라고 물어봤을 때, B의 값을 매번 처음부터 끝까지 다 찾아보는 것은 비효율적입니다

 

   이런 상황을 개선하기 위해 등장한 것이 바로 Hash입니다

   데이터를 빠르게 찾기 위해 특정 규칙에 따라 값을 변환해두고 필요할 때 쉽게 꺼내쓰는 것이죠

⎮ Hash

     Hash란 어떤 입력값을 일정한 규칙에 따라 변환한 출력값을 의미합니다

    즉, 함수에 의해 얻어지는 값으로 해시 값 또는 해시코드로 불립니다

    해시 함수는 특정 Input을 넣으면 항상 일정한 Output을 return합니다

 

    A -> 2c23b2

    B -> 5ab235

 

    A를 넣으면 항상 2c23b2가 나오고, B를 넣으면 항상 5ab235가 나오는 것

   이 일관성이 바로 Hash의 특성입니다

 

⎮ Hasher

    A를 넣으면 항상 2c23b2가 된다는 말을 이해하려면, Hasher를 알아야 합니다

  Hasher는 임의의 byte 시퀀스를 정수 해시 값으로 변환하는데 사용될 수 있습니다

 

 

  combine 메서드를 여러 번 호출하여 해시할 데이터를 계속 입력하고,

  모든 데이터를 넣은 후에는 finalize()를 호출해서 해시 값을 얻게 됩니다

 

  Swift 프로그램이 실행되는 동안, 같은 바이트 시퀀스를 같은 순서로 넣으면 finalize()는 항상 동일한 해시 값을 return합니다

 다만 Swift 4.2부터는 보안 강화를 위해 실행 환경이 바뀌면 HashValue가 달라질 수 있습니다

 하지만 이 해시 알고리즘은 avalanche effect(눈사태 효과)를 가지도록 설계되어 있어서,

 시드(seed)나 입력 바이트가 아주 조금만 바뀌어도 해시 값의 결과는 크게 달라지게 됩니다

 

⎮ Hashable

    위의 Hasher에서 해시할 수 있는 조건은 Hashable 프로토콜을 준수하는 것입니다

   이 프로토콜을 채택한 타입은 정수 형태의 hash 값을 생성할 수 있습니다

 

   Hashable을 채택한 타입은 Set의 원소나 Dictionary의 key로 사용할 수 있습니다

  근데 왜 Set의 원소나 Dictionary는 Hashable을 채택해야할까요?

let colors = ["B": "blue", "R": "red"]

 

   여기서 B라는 key는 항상 blue라는 value를 갖게 됩니다

  만약 Dictionary의 key가 Hashable하지 않으면, B라는 key로 접근할 때마다 다른 value가 나오게 됩니다

 

  마찬가지로 Set은 중복 없는 컬렉션이고, 원소들을 빠르게 탐색하여 새 값이 기존 값에 존재하는지 확인해야 합니다

 이를 위해 내부적으로 Hash table로 구현되어 있어서 Hashable 해야합니다

 

   기본적으로 Swift의 기본 타입(Int, String, Bool 등)은 Hashable 합니다

 struct의 저장 프로퍼티가 모두 Hashable이거나 enum의 모든 연관값이 Hashable이면 Hashable 프로토콜을 채택할 수 있습니다

 

    class는 기본적으로 object identify 기반 hashValue가 제공됩니다

  다만 class의 기본 hashable은 *논리적 동등성이 아니라 *물리적 동일 객체인지가 기준입니다

  즉, 같은 값을 담은 다른 인스턴스라도, 메모리 주소가 다르면 hashValue도 다릅니다

  그래서 class로 논리적 동등성을 표현하려면 직접 Hashable/Equatable을 구현해야 합니다

  

    struct의 저장 프로퍼티(또는 연관값) 중 Hashable이 아닌게 있다면 어떻게 해야할까요?

  그럴 때는 다음과 같이 직접 구현해야합니다

// 일부 필드 무시 Hashable
struct User: Hashable {
    let id: Int
    var name: String
    var updateAt: Date // hashable하지 않은 값
    
    static func ==(lhs: User, rhs: User) -> Bool {
    	lhs.id == rhs.id      // updateAt과 name은 동치성에서 제외
    }
    
    func hash(into h: inout Hasher) {
    	h.combine(id)      // 해시도 id만 반영
    }
}

// 대소문자 무시 동치성
struct Tag: Hashable {
	let raw: String
    static func ==(lhs: Tag, rhs: Tag) -> Bool {
    	lhs.raw.lowercased() == rhs.raw.lowercased()
    }
    
    func hash(into h: inout Hasher) {
    	h.combine(raw.lowercased())
    }
}

 

  단, 이때는 finalize()를 호출하지 않습니다

 대신 해시 값을 실제로 써야할 때 Set이나 Dictionary 같은 해시 기반 컨테이너가 알아서 자동으로 finalize를 호출해줍니다

 이렇게 얻어진 해시값은 .hashValue로 확인할 수 있습니다

let r = "Red"
print(r.hashValue) //8622856722422684648
print(r.hashValue) //8622856722422684648
print(r.hashValue) //8622856722422684648

 

⎮ Equatable

    Hashable은 내부적으로 Equatable을 채택하고 있습니다

 

   Hashable에서 Equatable은 hash value로 찾은 원본 값이 정말 같은지를 확인합니다

 쉽게 말하자면, Hashable은 "어디에 저장할지"를 결정하는 것이고, Equatable은 "정말 같은 값인지"를 결정하는 것 입니다

 

 해시는 값이 같을 가능성이 높은 데이터를 찾는 용도입니다

해시 함수를 통해 얻은 값은 bucket(저장 위치)가 정해지고,

Set이나 Dictionary에서 새 값을 넣거나 조회할 때, Hash 값을 계산해서 바로 해당 버킷 위치로 이동합니다

따라서 매우 빠른 O(1) 연산이 이루어지는 것이죠

 

  그런데 여기서 해시 '충돌'이 발생할 수 있습니다

 다른 값인데도 정말 낮은 확률로 같은 버킷에 들어갈 수 있습니다

"cat" -> 12345
"dog" -> 12345

 

  여기서 만약 해시값만으로 두 값을 비교한다면 같은 버킷에 여러 값이 존재할 수 있게 됩니다

 따라서 == 으로 두 값이 정말 같은 값인지 확인해야 합니다

 이 때 정말 같은 값인지 확인하는 역할을 하는 것이 바로 Equatable입니다

⎮ HashTable

    HashTable은 값을 저장할 위치를 "해시값"으로 계산해서 바로 접근하는 자료구조입니다

   따라서 검색, 삽입, 삭제가 일반적으로 O(1)에 가깝게 동작합니다

 

    일반적인 배열이라면, 어떤 값이 있는지 검색할 때 일일히 다 찾아야하기 때문에 O(n) 연산이 들어갑니다

  그러나 해시 테이블은 해시 함수를 이용해서 값을 숫자(Hash)로 변환하고,

  배열의 특정 위치(Bucket)에 바로 저장하기 때문에 O(1)에 가깝습니다

 

    앞서 말한 것처럼

let dict = ["B": "Blue", "R": "Red"]

   

    이런 dictionary가 있을 때,

    "B"의 해시 값이 10293845라면, 5번 칸(bucket)을 보고 바로 꺼내서 빠르게 조회가 가능한 것이죠

 

     그런데 만약 같은 Bucket에 여러 개의 값이 있다면 어떻게 될까요?

   여기서 해시 충돌이 발생합니다

   이러한 충돌 상황에서 해시 테이블은 크게 두 가지 중 하나로 충돌을 해결합니다

 

⎮ Hash 충돌 해결

      체이닝(chaining) : 같은 버킷에 연결 리스트 / 작은 배열로 여러 개를 담아두는 방식

      오픈 어드레싱(open addressing) : 충돌나면 다른 빈칸을 찾아서 옮겨 넣는 방식

 

     Swift의 Set/Dictionary는 오픈 어드레싱 계열을 사용합니다

    따라서 cat이 9번 버킷에 있고, dog도 9번 버킷으로 들어가게 되면

    1. 9번 칸에서 == 비교를 하고, 다른 값이면 

    2. 다음 후보 칸(예: (h + 1) % capacity 또는 제곱 / 이중해시 기반의 다음 인덱스) 프로빙

    3. 빈 칸을 만날 때까지 1~2를 반복 후 빈칸에 dog 저장(만약 칸이 없다면 capacity를 늘리고 rehash)

     

      capacity를 처음부터 크게 잡으면 메모리 낭비가 일어날 수 있기 때문에,

     해시 테이블의 전체 용량은 로드 팩터(load factor)가 일정 기준을 넘으면 용량을 증가 시키는 방식으로 작동합니다

     용량이 늘어나면, 모든 값을 다시 재해시하면서 새로운 버킷 테이블로 값을 옮겨줍니다 

 

       이렇게 복잡한 과정이 필요한 이유는 데이터를 O(1)에 가깝게, 빠르게 조회하기 위함입니다

     해시 값을 통해 바로 버킷을 찾고, 충돌이 나도 빠르게 다른 위치를 탐색하고, 필요하면 자동으로 용량을 늘리고 재정렬하는 방식으로

     거의 평균적으로 O(1) 연산으로 데이터를 찾을 수 있게 됩니다

 

⎮ 해시테이블은 평균적으로 O(1)

      O(1)이면 O(1)일 것이지 왜 찝찝하게 '평균적으로' O(1)일까요?

     바로 위에서 말한 해시 충돌 문제 때문입니다

     기본적으로 해시테이블은 O(1)입니다

 

     1. 입력 값을 해시 함수에 넣고

     2. 정수 Hash로 변환한 뒤

     3. Hash % capacity(버킷 인덱스 계산)

     4. 해당 위치에 접근

 

     그러나, 위 flow에서 만약 버킷에 다른 값이 저장되어 있다면

    해시 테이블 특성상 다음 위치를 찾아야하고,

    이 과정에서 추가 비교가 생기기 때문에 최악의 경우에는 O(n)이 됩니다

 

     하지만 잘 설계된 해시 함수 + 충돌 해결 알고리즘을 사용하면 O(1)에 가깝게 동작합니다

⎮ 정리하며

       hash, hashable, equatable은 단순한 개념이 아니라

     Swift가 컬렉션을 빠르고 효율적으로 동작하게 만드는 핵심 원리입니다

     Set이 중복 없는 컬렉션으로 동작하는 이유, Dictionary가 key로 값을 즉시 찾아오는 이유,

     구조체나 enum을 Set:Dictionary에서 활용할 수 있는 이유가

     바로 Hashable, Equatable, HashTable 덕분입니다

---

⎮ 논리적 동등성(logical equality)

      값이 같으면 같은 것으로 취급하는 것

let u1 = User(id: 1, name: "Tom")
let u2 = User(id: 1, name: "Tom")

 

    u1과 u2는 데이터가 완전히 똑같고,

  논리적으로는 같은 사용자라고 생각하는게 자연스러운 것

  -> 내용이 같으면 같은 객체라고 보는 것

 

⎮ 물리적 동일 객체(Reference identity)

    메모리 안의 진짜 같은 인스턴스인가 확인하는 것

let u1 = User(id: 1, name: "Tom")
let u2 = u1

 

    여기서 u1과 u2는 같은 객체를 가리키고 있기 때문에, 메모리 주소가 동일하다

  따라서 진짜 같은 인스턴스로 취급된다