[자료구조]해시테이블, hash function

Hash Table

---

Key와 Value를 1:1로 연관지어 저장하는 자료구조 (연관배열 구조)

왜 필요한가?(장점)

• 예를 들어 key : 이름, value : 전화번호의 자료를 저장할 때 특정 이름으로 전화번호를 찾으려면 배열에서는 선형탐색(O(n))을 해야 함
• 해시테이블을 이용하면 특정 이름(키)로 자료를 찾을 때 O(1)로 찾을 수 있음
• 배열의 인덱스를 사용하기 때문에 빠른 검색, 삽입, 삭제 (O(1))

작동 방식

• 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용
• Key -> Hash Function -> Hash Function 결과 = Hash
• 예를 들어 크기 5인 해시테이블에 자료를 저장할 때 키 -> 해시함수 -> 해시값 % 5 를 이용해 인덱스 계산해 자료를 저장함

단점

• 충돌 발생 가능성, 공간 복잡도
• 충돌(Collision) : 서로 다른 두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)

Resolve Conflict

---

• 일반적으로 Open Addressing 은 Separate Chaining 보다 느리다.(해시 버킷을 채운 밀도가 높아질수록 워스트케이스 발생 빈도가 더 높아짐)
• 하지만 Open Address방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다.

Open Address 방식 (개방주소법)

• 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식(다음 후보가 될 주소, 배열 상의 위치를 구해서 거기에 저장)
• 해당 주소에도 데이터가 존재하면 다음 후보 주소를 구해 빈 곳을 찾을 대까지 주소를 계속 구함
• 순차적으로 탐색하거나 2차해시함수 등을 활용

Separate Chaining 방식 (분리 연결법)

• 연결 리스트를 사용하는 방식(Linked List): 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식, 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담
• Tree 를 사용하는 방식 (Red-Black Tree) : 메모리 측면을 봤을 때 데이터 개수가 적을 때는 연결리스트 사용
• 데이터가 많아지면 연결리스트에서 원하는 키의 데이터를 찾을 때 탐색시간이 오래걸린다(해쉬테이블의 장점이 사라짐)

기타

---

보조 해시 함수

• 보조 해시 함수(supplement hash function)의 목적은 key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다.
• Open Address방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다.
• 따라서 데이터의 개수가 충분히 적다면 Open Address방식이 Separate Chaining보다 더 성능이 좋다.

해시 버킷 동적 확장(Resize)

• 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다.
• 그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다.

---

해시함수

• SHA 알고리즘 : secure hash algorithm, sha-0 폐기, sha-1, sha2(SHA-224, SHA-256, SHA-384, SHA-512 등, 뒤엔 비트수)
• SHA-1 : 최대 264비트의 메시지로부터 160비트의 해시값을 만들어 냄, 해쉬 충돌 발생, 입력 메시지는 MD5와 동일한 방식으로 512bit 패딩을 적용
• SHA-256 : 2의 256승 가지의 경우의 수가 존재

해시테이블의 사용률(load factor) 과 해시함수

• 해시테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수
• 사용률이 낮아야 해시충돌이 적게 일어나며 사용률이 0.7보다 커지면 리사이징 해야함
• 좋은 해시 함수란 배열에 값을 고루 분포시키는 함수