Hash

사전적 의미 : 주어지는 임의의 길이의 임의 데이터를 사전에 정의한 길의의 데이터로 매핑하는 것.

해시 함수 : 일련의 알고리즘을 통해 입력된 데이터를 고정길이 데이터로 매핑하는 함수.

 

사용되는 자료구조 : 해시 맵, 해시 셋

(c++11 이전에는 hash_map, hash_set으로 포함되어있었으나 이후부터 unordered_map, unordered_set으로 변경되었다.)

 

함수에 사용되는 대표적인 알고리즘으로는 MD5, SHA계열 등이 있다.

암호화에도 사용될 수 있다.

 

작동방식

0~n개의 데이터 저장용 리스트를 만들고, 입력된 데이터에 대해 해시 함수를 적용한뒤, a 라는 값이 index로 생성되면, 저장용 리스트의 a index 위치에 데이터를 저장하는 방식.

 

데이터 저장시에 해시값이 겹치는 경우를 '충돌' 한다고 이야기한다.

이 경우, 두가지 방식으로 해결하는데, 개별 체이닝(separate chaining) 과 오픈 어드레싱(open  addressing)이 있다.

 

개별 체이닝(separate chaining)의 경우, 충돌이 발생하면 같은 index값을 먼저가진 값 뒤로 리스트 연결을 하는 방식.

 

오픈 어드레싱(open  addressing)의 경우, 저장용 리스트의 가장 가까운 빈공간을 찾아서(중복된 index 뒤쪽으로만 찾음.) 데이터를 삽입하는 방식. 

 

개별 체이닝의 경우는 무한정 새로운 해시값을 지정해서 추가할수 있지만, 오픈 어드레싱의 경우, 처음 지정한 리스트 길이를 넘어가는 해싱을 불가능하다. 

 

키 : 해시함수로 입력하는 데이터.

해시함수 : 키를 입력받아 알고리즘을 통해 index를 만들어낸다.

버킷 : 키의 값을 index 위치에 저장.

 

구현 : 개별 체이닝식

필요 클래스 : Node, Bucket, HashTable

데이터를 저장하기 위한 리스트에 필요한 Node

해시 함수를 통해 생성될 인덱스로 저장할 Bucket
삽입, 삭제, 해시 함수를 담은 HashTable

삽입 함수 : 

1. 해시함수를 통해 키를 인덱스로 변환.

2. Bucket에서 인덱스를 통해 위치 확인.

3. 입력된 키,값을 Node로 생성.

4. 충돌체크 : 찾은 위치의 Bucket이 비어있는지 체크.

4-1. 충돌 안했을때 : Bucket에 Node를 삽입.

4-2.  충돌시 : 현재 Bucket의 Node에 빈 노드(끝노드)까지 이동해서 삽입.

 

삭제 함수 : 

1. 해시함수를 통해 키를 인덱스로 변환.

2. Bucket에서 인덱스를 통해 위치 확인.

3. Bucket이 없으면 삭제 취소. 있으면 진행

4. Bucket의 Node를 순차적으로 확인 ㄱㄱ

5. Node의 키와 입력된 키값이 같은지 && 다음 Node가 있는지 체크.

5-1. true로 넘어오면 Node 땡기고 삭제.

6. 키만 같고 끝 노드일경우

6-1. Bucket 자체를 삭제.

7. 키가 다를때

7-1. 다음 Node 가 있다면 키가 같을때까지 노드를 넘겨본다.

7-2. 키가 같은데 다음노드가 있으면 땡기고 삭제 

7-3. 키가 같은데 다음노드 없으면 삭제.

7-4. 다 돌때까지 키가 같지 않다면 반복문 박살.

 

해시함수 : 

원하는 알고리즘으로 입력된 키를 변환해 bucket의 인덱스로 만든다.