10. hash

1. Hash 

- hash 는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 속도가 빠름

- 특정한 값을 Search할때 데이터 고유의 index로 접근 하기에 평균의 시간 복잡도가 Big-O(1)된다

- Collision 때문에 항상 Big-O(1)은 아니다

- 특별한 알고리즘(hash function)을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 데이터의 index에 사용한다 

- 특정 데이터의 인덱스는 고유한 위치라서, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 연산 시 다른 데이터로 채울 필요가 없기 때문에 추가적인 비용이 들지 않는 자료구조이다

2. Hash function

- hash function에 의해 반환된 데이터의 고유의 숫자 값을 hashcode

- 어설플 hash function은 동일한 key값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는데 이것을 Collision 이라고 한다.

- Collision 이란 서로 다른 두개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 되는 것.

- hash function을 무조건 1:1로 만드는 것보다 Collision을 최소하하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응하는할 것 인가가 중요

3. Resolve Conflict

1. Open Address 방식 (개방주소법)

- 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식

- 버킷이란 데이터를 저장하기 위한 공간

- Collision이 발생하면 데이터 저장할 장소를 찾는다 Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.

- 비어있는 버킷을 찾는 방식에는 세 가지 방식이 있다

1. Linear Probing

- 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행

2. Quadratic probing

- 해쉬 함수를 2차 식으로 만든다

3. Double Hashing probing

- 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. Linear, Quadratic 방식들에 비해 연산량이 많다

2. Separate Chaining 방식 (분리 연결법)

- Open Addressing은 Separate Chaining보다 느리다.

- Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문

- Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워 지는 빈도를 줄일 수 있다 

- Separate Chaining 방식에느 두 가지 구현 방식이 존재

1. Linked List를 이용하는 방식

- 각각의 버킷들은 연결리스트로 만들어 Collision이 발생하면 해당 bucket의 list에 추가하는 방식

- 연결리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단

- 연결리스트의 단점인 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담

- 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블 확장을 늦출 수 있다

2. Tree를 이용하는 방식

- 연결리스트 대신 트리르 사용하는 방식

- 연결리스트를 사용할 것인가 트리를 사용할 것인가 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다.

- 이 key-value 쌍의 개수가 6개, 8개를 기준으로 결정한다. (6개 연결리스트, 8개 트리)

- 만약 기준이 6,7 이라면 6 -> 7로 될때 트리로 변경해야하고 다시 삭제한다면 연결리스트로 자료구조를 다시 변경해야 한다.

- 기준이 1이라면 Switching 비용이 너무 많이 필요하게 된다. 그래서 2라는 여유를 남겨두고 기준을 잡아준다.

3. Open Address vs Separate Chaining

- 두 방식 모두 Worst Case 에서 O(M)이다.

- Open Address 방식은 연속된 공간에 데이터를 저장하기 떄문에 Separate Chaining에 비해 캐시 효율이 높다.

- Separate Chaining 방식에 비해 Open Address 방식은 버킷을 계속해서 사용하기 때문에 Separate Chaining 방식은 테이블의 확장을 늦출 수 있다.

4. 보조 해시 함수

- 보조 해시 함수의 목적은 key의 해시 값을 변경하여 해시 충돌 가능성을 줄이는 것이다. Separate Chaining 방식을 사용할 때 함계 사용되며 보조 해시 함수로 Worst Case에 가까워지는경우를 줄일 수 있다

5. 해시 버킷 동적 확장(Resize)

- 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실 발생한다

- HashMap은 key-value쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다

- 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다

- 0.75라는 숫자는 load factor라고 부른다