22.05.17 해시

https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C

[알고리즘] 해시(Hash)

https://yjshin.tistory.com/entry/%EC%95%94%ED%98%B8%ED%95%99-%ED%95%B4%EC%8B%9C-%ED%95%A8%EC%88%98-%EC%9E%91%EC%84%B1-%EC%A4%91

[암호학] 해시 함수, 해시 알고리즘, 해시 충돌, 해시 자료구조

https://hsp1116.tistory.com/35

해쉬 알고리즘(Hash Algorithm) 요약 정리, 테스트 코드

 

 

https://hee96-story.tistory.com/48

[자료구조] Hash/HashTable/HashMap

 

 

해시 : 데이터를 다루는 기법 중 하나, key-value 형태로 데이터 존재, key값이 배열의 인덱스로 저장되어 검색과 저장을 아주 빠르게 하는 자료구조. 해시 충돌이 발생할 수 있음에도 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있기 때문이다. ex 하드디스크나 클라우드에 존재하는 무수히 많은 데이터(key)들을 유한한 개수의 hash value로 매핑함으로서 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있음.

 

크게 해시, 해시 함수, 해싱, 해시 테이블 4가지의 구성요소가 있다.

 

key : 매핑 전 원래 데이터의 값

hash value : 매핑 후 데이터의 값

hash table : 해시 값 + 데이터의 인덱스

hashing : 매핑하는 과정을 일컫는 말

 

해시 테이블 : 연관 배열구조를 이용해 데이터를 key와 value로 저장하는 자료구조. 해시 함수를 이용하여 인덱스를 bucket(버킷)이나 slot(슬롯) (=연관된 value가 저장되는 공간)의 배열로 계산한다. 

 

연관 배열 구조 : 자료 구조의 하나로, key 하나와 value 하나가 연관되어 있으며 key를 통해 연관되는 값을 얻을 수 있다.

연관 배열은 다음의 명령을 지원한다.

- key와 value가 주어졌을 때, 연관 배열에 그 두 값을 저장

- key가 주어지면 연관되는 value를 얻는 명령

- key와 새로운 value가 주어졌을 때, 원래 key에 연관된 value를 새로운 value로 교체하는 명령

- key가 주어졌을 때 그 키에 연관된 value를 제거하는 명령.

해시의 장단점

장점 : 1. 중복 제거 가능, 2. 데이터 캐싱,보안에 좋음, 3. 배열의 인덱스로 접근하기 때문에 삽입,삭제가 빠름

단점 : 1. 공간복잡도가 큼, 2. 충돌 발생 가능(충돌이 발생하면 시간복잡도는 O(n)에 가까워짐), 3. 순서가 있는 배열에는 좋지않음.

 

해시테이블 vs 해시맵

해시테이블과 해시 맵의 가장 큰 차이는 동기화 지원 여부와 null 허용이다(java)

 

Direct Address Table

기본적인 해시 테이블. key 개수 = hash table 크기의 수여서 충돌이 일어나지 않음.

그러나 전체 키의 갯수는 10개(K+U)이나 실제 사용하는 키는 K개 이므로, 사용할 떄 사용하지 않는 키들을 위한 공간까지 마련해야 됨(0,1,4,6,7,9 버킷) 그래서 메모리 효율성이 떨어짐.

-> 실제로는 충돌이 나더라도 해시 테이블 크기가 실제 사용하는 키개수보다 적은 해시테이블을 운용함.

 

 

충돌

서로 다른 문자열이 해시 함수를 통해 해싱한 해시값이 중복인 경우.

충돌이 많아질 수록 탐색의 시간복잡도가 O(1) -> O(n)이 된다.

 

충돌 해결 방법

1 Separating Chaining - Linked List, Tree(Red-Black Tree)

2 Open Addressing - Linear Probing, Quadratic Probing, Double Hashing

 

1 Separating Chaining

- JDK 내부에서 사용하는 방법. Linked List (data가 6개 이하)또는 레드블랙트리(data가 8개 이상)를 사용. 7개인 경우 데이터를 삭제하면 linked list로 바꾸고, 추가되면 트리 사용. 

- 한 버킷당 들어갈 수 있는 엔트리 수에 제한을 두지 않는 해시테이블.

Linked List를 사용할 경우 인덱스 충돌이 났을 때 index가 가리키고 있는 linked list에 노드를 추가하여 삽입한다.

탐색 : 데이터를 탐색할 떄는 key(Sandra Dee, John Smith)에 대한 인덱스(152)가 가리키고 있는 Linked List를 선형검색하여 해당 키에 대한 데이터를 반환한다. 

삭제 : key에 대한 인덱스가 가리키는 Linked List에서 그 노드를 삭제

-> Separate Chaining 방식은 Linked List 구조를 사용하기에 추가할 수 있는 데이터 수의 제약이 적다.

 

 

2. Open Adressing

- 인덱스에 대한 충돌 처리에 대해(key가 두개 이상이 한 인덱스로) Linked List와 같이 추가적인 메모리를 사용하지 않고 Hash Table Array의 빈 공간을 활용하는 방법. 추가 메모리를 쓰지 않기에 Separate Chaining 에 비해 메모리를 덜ㄷ 사용한다.

- 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 헤시테이블.

- Linear Probing, Quadratic Probing, Double Hashing 등이 있으며 그 중 Linear Probing의 예시를 보자.

인덱스가 중복되는 충돌이 발생할 떄 인덱스 뒤에 있는 버킷 중 빈 버킷을 찾아 데이터를 삽입. 그림에서 Sandra의 키 값의 인덱스는 152를 가리키나 John과 충돌이 나기 때문에 그 다음인 153으로 삽입시키는 것이다.

 

탐색 : Sandra 키에 대해 검색을 하면 index가 152이기 때문에 key가 일치하지 않기에 뒤의 index를 검색해서 같은 key가 나오거나 key가 없을 때까지 검색을 진행.

삭제 : 더미 노드를 넣어서 검새개할 때 다음 인덱스까지 검색을 연결해주는 역할을 해야 함. (삭제가 어렵다)

 

Resizing (리스트 크기 재배열)

- Separate Chaining : 버킷이 일정 수준으로 차버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나서 검색 성능이 떨어짐. 버킷의 갯수를 늘려줘야 한다.

- Open Addressing : 고정 크기 배열을 사용하기에 데이터를 더 넣기 위해서는 배열을 확장해야 함.

- 보통 2배로 확장하는데, 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때. (0.75 = load factor)

- 리사이징은 더 큰 버킷을 가지는 array를 새로 만든 다음, 기존 array의 hash를 다시 계산해서 복사해줘야 함.

-> 비용이 많이 든든 작업.. 실시간으로 빠른 처리를 요하는 환경에서는 무리

 

해시 테이블 확장 방식

- 큰 리스트를 하나 더 만들어서 적당한 타이밍에 몇 개씩 점진적으로 옮기다가 다 옮기면 기존의 테이블을 없애 확장하는 방식

- 단 메모리를 많이 사용하게 된다.

 

Consistent Hashing 

- 해시의 비트 수를 늘림.

- 항목 수가 적을 떄는 짧은(적은 비트수) 해시와 작은 저장공간을 사용하다가 충돌이 많아지면 비트 수를 1비트로 늘리고 저장공간도 2배로 늘림.

- 그 다음 항목을 점진적으로 확장된 공간으로 이전하게 함으로서 충돌을 줄임.

- 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 사용됨.

 

해시 함수를 이용해 충돌 방지

- 해시 테이블 크기가 m이라면 좋은 해시함수는 임의의 key를 임의의 해시 value에 매핑할 확률이 1/m이다. (충돌나지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수!)

 

해시 함수 종류

- 나눗셈법(나머지 연산법) : 숫자로 된 key를 해시테이블크기 m으로 나눈 나머지를 해시 value로 반환. m은 소수 사용, 2의 제곱수와 먼 소수를 사용하는 게 좋음.

 

- 곱셈법 : 숫자로 된 key K, 0과 1사이 실수 A를 사용해 아래 식으로 진행. m이 얼마가 되든 중요하지않고 보통 2의 제곱수, 나눗셈법보다는 느리지만 2진수 연산에 최적화된 컴퓨터 구조에 좋음

 

- Universal Hashing : 다수의 해시 함수를 만들고 해시함수 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법. H에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 key를 임의의 hash value에 매핑할 확률을 1/m으로 만드는 것이 목적.

 

해시테이블 vs 해시맵

Java에서 해시테이블과 해시맵의 차이는 동기화 지원 여부 뿐.

key에 대한 hash value를 사용하여 value를 저장, 조회하는 것은 해시테이블/해시맵은 동일

 

- 해시테이블 : 병렬처리 할 때 (동기화 고려), Null값 X

- 해시맵 : 병렬처리 하지않을 때(동기화X), Null값 O

 

해시테이블 (해시맵) 시간복잡도

- key가 배열의 인덱스로 변환되기 때문에 탐색,저장,삭제가 빠르다. 평균 시간 복잡도가 O(1)이다.

최악의 경우는 충돌 때문.