[Algorythm-자료구조] 해시

1. 해시란?

 해싱 = 해시 맵 = 해시 테이블

같은 용어로 key를 활용하여 value에 직접 접근 가능한 구조이다. 정렬보다는 검색이 유용하다.

파이썬으로 치면 딕셔너리가 이에 해당한다.

 

2. 해시 함수란?

 해시와 해시테이블을 알기 전에 해시 함수라는 것을 알아야 한다.

자료구조를 배우는 이유는 원하는 값을 최대한 효율적으로 찾기 위해 여러가지 저장구조를 배우는 것이다.

데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각하여 저장해야 한다.

해시 함수는 key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 "해싱"이라고 말하기도 한다.

key를 해시라는 함수에 input으로 넣고output으로 나오는 것이 해시이다. 

 

3. 해시테이블?

 해시 함수를 사용하여 키를 해시 값으로 매핑하고, 해시를 주소 삼아 데이터의 값을 저장하는 자료구조를 해시테이블이라고 한다.

 

4. 충돌 문제가 있지만 해시 테이블을 사용하는 이유

1) 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있기 때문이다.

하드디스크나 클라우드에 존재하는 무한에 가까운 데이터를 유한한 개수의 해시 값으로 매핑하여 작은 크기의 캐시 메모리로도 프로세스를 관리할 수 있게 된다.

 

2) 항상 동일한 해시 값을 리턴하고, 해당 index만 알면 테이블의 크기와 상관없이 데이터에 아주 빠르게 접근 가능 O(1)의 시간이 걸린다.

 

5. 충돌을 해결하기 위한 방법

* 만약 A, B 두 가지 key가 있다고 하면, A와 B를 hash function을 이용해 hash값이 2로 똑같이 나왔다. 이러한 현상을 hash collision이라고 한다. 

 해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다. 해시 충돌은 필연적으로 나타날 수 밖에 없다.

 

1) 체이닝 : 연결리스트로 노드를 계속 추가하는 방식, 메모리 문제가 있다.

2) 선형 탐색 : 해시값에서 고정폭으로 건너 뛰어 비어있는 해시가 나오면 저장한다.

3) 제곱 탐색 : 해시값에서 고정폭이 아닌 1칸, 4칸, 9칸, 16칸 씩 뛰면서 빈 칸을 찾는다.

 

++

6. 블록체인에서 사용하는 해시함수

1) 해시함수란

 블록체인에서 말하는 해시함수도 위와 같이 같은 길이의 결과를 도출하는 일방향 함수를 말한다.

 

2) 가장 큰 특징3가지

 i) 특정 데이터는 단 하나의 고유한 해시값을 가진다. 따라서 원본 데이터가 완전히 같다면, 완전히 같은 해시값을 가진다.

 

ii) 원본 데이터의 일부라도 다르면 완전히 다른 해시값을 가진다. (공백, 점 등등)

 

iii) 해시값의 조합만 보고 원본 데이터를 유추하는 것은 거의 불가능하다.

 ex) 해시값: asdfq12as8fjv  , 원본 데이터: ??  

 

 

@참고문헌

https://go-coding.tistory.com/30

https://startup-in-seongudong.tistory.com/25