[Data Structure] Hash

 

해싱 정의

키(key) 값에 직접 산술 연산을 적용하여 해시 테이블 주소를 통해 값(Value)에 접근하는 것

 

해시 테이블 (Hash Table)

key 값의 연산에 의해 직접 접근이 가능한 자료구조

Dictionary == Map == Table

사전(Dictionary) 자료구조는 Key - Value를 갖는 자료구조로

오로지 키에 의해 값에 접근한다.

(키가 정렬되었는지 여부는 구현시 결정 가능하다.) // 별로 중요하지 않다.

 

ex) 사람 이름(key) - 전화번호(Value) 

 

필수 연산은 다음과 같다.

• Insert
• Delete
• Search

이런 사전 자료구조 (Dictionary)를 효율적으로 구현하기 위해 해시 알고리즘을 적용한다.

---

해시 함수

해시 함수 그림 표현

키를 입력하여 해시 주소를 얻어낸다. 해시 주소는 해시 테이블의 인덱스로 쓰인다.

해시 함수의 조건은 다음과 같다.

1. 충돌 최소화
2. 빠른 계산
3. 값이 해시 테이블 내에 고르게 분포

 

충돌 (Collision)

서로 다른 키에 대해 해시함수를 적용한 결과 해시주소가 같은 경우이다.

HashFunction(Key1) == HashFunction(Key2) // Collision

충돌이 발생하면 버켓에 더 이상 값을 저장할 수 없게되는 Overflow가 발생한다.

 

첫글자를 Hash Address (Index)로 사용하는 해시 테이블을 살펴보자 6 * 5

Slot이 총 5자리 일때, Overflow가 'C' Bucket의 6번째 슬롯에서부터 발생한다.

---

Open Addressing

 

Time Complexity

m: number of slots in hash table

n: number of keys to be inserted in hash table

=> 무조건 slot 수가 총 input data 수 보다 많다! (당연.. 안그러면 overflow!)

 

Load Factor α = n/m ( < 1 )

Search / Insert / Delete  < 1 / (1-α)

 

∴ O( 1/ (1-α) )

 

 

암호화 해시

다음 4가지 성질을 만족하는 해시를 암호화 해시 (Cryptographic Hash) 라고 한다.

 

1. Easy
   유한한 길이 메시지 m이 주어졌을 때 그 메시지 관한 해시 계산이 매우 간편해야함.
   $$ h = H(m), h는 고정된 길이 $$
2. Pre-image resistance
   해시 이전의 복원된 값 메시지 (m)을 찾을 수 없어야함. (일방향 함수의 성질)
   $$ h = H(m), m을 찾을 수 없음. $$
3. Second pre-image resistance
   해시값으로부터 동일한 해시값을 갖는 또다른 메시지 m` 을 찾을 수 없어야함.
   $$ h = H(m) = H(m`) , m`$$ 을 찾는 것이 불가능해야함
4. Collission resistance
   동일한 해시값을 갖는 메시지 쌍 (m, m`)을 찾을 수 없어야함.
   $$ m != m`  \,\&\&\,  H(m) = H(m`) $$  // 동일 해시값을 갖는 메시지 쌍 찾기가 불가능해야한다.
   
   

※ 통상 문제 해결에 지수 시간이 소요될 때 저항성이 커지며 불가능에 가까워진다고 한다.

 

---

🔗 Reference

서적 - 비트코인과 블록체인, 가상자산의 실체 2/e