Hash-Hashable을 곁들인

사실 이건 기본중의 기본이다. 이미 알고리즘을 풀며도 사용하고 개발을 할때도 이미 많은 곳에 포함되어있다. 하지만 내 블로그에는 따로 정리를 해놓은 적이 없어 딥다이브로 파고들 생각이다. 자 들어가자

해쉬🌞

Hashing은 임의의 각각 크기를 가진 입력 데이터를 고정 크기의 값으로 변환하는 과정으로, 이를 해시 함수(Hash Function)가 담당한다.

이 과정에서 생성된 출력값은 해시 값(Hash Value) 또는 해시 코드(Hash Code)라고 한다

나무 위키자료

원본 데이터인 키값을 저 hash function을 통해 64 bit의 int형으로 변환한 것을 확인 할 수 있다. 일반 적으로 키 값이 동일하면 해쉬결과값도 동일하게 나온다. Hash Function를 통해 어떠한 값이 들어오건 정해진 자료내의 결과값으로 반환하여 관리할 수 있다. 이렇게 고정된 크기를 반환하게 하여 일관성 + 암호학적 요구사항 충족.

저 해시함수의 결과값을 Hash라고 하는데 이는 Bucket의 위치를 찾을 수 있는 인덱스와 같은 존재이다. 데이터가 저장되는 공간을 버킷이라 한다. 

해시 테이블은 1:1로 K-V매핑되어 있어 삽입이든 삭제든 검색이든 모두 O(1). 

하지만 고려해야할 것이 여기서 해시 충돌이라는 것이 발생할 수 잇따.

좋은 해시 함수는 몰까?

빠른 계산(Fast Computation): 당연히 해시 값이 들어오면 효율적으로 계산될 수 있어야 한다.

균일 분포(Uniform Distribution): 충돌을 최소화하기 위해 해시 값이 균일하게 분포되어야 한다. 

해시 충돌💥

키 값으로 들어온 것은 다른데 해시 함수의 연산에 따라 결과값이 같게 나올 수가 있다. 이를 해시 충돌이라 한다. 물론 해시 함수를 잘 구현하여 균일 분포하는 것도 방법일 수 있지만 충돌났을때의 방법도 있다. 

체이닝

같은 해시값이 나온것들을 링크드리스트로 관리한다. 

하지만 3을 보면 벌써 4개다. 이렇게 되면 55를 찾을때 시간이 소요된다. 해시를 사용한 이유가 퇴색될수 있다.

개방 주소 📇

그 자리에 이미 다른 값이 있으면 다른 주소를 주는 것이다. 그렇게 되면 내 해시값이 나와도 해당 해시값을 따라가도 다른 값이 들어가 있을 수 있다.

선형 조사: 만약 내 자리에 다른 값이 있다면 임의의 패턴으로 다음 것으로 가서 빈자리가 있을때까지 찾아본다. 있네 하면 거기 앉는다. 오래걸릴수 있다.

더블 해싱: 2개의 해시 함수 사용. 하나는 최초의 해시값 얻을 때 사용, 다른 하나는 충돌이 일어났을 때, 이동할 폭 저장.

SHA

SHA(Secure Hash Algorithm)는 미국 국가안보국(NSA)이 설계하고 NIST(미국 국립표준기술연구소)가 발표한 암호화 해시 함수의 표준.

특징 : 

 

• 고정된 출력 크기: 입력 크기에 관계없이 일정한 크기의 해시 값 생성(SHA-256은 256비트).
• 충돌 저항성: 서로 다른 입력이 동일한 해시 값을 생성하지 않도록 설계.
• 원웨이 방향성: 해시 값을 통해 원본 데이터를 역추적할 수 없음.
• 고속 처리: 효율적인 연산 성능 제공.

 

Hashable

Hashable은 Swift 표준 라이브러리에 포함된 프로토콜로, 객체를 해싱 가능한 데이터로 변환할 수 있도록. 해싱은 데이터를 정수 형태의 해시 값(hash value)으로 변환하는 과정.

Hashable을 채택한 타입은 다음 조건을 만족해야함:

• Hashable 객체는 반드시 고유한 해시 값.
• 같은 객체는 항상 동일한 해시 값을 반환해야 한다.

Equtable

Hashable은 Equtable프로토콜을 상속받고 있다. 해당 이유로는 항상 unique하지 않기때문! 이는 두 객체의 값이 같으면 해시 값도 같아야 함을 보장한다. 또한 고유한 key값을 가져야하기에.

Hashable이 필요한 이유

1. Dictionary의 Key
   딕셔너리에서 키는 고유해야 하며, 빠르게 값을 검색하려면 해싱이 필요하다
2. Set의 원소
   집합은 중복을 허용하지 않으므로 요소의 고유성을 보장하기 위해 Hashable이 필요

해당 이유로는 Dictionary, Set이 해시방식으로 구현이 되어있기 때문이다. 그래서 검색, 추가, 삭제가 O(1)이다.

hashable 프로토콜을 채택하면 구현해야 하는 필수 메서드다. 요소들의 값을 주어진 hasher에 전달해서 해싱하는 함수.

hasher: 해시 값을 계산하기 위한 Hasher 타입의 inout 매개변수.

Hasher는 Swift에서 해시 값을 계산하는 내부 도구
이 구조체는 주어진 값을 해시 값을 생성합니다.

Hasher의 특징

1. 보안성
   • Hasher는 내부적으로 실행마다 달라지는 Seed 값을 사용하여 해시 값을 생성한다. 이는 동일한 데이터라도 앱 실행마다 다른 해시 값을 생성함으로써 보안을 강화한다.
2. 결합 기능
   • combine(_:) 메서드를 통해 여러 속성을 결합하여 하나의 해시 값을 만든다.
3. 해시 값 반환
   • finalize() 메서드를 호출하여 최종적으로 정수 타입의 해시 값을 반환

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

    func hash(into hasher: inout Hasher) {
        hasher.combine(name) // 속성 1: 이름
        hasher.combine(age)  // 속성 2: 나이
    }
}

let john = Person(name: "John", age: 30)
let hashValue = john.hashValue

이름과 나이속성을 해시 계산에 추가한거다. 모든 속성을 결합 후 Hasher는 최종적으로 하나의 정수 해시값을 반환한다.

1. Hashable 프로토콜을 채택해 원하는 형태를 Hashable하게 한 후 

2. 타입 내부에 hash(into: )메서드 구현해서 Hasher타입 hashFunction에 추가적인 값 제공하고 해싱한다.

3. 결과값으로 정수의 Hash를 얻게됨.