6. 해시

어떤 데이터를 찾는다고 했을 때 쉽게 떠올려볼 수 있는 방법은 처음부터 끝까지 순차 탐색하는 방법이다. 이 방법은 확실하게 원하는 데이터를 찾을 수 있다는 장점이 있지만. 최악의 경우 탐색을 할 때마다 모든 데이터를 살펴봐야 할 수 있으므로 효율적이지 않다.

이 방법을 개선하려면 찾아야 할 값이 어디에 있는지 알아낼 방법이 필요하다. 즉, 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 굳이 탐색을 할 필요 없이 바로 데이터를 찾아낼 수 있다. 이 방법이 바로 해시이다.

 

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.

"어떻게 하면 빠르게 탐색을 할까?"라는 의문이 들 수 있는데 보통은 인덱스를 활용해 탐색을 빠르게 만들지만 해시는 키를 활용해 데이터 탐색을 빠르게 한다.

※ 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있다.

 

해시를 자세히 알아보자

일상생활에서 연락처로 해시의 예를 들 수 있다.

전화번호는 값이고 값을 검색하기 위해 활용하는 정보는 키이다. 그리고 그 사이에 키를 이용해 해시값 또는 인덱스로 변환하는 해시 함수가 있다. 해시 함수는 키를 일정한 해시값으로 변환시켜 값을 찾을 수 있게 해준다.

 

해시의 특징

1. 해시는 단방향으로 동작한다. 즉, 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없다.

2. 찾고자 하는 값을 O(1)이라는 굉장히 빠른 속도로 찾을 수 있다.

키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.

3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.

※ 단방향으로만 동작해서 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용된다.

 

해시 함수

해시 함수를 구현할 때 고려할 내용 

1) 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다.

ex) 해시 테이블의 크기가 N이면 인덱스는 0 ~ N - 1사이의 값을 나타내야 한다.

2) 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다. 충돌의 의미는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미한다.

 

자주 사용하는 해시 함수

1. 나눗셈법

키를 소수로 나눈 나머지를 활용한다. 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시한다. 

h(x) = x mod k

x는 키 k는 소수이다. 키를 소수로 나눈 나머지를 인덱스로 사용하는 것이다.

 

나눗셈법의 해시 테이블의 크기는 자연스럽게 K가 된다. 왜냐하면 K에 대해 모듈러 연산을 했을 때 나올 수 있는 값은 0 ~ (K - 1)이기 때문이다.

 

2. 곱셈법

나눗셈법은 때에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기가 쉽지 않다는 단점이 있다.  곱셈법은 모듈러 연산을 활용하지만 소수는 활용하지 않는다.

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

m은 최대 버킷의 개수(인덱스 + 값(1행)), A는 황금비이다. 

※ 황금비는 임의의 길이를 두 부분으로 나누었을 때 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율가 같은 비율을 말한다.

 

1) 키에 황금비를 곱한다.

2) 1단계에서 구한 값의 모듈러 1을 취한다. 쉽게 말해 정수 부분을 버리고 소수 부분만 취한다.

ex) 3.1523이면 0.1523만 취한다.

3) 2단계에서 구한 값을 가지고 실제 해시 테이블에 매핑한다. 테이블의 크기가 m이면 2단계에서 구한 수에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블에 매핑할 수 있다.

 

3. 문자열 해싱

키의 자료형이 문자열일 때도 사용할 수 있는 문자열 해싱에 대해 알아보겠다. 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.

hash(s) = (s[0] + s[1] * p + s[2] * p²  ... s[n - 1] * pⁿ⁻¹) mod m

 

1) 알파벳 a부터 z까지 숫자와 매치한 표와 키이다.

2) "a"는 매치 표를 보면 1이다. 따라서 "apple"의 "a"는 1이다. 그러므로 수식의 s[0] * p^0은 1 * 1이므로 (31의 0승은 1이다) 1이다.

3) 두 번째 문자열 "p"에 대해 연산을 진행한다. "p"는 16이다. 여기에 p^1을 곱하면 496이다.

4) 이렇게 곱한 값들을 더하면 최종값은 4,990,970이다. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 된다.

이렇게 하면 오버플로우가 발생할 수 있으므로 아래와 같은 문자열 해시 함수를 수정할 수 있다.

 

문자열 해시 함수 수정하기

덧셈을 전부한 다음 모듈러 연산을 하는 왼쪽 수식 대신, 오른쪽 수식처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우를 최대한 방지할 수 있다.

(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이다.

 

충돌 처리

1) 체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법이다. 체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결한다.

※ 링크드리스트는 데이터 요소들을 연결하여 구성한 선형 데이터 구조

B와 C를 해싱했을 때 3이다. 즉, 해시 테이블의 같은 위치를 가리키므로 데이터를 저장할 때 충돌이 발생한다. 이때 체이닝은 링크드 리스트로 충돌한 데이터를 연결하는 방식으로 해결한다. 하지만 체이닝에도 2가지 단점이 존재한다.

 

해시 테이블 공간 활용성이 떨어짐

충돌이 많아지면 그만큼 링크드리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어진다.

검색 성능이 떨어짐

충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어진다. 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문이다. 만약 마지막 버킷을 검색하는 경우 시간 복잡도는 O(N)이다.

참고로 자바에서 HashMap 클래스는 체이닝을 사용하여 해시 충돌을 처리한다. 그래서 링크드리스트로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 링크드리스트를 이진 탐색 트리로 변환하여 데이터 접근에 O(logN)의 성능이 나오도록 개선한다.

 

개방 주소법으로 처리하기

개방 주소법은 체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다.

 

선형 탐사 방식

충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동한다.

※ 보통 간격은 1로 하는 것이 일반적이다.

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

m은 수용할 수 있는 최대 버킷이다. 충돌이 나면 선형 탐사 방법으로 1칸씩 아래로 내려간다. 이 방법의 단점은 충돌 발생 시 1칸씩 이동하여 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생긴다. 이를 클러스터를 형성한다고 한다.

이런 군집이 생기면 해시값은 겹칠 확률이 더 올라간다.

※ 이를 방지하기 위해 제곱수만큼 이동해 탐사하는 방법도 있다.

 

이중 해싱 방식

말 그대로 해시 함수를 2개 사용하는 것이다. 두 번째 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 한다. 

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

선형탐사와 비슷하게 더하는 방식으로 데이터 위치를 정하지만 클러스터를 줄이기 위해 m을 제곱수로 하거나 소수로 한다

 

실제 코딩 테스트 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정이다.

 

해시맵

HashTable의 클래스와 HashMap 클래스가 있습니다. 두 클래스는 유사하지만 HashTable 클래스는 자바의 초기 버전과 호환성을 위해 남겨두었을 뿐 최근에는 잘 사용하지 않는다.

 

해시맵의 ADT

구분	정의	설명
연산	ValueType put(KeyType key, ValueType value)	해시맵에 데이터를 저장한다. 첫 번째 매개변수는 해당 데이터의 key값, 두 번째 매개변수는 해당 key에 해당하는 value값이다. 반환하는 값은 해시맵 내에 동일한 key에 해당하는 값이 있었다면 그 key에 대한 value 값을 반환한다.
	ValueType get(KeyType key)	key에 대한 value값을 반환한다.
	ValueType remove(KeyType key)	해시맵에서 key에 해당하는 데이터를 삭제한다.
	boolean containsKey(KeyType key)	해시맵 안에 해당 key가 있다면 true, 없다면 false를 반환한다.
	void clear()	해시맵 안의 모든 데이터를 삭제한다.
상태	int isEmpty()	해시맵 안에 데이터가 없다면 true, 있다면 false를 반환한다.
	int size()	해시맵 안에 있는 데이터의 개수를 반환한다.

 

 

HashMap 클래스 사용하기

//HashMap<KeyType, ValueType>
HashMap<String, Integer> hashMap = new HashMap<>();

// hashMap에 데이터 추가
hashMap.put("ABC", 10);
hashMap.put("BBB", 20);
hashMap.put("AAA", 30);
hashMap.put("ABC", 15);

System.out.println(hashMap.isEmpty()); // false
System.out.println(hashMap.get("ABC")); // 15
System.out.println(hashMap.containsKey("ABC")) // true

hashMap.remove("ABC"); // hashMap에서 키가 "ABC"인 데이터 제거
System.out.println(hashMap.size()); // 2

hashMap.clear(); // 해시맵의 모든 데이터 삭제
System.out.println(hashMap.isEmpty()); // true

 

처음에 ABC에는 value가 10이었지만 이후에 15라는 값을 넣을  때 10은 삭제되고 15로 대체된다.