[Data Structure] Hash

이 포스팅은 세미나를 위해 
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다.

출처: https://yourbasic.org/algorithms/hash-tables-explained/

Hash Table

• hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다.
• hash function을 사용하여 저장할 데이터과 연관된 고유한 숫자(hashcode)를 만들어 이를 인덱스로 사용한다.
• 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입, 삭제 연산 시 shift 연산의 추가적인 비용이 없도록 만들어진 구조이다.

Hash Function

• 저장되는 값들의 key 값을 hash function을 통해 작은 범위의 값들로 바꿔준다.
• 적절한 hash function을 사용하여 고유한 인덱스 값을 만드는 것이 중요하다.
• 동일한 key 값의 다수의 데이터가 동일한 인덱스를 가지면 collsion이 발생한다.
• Collision: 서로 다른 두 개 이상의 키가 같은 인덱스로 hashing되는 문제

좋은 hash function의 조건

• hash function은 무조건 1:1로 만드는 것보다 Collsion을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 더 중요하다.
• 1:1 대응으로 만드는 것이 거의 불가능하기도 하지만 그런 hash function을 만들 경우 array와 다를 바가 없으며 메모리를 너무 많이 차지하게 된다.
• hashing된 인덱스에 이미 다른 값이 들어 있다면, 새 데이터를 저장할 다른 위치를 찾아야 한다.
  이 과정을 최소화하는 것이 hash 성능에 중요하다.

Resolve Conflict

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

• Collision이 발생하면(삽입하려는 해시 버킷이 이미 사용 중인 경우), 다른 해시 버킷에 데이터를 삽입하는 방식
• Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.

구현 방법

1. Linear Probing: 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
2. Quadratic probing: 2차 함수를 이용해 탐색할 위치를 찾는다.
3. Double hashing probing: 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.

2. Seperate Chainig 방식 (분리연결법)

• Collision이 발생하면 해당 해시 버킷에 데이터를 추가로 삽입하는 방식
• 일반적으로 Separete Chaining 방식이 Open Address 방식보다 빠르다.
  Open Address 방식의 경우 해시 버킷을 채운 밀도가 높아질수록 worst case 발생 빈도가 높아지기 때문이다.
• Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.

구현 방법

•  연결리스트를 사용하는 방식(Linked List): 각각의 버킷들을 연결리스트로 만들어 Collision이 발생하면 해당 버킷의 리스트에 추가하는 방식
  • 장점: 연결리스트로 구현되므로 삽입, 삭제가 간단하다.
  • 단점: 데이터를 삽입, 삭제하기 위해서 탐색하는 시간이 버킷 갯수만큼 들며, 다음 버킷의 주소를 저장하기 위한 데이터가 추가적으로 필요하다.
• 트리를 사용하는 방식(Red-Black Tree): 각각의 버킷들을 트리로 만들어 Collision이 발생하면 해당 버킷의 트리에 추가하는 방식
  • 장점: 데이터를 탐색하는 시간이 연결리스트를 사용하는 방식에 비해 빠르다.
  • 단점: 연결리스트를 사용하는 방식에 비해 메모리 사용량이 크다.
• 데이터 갯수가 적다면(6개 이하), 연결리스트를 사용하고 데이터 갯수가 많다면(8개 이상), 트리를 사용한다.

---

Reference

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure