Hash Value

Hash와 Hash Table

해쉬값을 이해하기 위해선 Hash와 Hash Table에 대한 이해가 먼저 필요하다

Hash Table

Key라는 것을 해시 함수를 이용해 해시 주소값(해시 테이블의 index)으로 바꾸고,해시 주소값(해시 테이블의 index)를 통해 해시 테이블에 접근하여 값을 가져오거나 저장하는 형태임

이게 뭔 소리야?

• 만약 아래 그림에서 희재 - 0, 석우 - 1, 서린 - 2 이런식으로 저장되면 이건 그냥 일반 배열과 다름이 없겠지?
  
• Key를 통해 해시 테이블의 index를 알 수 있어야만, 해당 Value에 접근이 가능하다
• 해당 Key에 상응하는 index는 항상 동일하게 나와야함
• 해시함수는 Key에 대한 산술 연산을 이용하여 해시 주소값(해시 테이블의 index)으로 만들어주는 것!

why hash?

해시는 값의 검색 속도가 빠르다. 원래는 처음부터 순서대로 값을 찾아야 한다. 반면, 해쉬 테이블에서는 해쉬값을 index로 사용하여 원하는 값의 위치를 한 번에 알 수 있다.

하지만 충돌 문제를 해결하기 위해 저장공간을 넓게 잡아서 공간 복잡도는 커진다..

장점	단점
1. 데이터 저장, 읽기 속도가 빠르다	1. 일반적으로 저장공간이 많이 필요하다
2. 키에 대한 데이터 중복 확인이 쉽다	2. 충돌이 발생 시 해결하기 위한 별도의 자료구조가 필요하다

그래서 해시는 저장, 검색, 삭제 등 탐색을 많이 하는 경우나 캐쉬를 구현하는 경우 많이 사용된다.

Hash Value(해쉬값) ?

원본 데이터를 특정 규칙에 따라 처리하여 간단한 숫자로 만드는 것

• 정확히 원본 데이터 (객체)를 해쉬 함수를 사용하여 64bit의 Int 값으로 변환한것
• 2개의 데이터를 비교할 때, 데이터가 동일하면 각 데이터의 해쉬값도 동일
• 하지만 데이터가 조금이라도 다르면, 완전히 다른 해쉬값
• 코드를 컴파일 및 실행할 때마다 모든 해쉬값이 변경됨!

let hi: String = "히디 안녕?"
let hello: String = "히디 안녕?"
let hihello: String = "잘생긴 히디 안녕?"

print(hi.hashValue) // 2897129375192192 (예시)
print(hello.hashValue) // 2897129375192192 (예시)
print(hihello.hashValue) // 1239591329282384

Hashable?

이게 뭔 소리져...?

Set에 어떤 값을 저장하고 싶다면, "해당 값의 타입은 Hashable 해야한다"

- Hashable 해야 한다는 것은 Hashable Protocol을 준수한다는 의미이다!
- Hashable 한 타입의 데이터는 해쉬값을 구할 수 있다!
- Hashable은 Equatable의 상속을 받으므로 연산자 '==' 사용 가능

struct Sopt: Hashable {
	let name: String
    let part: String
    let appJam: Bool
}

struct Soap: Hashable {
	let string1: String
    let string2: String
    let random: Bool
}

let hidi = Sopt(name: "hidi", part: "iOS", appJam: true)
let partJang = Sopt(name: "hansol", part: "iOS", appJam: true)

// 구조체가 Hashable Protocol을 준수하므로 == 연산자로 비교 가능
if hidi == partJang {
	print("영광입니다~!")
} else {
	print("아직 부족합니다 ㅠ")
}

let soap = Soap(string1: "hidi", string2: "iOS", random: true)

// 다른 객체이지만, 동일한 해쉬값을 가진다! (해쉬값 충돌)
print(hidi.hashValue) 
print(soap.hashValue)

if hidi == soap // 컴파일 에러: 객체의 타입이 다르므로 연산자 사용 불가