[자료구조] 해시

해시란?

• 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
• 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근 가능함
• 특정 값이나 정보를 기준으로 빈번한 검색을 하거나 특정 정보와 매핑하는 값의 관계를 확인하는 작업이 있을 때 해시를 활용

해시의 특징

• 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없음 (단방향 동작)
• 탐색 시 시간 복잡도가 O(1)
• 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 함

해시 함수

나눗셈법

• 키를 소수로 나눈 나머지를 인덱스로 사용함 (e.g. 7 % 2 = 1)
• 나머지를 취하는 연산은 모듈러 연산이라고 부름

  h(x)=x mod k

• x는 키, k는 소수
• 나눗셈법의 해시 테이블 크기는 K, 따라서 아주 많은 데이터를 저장해야 한다면 아주 큰 소수가 필요함

곱셈법

• 나눗셈법과 비슷하게 모듈러 연산을 활용하나 소수는 활용하지 않음

  h(x) = (((x ⋅ A) mod 1) ⋅ m)

• m은 최대 버킷의 개수, A는 황금비(대략 1.618...)

1. 키에 황금비를 곱함
2. 1에서 구한 값의 모듈러 1을 취함.
   (e.g. 모듈러 1의 결과가 3.1523이면 0.1523만 취함)
3. 구한 수에 m을 곱한 후 정수 부분만 취함

문자열 해싱

hash(s) = (s[0]+s[1]p+s[2]p^2+⋯+s[n−1]*p^n−1) mod m

• p는 31이고, m은 해시 테이블 최대 크기
• 키가 문자열이면 각 문자열의 문자들을 적절한 숫자로 변경한 다음 해시 함수를 적용해야 함

충돌 처리

서로 다른 키에 대하여 해시 함수의 결괏값이 같을 수 있으며, 이를 충돌이라고 함

체이닝으로 처리하기

• 충돌이 발생하면 해당 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결함
• 충돌이 많아지면 그만큼 연결 리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어짐
• 연결 리스트로 연결한 값을 찾으려면 리스트의 맨 앞 데이터부터 검색해야 함 -> 충돌이 많을수록 검색 성능이 떨어짐

개방 주소법으로 처리하기

• 빈 버킷(해시 테이블 데이터)을 찾아 충돌값을 삽입함
• 체이닝보다 메모리를 더 효율적으로 사용
• 선형 탐사 방식: 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
• 이중 해싱 방식: 해시 함수를 2개 이상 사용, 두 번째 해시 함수의 역할은 충돌이 발생했을 경우 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 함

정리

• JS의 경우 Object 자료형을 제공하는데, 이 자료형이 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있음.
• 해시 함수 자체를 구현하라는 문제는 잘 나오지 않지만, 개념을 알면 좀 더 효율적으로 오브젝트를 사용할 수 있다!