[Algorithm/Study] 3주차 - 해시

 

해당 스터디는 <코딩 테스트 합격자 되기 C++> 저자님과 함께하는 스터디입니다.

인프런 강의 < 코딩 테스트 합격자 되기 C++ > 을 보고 정리한 내용입니다.

---

 

해시의 개념

배열로 구현한 전화번호부

전화번호부를 만든다고 생각해보자. 이름과 그 이름에 맞는 연락처를 저장하려고 한다면 어떻게 구현할 수 있을까?

배열로 구현한 전화번호부에서 '홍길동'의 연락처를 찾으려면 다음과 같은 과정을 거친다.

• 이름 테이블을 선형탐색하면서 '홍길동'을 찾는다.
• '홍길동' 위치에 해당되는 전화번호 테이블을 참조한다.
• '홍길동' 위치에 있는 전화번호는 '전화번호4'라는 것을 확인한다.

위와 같은 방식으로 '홍길동'의 연락처를 찾을 수 있다. 그러나 문제점은 성능이 떨어진다는 점이다! 가장 최악의 경우 배열 끝까지 탐색을 해야하기 때문에 O(N)의 시간복잡도가 걸린다. 예시는 5개의 이름과 전화번호뿐이지만 그 수가 훨씬 늘어난다면 매우 비효율적일 것이다. 전화번호부를 좀 더 효율적으로 구현하기 위해 해시함수를 사용할 수 있다.

해시함수로 구현한 전화번호부

해시란 해시함수를 사용하여 변환한 값을 인덱스로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 아래 이미지와 같이 이름을 해시함수에 넣어 변환한 값을 인덱스로 사용해 이름만 가지고 빠르게 그 위치를 알 수 있다. 

해시 함수 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

이렇게 나온 인덱스에 각 이름에 해당하는 연락처를 저장해두면 하나하나 탐색하지 않고도 이름만 넣으면 바로 연락처를 찾을 수 있다. 배열로 구현했을 때의 시간복잡도는 O(N)이었는데, 해시로 구현하면 키를 통해 바로 위치를 찾을 수 있으므로 O(1)의 시간복잡도를 갖는다.

 

해시의 요소는 다음과 같다.

• 해시함수 : 키를 인덱스로 변환해주는 함수
• 버킷 : 해시 테이블에서 데이터 하나하나를 저장하는 공간
• 해시 테이블 : 해시 함수를 사용해 데이터를 저장하고 검색하는 자료구조, 버킷들의 집합

해시를 사용하는 경우

그렇다면 어떤 문제에서 해시를 활용해야 할까?

• 키-값 쌍으로 연관된 데이터가 존재하면서 해당 값에 대한 접근이 빈번한 경우(ex. 사전, 전화번호부 등)
• 중복되지 않은 키를 사용하는 경우(ex. 학번, 주소 등)

특정 키에 여러가지 값을 매칭해야하는 경우에는 해시를 사용하지 않는 것이 좋다.

해시함수

해시함수란 임의의 키를 해시 테이블의 인덱스로 변경해주는 함수이다. 해시함수에서 중요한 점은 다음과 같다.

• 해시 테이블의 크기가 N이라면 해시함수는 0 ~(N - 1) 사이 값을 내야 한다.
• 충돌을 최소화 할수록 좋은 해시함수이다.

여기서 '충돌'이란 서로 다른 키에 대해 해시함수가 동일한 인덱스를 반환할 경우 생기는 현상을 말한다.

해시함수(나눗셈 법)

나눗셈 법은 소수인 k로 mod 연산을 하는 방식이다.

h(x) = x mod k (x는 키, k는 소수)

• k로 나눈 나머지는 0 ~ (k - 1)이므로 해시 테이블의 크기는 k이다.
• k가 소수가 아니라면 k주기로 해시값이 반복되어 충돌이 일어날 확률이 크다. 따라서 소수를 사용해 숫자를 골고루 나오게 해서 충돌을 줄인다.
• 단점 : 해시 테이블의 크기가 커지면 더 큰 소수가 필요하다. 

해시함수(곱셈법, 실제연산)

곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식이다.

h(x)= (((x * A) mod 1) * m) (x는 키, A는 황금비, m은 최대 버킷의 갯수)

 

황금비란 두 길이 a와 b가 있을 때 두 길이의 비율이 a/b = a/(a+b)를 만족할 때 나타난다. 황금비는 대략 1.6180339887...이라는 고유한 값이 나온다. 이 비율은 충돌을 최소화할 수 있는 불규칙한 소수이기 때문에 곱셈법에서 사용된다.

• 키에 황금비를 곱해 그 결과에 mod 1을 하면 소수만 취할 수 있다.
• 그 결과에 m을 곱해 정수 부분을 인덱스로 사용한다. (0 ~ m-1)

해시함수(문자열 해싱)

문자열 해싱은 아스키 코드 값을 이용하는 방식이다.

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

• 해시함수를 적용하려면 숫자여야하므로 각 문자의 아스키 코드 값으로 매칭시켜 사용한다.
• p는 보통 31로 한다. 그러나 예를 들어 문자열이 20개라면 p는 31^19가 되므로 숫자가 너무 커져 오버플로우가 발생할 수 있다. 따라서 실제로 사용할 때는 수정된 공식을 사용한다.

오버플로우를 방지하기 위해 수정된 공식은 다음과 같다. (a + b) % c = (a % c + b % c) % c 의 공식을 활용한 것이다.

hash(s) = (s[0] % m + s[1] * p % m + s[2] * p^2 % m + ...... + s[n-1] * p^(n-1) % m) % m

해시 충돌 처리

해시 충돌은 서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 발생한다. 해시 충돌을 처리하는 대표적인 방법에는 체이닝, 개방 주소법이 있다.

체이닝

체이닝이란 충돌 발생 시 해당 버킷에 Linked List로 데이터를 연결하는 것을 말한다. 따라서 특정 버킷에 데이터가 N개인 경우 원하는 값을 찾는데 O(N)이 걸릴 수 있다.

Hash table - Wikipedia

개방 주소법 - 선형 탐사

개방 주소법이란 충돌 발생 시 다른 빈 버킷을 찾아 충돌값을 삽입하는 것으로, 메모리를 아끼기 위해 기존 해시테이블을 사용하는 방식이다. 그 중에서도 선형 탐사법은 충돌이 발생한 곳에서 비어있는 버킷이 나올 때까지 계속해서 탐사하는 방법이다.

h(k, i) = (h(k) + i) mod m

개방 주소법 - 이중 해싱

이중 해싱법은 해시 함수를 2개(경우에 따라 N개까지 확장) 사용하는 방식이다. 첫 번째해시 함수는 초기 위치를 찾고, 충돌이 발생하면 두 번째 해시 함수를 사용해 탐색 간격을 결정한다.

h(k, i) = (h1(k) + i * h2(k)) mod m

Map과 Hash

map은 hash와 달리 이진 탐색 트리를 활용하며, 매번 키 순으로 데이터가 정렬된다. O(logN) 따라서 키 값 정렬이 필요하지 않은 상황에서 map을 사용하면 안된다. 강의에서는 이렇게 설명해주셨는데 자바에서도 똑같은지 궁금해서 검색해보았다. 자바에서 Map은 인터페이스로 데이터를 키-값 쌍으로 저장하는 추상적인 자료구조이다. Map 인터페이스는 여러 클래스에 의해 구현되며, 가장 많이 사용되는 구현체들은 HashMap, LinkedHashMap, TreeMap 등이 있다.

 

결론부터 말하자면 내부적으로 해시 테이블을 사용하는 구현체는 HashMap이고, 정렬과 이진 탐색 트리를 사용하는 구현체는 TreeMap이다. 보통 정렬된 순서가 필요한 경우 TreeMap을 사용하고, 순서와 상관없이 빠른 검색이 필요할 때는 HashMap을 사용한다.

What is a map interface in Java?. In Java, the Map interface is a part of… ❘ by Mayanknegi ❘ Oct, 2024 ❘ Medium

 

위 이미지에 설명은 다음과 같다.

 

• Map: 모든 Map 자료구조의 기본 인터페이스
• HashMap: Map 인터페이스를 구현한 기본적인 해시 테이블 기반의 자료구조
• LinkedHashMap: HashMap을 상속받아 데이터의 삽입 순서를 유지하는 자료구조
• SortedMap: 데이터를 정렬된 상태로 저장할 수 있는 인터페이스
• NavigableMap: 정렬된 Map에서 추가적인 탐색 기능을 제공하는 인터페이스
• TreeMap: NavigableMap과 SortedMap을 구현하며, 이진 탐색 트리를 기반으로 데이터를 자동으로 정렬하는 자료구조

⭐ 기억할 것 ⭐
- 강의나 정리된 자료만 보고 "이해했다"고 느끼면 내 실력은 늘지 않는다.
- 남의 것을 보지만 말고 정말 내 것으로 만들어야 한다.
- 남에게 내가 배운 것을 설명한다고 했을 때 막히지 않고 설명할 수 있는지 확인해보자.

저자님께서 피드백 해주신 말씀 중 하나인데, 찔리는 부분이 많다.😅
1) 이 개념을 모르는 사람이 내 블로그 글을 보고 이해할 수준으로 정리 되었는가?
2) 이 개념과 대립되는 다른 개념들이 있는가? 비교 설명할 수 있는가?
3) 이 개념을 적용하는 문제를 풀 수 있는가?

단순히 '강의를 보고 개념 정리를 한다' 라는 느낌보다는 정말 안보고도 설명할 수 있도록 온전히 내 것으로 만들어가며 공부를 해야겠다는 생각이 들었다. 그 과정이 쉽지는 않겠지만 정직한 방법으로 꾸준히 하면 더 성장할 수 있지 않을까? 앞으로도 화이팅...!

 

코딩 테스트 합격자 되기 - C++ 강의 | 대시보드 - 인프런