Mission3 (hashmap)

✏️Hashmap

• 특정값 → 해시함수 → 인덱스에 저장

• 해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 index에 저장하는 자료구조이다.

• 시간 복잡도가 O(1)이다.

• 직접 주소 테이블은 값에 접근하기는 편하지만 공간 효율이 좋지 않다는 단점이 있다.(저장된 데이터를 제외하고 나머지 공간은 값은 없지만 메모리 할당된 상태 = 적재율이 낮다)

• 이 단점을 보완한 것이 해시 테이블이다. 해시 테이블은 직접 주소 테이블처럼 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수에 통과시켜서 사용한다.

• 해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 이 함수가 뱉어내는 결과물을 해시라고 한다.

 

📌 hash function

아래 과정을 예로 들 때,

A = 1, B = 2, C = 3, D = 4, E = 5

위에 따라서,

ACE = 135

CAB = 312

DAB = 412...

문자를 가져와 숫자로 변환하는 이러한 과정을 해싱이라고 하고,

글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라고 한다.

 

좋은 해시함수는?

1. 동일한 키는 동일한 값을 생성.

2. 사용 가능한 모든 셀에 데이터를 분산시키는 함수.

3. 배열의 범위가 골고루 활용돼야 한다.

4. 일정한 크기로 hash code생성

5. 다양한 연산을 조합해서 해쉬함수를 만듦

   • ASCII 값과 소수(prime number)를 활용한 방법

해시테이블의 효율성

1. 해시 테이블에 얼마나 많은 데이터를 저장하는가

2. 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가

3. 어떤 해시 함수를 사용하는가

 

📌 Collision

• 다른 값을 해시 함수에 넣었지만 같은 값이 튀어나오는 것.

• 이미 채워진 셀에 데이터를 추가하는 것. (인덱스가 겹치는 상황)

• 해시테이블은 반드시 충돌 조정을 수행해야 한다.

• 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

직접 주소 테이블은 동적으로 테이블을 늘려갔지만, 해시 테이블은 처음부터 고정적인 공간을 할당하고 값을 계속 우겨넣는 방식이다. 데이터의 개수보다 테이블이 작다면 당연히 충돌이 생길 수 밖에 없고, 그렇지 않다해도 충돌 가능성이 있다.

이처럼 해시 테이블에는 해시의 충돌이라는 단점이 있기 때문에 해시 테이블을 운용할 때 가장 중요한 것은 해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐이다. 그러나 해시 함수를 아무리 잘 짜더라도 충돌을 완전히 방지한다는 것은 힘들다. 어느 정도 충돌을 감안하되 최소화하기 위해 해시 함수의 알고리즘을 개발하거나, 충돌이 발생했을 때 우회해서 해결할 수 있는 방법을 사용한다.

 

Open Address(개방 주소법)

해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(probe)한 후, 비어 있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방주소(open address)라고 한다.

• 선형탐사(Linear probing): 충돌 발생 시 정해진 n칸 만큼 옆 방을 주는 방법. 같은 해시가 여러 번 나오는 경우 데이터가 연속되게 저장될 가능성이 높아진다. ➔ 악순환의 반복! 충돌이 계속 될 수록 데이터가 연속되게 저장되기 때문에 데이터가 밀집되어 있는 덩어리가 생긴다. (일차 군집화 Primary Clustering)

• 제곱탐사(Quadratic probing): 선형 탐사와 동일하지만 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어난다. 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법 보다는 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 줄어든다. (이차 군집화 Secondary Clustering)

• 이중해시(Double hashing probing): 해시 함수를 이중으로 사용하는 것. 하나는 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 발생했을 때 탐사 이동폭을 얻기 위해 사용한다. 최초 해시에서 같은 인덱스가 나오더라도 다른 해시 함수를 거치면서 다른 탐사 이동폭이 나올 확률이 높기 때문에 값이 골고루 저장될 확률이 높아진다.

Seperate Chaining(분리 연결법)

충돌 우회 방법. 해쉬 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.

 

Resizing(테이블 크기 재할당)

해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가 데이터가 넘치기 마련이다. 개방 주소법을 사용하는 경우에는 해시 테이블이 꽉 차서 더 이상 저장을 못 하는 상황이 발생할 것이고, 분리 연결법을 사용하는 경우에는 테이블에 빈 공간이 적어지면서 충돌이 발생할수록 각각의 버킷에 저장된 리스트가 점점 더 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것이다.

• 해시 테이블은 꽉꽉 아낌없이 채우기보다는 어느 정도 비워져 있는 것이 성능 상 더 좋다.
  (데이터와 셀 간 비율을 부하율이라고 하고 이상적인 부하율은 0.7(원소 7개/셀 10개)이라 말할 수 있다. )
• 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야 한다.