해시 (Hash)

Yejung·2022년 9월 30일

목록 보기

1/1

자료구조를 배우는 이유는 원하는 값을 최대한 효율적으로 찾을 수 있도록 여러가지 저장구조를 배우는 것 이라고 한다

해시란 데이터를 다루는 기법 중 하나이다. 블록체인을 공부할 때 잠깐 들어보았던 개념이다.

리소스가 많이 필요하지만 검색 속도가 빠르다는 장점이 있다. 해시코드로 연산을 거쳐 인덱스를 결정하므로, 데이터 검색 시 위치 검색이 필요 없고 해시코드 자체로 바로 데이터의 위치 파악이 가능하다.

해싱 (Hashing)

키(데이터) ➡ 해시 함수 ➡ 해시 값 / 해시 코드 ➡ 배열 인덱스로 환산 ➡ 해시 테이블에 넣기

이와 같은 일련의 과정을 해싱 이라고 한다.

이 때 키는 문자열, 숫자, 파일 데이터도 될 수 있다!

데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

입력한 키 값이 동일할 때 무조건 같은 해시 값을 return 한다. 이 때 반환되는 해시 값(해시 코드)는 integar 이다.

키(데이터)와 배열의 인덱스(index)를 이용하여 키를 저장하는 자료구조이다.

해시 테이블은 키를 해시 함수로 계산하여 그 값을 배열의 인덱스로 사용한다. 즉, 키를 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다.

해시 테이블을 사용하려면 우선 고정된 크기의 배열을 선언해야한다. 이것은 저장공간(bucket)을 지정해야 하므로 저장공간이 많이 필요하다는 단점이 된다.

충돌이 일어나지 않는다는 가정 하에 데이터 삽입, 삭제, 검색 시 시간복잡도는 O(1)이다. 따라서 데이터 삽입, 삭제, 검색이 많이 필요한 경우에 자주 사용된다!

해시 테이블을 만들다보면 충돌이 일어나는 경우가 있는데 그 경우를 알아보자.

different keys ➡ same hash code
다른 데이터 값이 해시 함수에 의해서 같은 해시 코드를 가지는 경우이다. 배열 index로 환산하는 과정에서도 결국 같은 index를 가지게 되므로 해당 index의 bucket에서 충돌이 일어난다.
different hash code -> same index
다른 해시 코드가 배열 인덱스로 환산되는 과정에서 같은 인덱스를 가지는 경우이다. 이 경우도 데이터를 저장하는 과정에서 충돌이 일어난다.

seperate chaining
- 해시 충돌이 발생했을 때 이를 동일한 bucket에 저장 하되 나중에 저장되는 값을 연결리스트(linked-list) 형태로 저장한다.
- Chaining 을 통해 hash table 을 생성하였을때 기능들의 시간복잡도는 O(n) 까지 늘어날 수도 있다는 단점이 있다.

Open Addressing (Close hasing)
- 해시 충돌이 일어날 경우, 비어있는 hash를 찾아 데이터를 저장하는 기법이다.
- 이때, 비어있는 hash 를 찾는 방법으로 단순히 한칸씩 옆으로 옮기며 빈 공간(bucket) 를 찾아가는 linear probing 방법이 있다.
- 이러한 linear probing 방법을 사용하면 데이터들이 특정 위치에만 밀집하는 clustering 문제가 발생할 수 있다.
- 이 문제를 해결하기 위해 n^2 을 건너뛰어 빈 공간(bucket) 를 찾아가는 quadratic probing 방법도 있다.

참고자료

이것저것... 차곡차곡...