[자료구조] Hash(해시)

해시란?

- Hash 혹은 HashTable은 키를 값에 매핑할 수 있는 구조인, 내부적으로 배열을 사용하는 자료구조입니다.

- 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변환시켜 저장

- 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array

- 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라 하고, 이때 사용하는 함수를 해시함수

- 해시값 자체를 index로 사용하기 때문에 평균 복잡도가 O(1)로 매우 빠르다

- 보안에서 가장 많이 사용됩니다.

 

해시 함수란?

- 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 테이터로 매핑하는 함수로, 해시 함수에 의해 얻어지는 값을 해시코드, 해시라 합니다.

 

해시 테이블

- 키와 값을 매핑해둔 데이터 구조입니다.

- 해시함수로 얻은 해키를 키로 활용하여 index로 사용하고, 해당 index에 데이터를 저정하여 효율적인 검색을 위해 사용됩니다.

- 동기화를 지원

- Key, value에 Null값을 허용하지 않음

- 적은 자원으로 많은 데이터를 효율적으로 관리

- 하드 디스크나 클라우드에 존재하는 무한한 데이터드을 유한한 개수의 해시값으로 매핑하여 작은 메모리로도 프로세스 관리가 가능

 

해시의 충돌 (Collision 현상)

- 데이터가 많아지면, 다른 데이터가 같은 해시 값을 가지게 되어 충돌이 발생하기도 합니다.

: 해시 테이블의 근본적인 문제는 결국 index의 충돌

 

충돌 해결 방법

1. Separate Chaining

- Key에 대한 index가 가르키는 자료구조를 LinkedList를 이용하는 방식

- index로 인해 충돌이 발생하면 그 index가 가르키는 LinkedList에 노드를 추가

 

** JDK 1.8의 경우엔 index 노드가 8이하면 LinkedList, 초과하면 트리 구조로 저장하여 탐색 성능을 개선

 

2. Open Addressing (개방주소법)

- 해시 충돌이 일어나면 다른 저장소에 데이터를 삽입하는 방식

1) 선형 탐색 : 해시충돌시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입

2) 제곱 탐색 : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터 삽입

3) 이중 해시 : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용

- 체이닝처럼 포인터가 필요없고, 저장한 메모리 외 추가적인 저장공간도 필요없음

- 삽입, 삭제시 오버헤드가 적음

- 저장할 데이터가 적을 때 더 유리함

 

** 실제 해시함수가 보안에 사용되는 예시인 HMAC SHA-256
http://sunphiz.me/wp/archives/1104

HMAC SHA-256 – Dog발자

[참고]

https://power-overwhelming.tistory.com/42

[자료구조/알고리즘] 해시(Hash) 란?

https://ablue-1.tistory.com/68

[자료구조] 해시(Hash)란 무엇인가

https://velog.io/@wupajw/%ED%95%B4%EC%8B%9C%ED%95%A8%EC%88%98%EC%99%80-%ED%95%B4%EC%8B%9C%EC%B6%A9%EB%8F%8C

해시함수와 해시충돌

https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data%20Structure/%5BData%20Structure%5D%20Hash(%ED%95%B4%EC%8B%9C).md 

GitHub - WooVictory/Ready-For-Tech-Interview: 💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간