[CS] 자료구조 - HashMap

hash

1) 정의
데이터를 다루는 기법으로 Hash 값이란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑 한 값이다.
2) 특징

• Hash 를 통한 데이터 저장 시 에는 검색과 저장이 아주 빠르게 진행된다. 이유는 데이터를 검색할 떄 사용할 key와 실제 데이터의 값이(value) 한 쌍으로 존재하고, key 값이 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1) 에 수렴하게 된다.
• 해시는 특정한 데이터를 상징하는 고정된 길이의 데이터로 변환하게 된다. 여기서 상징 데이터는 원래의 데이터가 조금만 달려져도 확연하게 달라지는 특성을 가지고 있어 무결성을 지키는데에 많은 도움을 준다. EX) 'A'라는 문자열의 해시와 'B'라는 문자열의 해시는 고작 한 알파벳이 다를뿐 이지만 해시 결과값은 완전히 다른 문자열이 나오게 된다. (무결성 보장)
• 해시는 기본적으로 복호화가 불가능 하다는 특징이 있다. 이는 당연히 입력 데이터 집합이 출력 데이터 집합을 포함하고 있으므로, 특정한 출력 데이터를 토대로 입력 데이터를 찾을 수 없기때문이다. (보안성)

hashMap

1) Map 의 구현체로 배열과 해시 함수(hash function)을 사용하여 map을 구현한 자료구조

Map이란? 
key-value pair들을 저장하는 ADT(Abstract Data Type)
같은 key를 가지는 pair는 최대한개만 존재. value는 중복이 됨
associative array, dictionary 라고 불리기도 함
Map의 구현체로 hash table 과 tree-based가 있다.

2) 배열로 구현되어 있으며 배열의 장점은 곧 HashMap 의 장점이 된다. 장점으로는 데이터 사이즈 상관없이 아주 빠른 속도로 처리 가능하다. 즉, 삽입, 삭제, 갱신, 탐색 이 상수 시간에 처리된다. -> O(1)

<-> O(n) : n 은 데이터 사이즈 로 삽입,삭제,갱신,탐색 이 데이터 사이즈에 정비례하여 오래 걸린다.

3) 많이 접근하는 데이터 위주로 메모리 상에 올리면 사용율 상으로 이득을 볼 수 있다. (캐싱과 유사)
4) HashTale

• 두 자료구조 모두 Map의 구현이고 둘 다 Key - Value 형태로 데이터를 저장한다
• 차이점

	HashMap	HashTable
Null 허용	O	X
동기화 보장	X	O
쓰레드	싱글쓰레드 적합	멀티쓰레드 적합
성능 속도	1등	2등

hash function

1) 정의

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터(hash) 로 변환하는 함수
• key를 index로 변경해주는 역할을 하는게 hash function 이다.

HashFuction(key) % [map_capacity] = index

• 배열은 index가 양의 정수를 갖기 때문에 hashmap에서 어떤 key가 오는 hashfunction을 통하여 index를 바꿔주어 적절한 위치에 넣어 주도록 하는게 hashMap이다.
• 데이터의 원사이즈는 크지만 실제 배열의 사이즈는 원사이즈보다 작으니 충돌 가능성이 있다.
• key가 같을 경우 기존에 있던 key의 bucket에 덮어 씌어진다.
• hash function의 완성도에 따라서 충돌 가능성을 낮춘다.

해시충돌 (hash collision)

1. 발생원인
   key는 다른데 동일한 index bucket에 저장되어 충돌이 발생한다. 즉, hash % map_capa 결과인 index가 같을 때 발생 한다.

2. Separate Chaining
   1) 추가적인 활용하여 해결하는 방식
   2) Linked List를 사용
   EX) Key == Value 가정
   hf(100) % 10 = 1

3. Open addressing(개방 주소법) : 충돌 발생 시 인접한 비어있는 공간에 저장
   추가적인 메모리 공간을 사용하지 않고 이미 확보된 공간만을 이용하여 해결하는 방식
   1) Linear Probing(선형 탐색) : 고정폭으로 이동하여 빈공간을 찾음

• 충돌 시 공식

hf_lp = hf(key) + i
* 충돌 횟수 i = 0,1,2

• 맨 처음에는 충돌이 발생하지 않아 hash값을 알기 위해서 i = 0 으로 연산

2) Quadrattic probing(제곱 탐색) : 제곱 수로 이동하여 빈 공간을 찾음

• 충돌 시 공식

hf(key, i) = hf(key)+i^2 or hf(key)+i^2*a(임의의 상수)
* 충돌 횟수 i = 0,1,2

• 맨 처음에는 충돌이 발생하지 않아 hash값을 알기 위해서 i = 0 으로 연산
• 클러스터링이 클러스터링(군집현상)이 두부분으로 나눠지고 충돌이 발생하는 시점이 Liner Probing 와 동일하지만 비교 횟수가 앞에 비해서 상대적으로 줄어들어서 군집 현상, 클러스터링이 발생한 공간에 빠졌을때 빨리 탈출하기 위해 제곱을 사용

3) Double Hashing(이중탐색)

• 충돌 발생할때 전혀 다른 hf을 사용하여 hash값을 구하면 저장된 bucket이 더 퍼트려진다.
• 서로 다른 key라도 hf 넣어서 나온 값이 같으면 아무리 충돌 횟수를 늘려도 같은 위치를 확인할 수 밖에 없다.

hf_dh(key,i) = hf(key)+i*2nd_hf(key)
* 충돌 횟수 i = 0,1,2..

• 주의 점으로 2nd_hf(key) 의 값이 map 사이즈로 서로소여야 한다는점. 그렇게 하지않으면 한번도 접근하지 못하는 공간이 발생한다. map의 사이즈가 10이라고 치고 2nd_hf(key)에서 key값이 4이고 1nd_hf 같은 key를 넣어서 0이 나올 때
  EX)
  hf_dh(key,i) = 0+ix4= 4i
  값이 최종적으로 4,8,12,16.. 4의 배수가 되는데 모듈러 연산을 하면 4 8 2 6 0 4 8 .. 으로 충돌횟수가 늘어도 다른 인덱스 공간에 한번도 접근하지 않는 현상이 발생한다.

재해싱 (Rehashing = hash table resizing)

• Java 기준으로 데이터가 75% 이상 차면 2배로 map_capacity가 2배로 늘어난다.
• 늘어난 만큼 기존에 있던 bucket에 들어있던 hash값을 이용하여 map_capacity 만큼 모듈 연산을 하여 재해싱이 진행된다.