[JAVA] 해시 맵

해시(Hash)

• 해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값
• 해시 값(Hash value), 해시 코드, 체크섬
• 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터값을 검색할때 활용

해시함수(hash function)

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 해시 함수(Hash function)는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘
• 자료구조, 캐시, 검색, 에러 검출, 암호 등으로 유용하게 사용

// 해시 함수 예시
Integer hashFunction(String key) {
	
    return (int)(key.charAt(0)) % 100;
}

해시 테이블(Hash Table)

• 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해시 테이블은 키와 값을 함께 저장해 둔 데이터 구조이다
• 테이블에 데이터를 저장할때 무작위로 지정되어 작성. 중간에 여유공간이 발생할 수 있다

해싱(hashing)

• 키(key) : 매핑 전 원래 데이터의 값
• 해시값(hash value) : 매핑 후 데이터의 값

매핑하는 과정 자체를 해싱이라 한다.

해시충돌(collision)

해시함수는 해시값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응) 하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌이 발생하게 된다.

그래서 충돌을 최소화할 수 있는 해시함수를 사용해야한다.

 

 

적재율(load factor)
적재율(load factor)이란 해시 테이의 크기에 대한 키의 개수의 비율을 뜻합니다. 즉 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이 됩니다.

 

해시 충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만, 충돌이 발생하는 경우에는 탐색과 삭제 연산이 키의 개수인 O(K)만큼이 걸리게 됩니다.

HashMap은 키 집합인 정의역과, 값 집합인 공역의 대응에 해시 함수를 이용하기에 해시 충돌이 하나도 일어나지 않는 해시 함수를 만드는 것은 비둘기집 원리에 의해 불가능합니다. 따라서 해시 충돌에 대해 안전하다는 해시 함수는 '충돌이 거의 일어나지 않는다'라는 의미를 뜻합니다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우에는 비둘기집 원리에 의해 해시 충돌은 항상 존재하며, 해시 테이블의 충돌을 해결하기 위해서는 해시 충돌을 완화하는 방향으로 문제를 해결해야함

 

해시 충돌 완화 방법

해시 충돌을 완화하는 방법에는 크게 Open Addressing과 Separating Chaining 방법이 있습니다.

• 개방 주소법(open addressing): 해시 테이블 크기는 고정하면서 저장할 위치를 찾는다.
• 분리 연결법 (separate chaining): 해시 테이블의 크기를 유연하게 만든다.

각각의 방법에 대해 한번 알아보겠습니다.

1. 개방 주소법(open-address)

open addressing은 한 버킷 당 들어갈 수 있는 엔트리는 하나이지만 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법입니다.
즉, open addressing의 주요 목적은 저장할 엔트리를 위한 다음의 slot을 찾는 것인데 예시로 다음과 같습니다.

그림을 살펴보면, John Smith와 Sandara Dee 152번으로 동일한 값이 나옵니다. 해시 충돌이 일어난 경우인데, Sandara Dee는 152번에 덮어 씌워지지 않고, 다음 빈 버킷인 153번에 들어간 것을 확인할 수 있습니다. 다음 key인 Ted Baker는 153이라는 값이 나왔지만 이미 Sandra Dee가 저장되어 있기에 충돌이 발생해서 다음 빈 버킷인 154번에 저장되었습니다.
예시는 무조건 한 칸씩 찾는 방법을 예로 들었지만 비어있는 칸을 찾아가기 위해서 아래와 같은 다양한 방법들이 존재합니다.

• Linear probing(선형 탐사법)
• Quadratic probing(제곱 탐사법)
• Dobule hashing(이중 해싱)

Linear Probing(선형 탐사법)

말 그대로 가장 간단하게 선형으로 순차적 검색을 하는 방법입니다. 해시 함수로 나온 해시 값(index)에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정된 폭만큼 옮겨 다음 빈칸을 찾아가는 방법입니다.

위 이미지를 보면 52라는 값을 해싱하여 해시값 2에 접근했지만 이미 존재하여 충돌이 났음을 알 수 있습니다. 따라서 임의의 고정된 크기인 한 칸씩 옮겨서 빈칸을 찾아가며 최종적으로 6에 저장되는 것을 확인할 수 있습니다.
이 경우에는 간단하지만 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(primary clustering) 문제가 발생할 수 있습니다. 위 이미지만 해도 2~6까지 데이터가 모여있는 것을 확인할 수 있는데, 모든 키가 2라는 값으로 해시값이 나올 경우 군집화 된 값들을 순차적으로 방문할 텐데 해시 성능이 크게 저하될 수 있습니다.
따라서 Linear Probing(선형 탐사법)은 해시 충돌이 해시 값 전체에 균등하게 발생할 때 유용한 방법입니다.

 

 

Quadratic probing(제곱 탐사법)

제곱 탐사법은 위의 선형 탐사법과 동일한데, 탐사 폭이 고정된 값이 아니라 제곱으로 늘어나는 점에 있어 차이가 있습니다.
즉, 빈 버킷의 slot을 찾기 위해 고정된 값이 아닌 2^1, 2^2, 2^3.... 의 방식으로 이동해서 빈칸을 찾습니다.
제곱 탐사법을 이용한 경우 데이터의 밀집도가 선형 탐사법보다 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 가능성이 적습니다. 하지만 선형 탐사법보다는 캐시의 성능이 떨어져서 속도의 문제가 발생합니다. 이는 배열의 크기가 커지게 되면서 L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문입니다.

 

Dobule hashing(이중 해싱)

이중해싱법 또는 재해싱은 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법입니다. 이 방법은 항목들을 이전 방법들보다 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있습니다.
하나는 처음의 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이며, 충돌 발생 시 저장할 index를 찾기 위한 해시 함수는 첫 번째 해시 함수와 달라야 합니다.

Dobule hashing(이중 해싱)

이중 해싱법은 충돌의 발생 가능성은 가장 적으나, 캐시의 성능은 Linear Probing, Quadratic Probing과 비교했을 때 가장 좋지 않으며, 추가적인 해시 연산이 들어가기에 가장 많은 연산량을 요구한다는 단점이 있습니다.

 

2. Separate chaining (분리 연결법)

간단한 아이디어로 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는다.

해당 버킷에 데이터가 이미 있는데 key 값이 다르면 충돌이 발생한다. 이때 연결리스트에 노드를 추가하여 데이터를 저장한다.

장점

• 유연하다.

단점

• 메모리 문제를 야기할 수 있다.
• 데이터의 수가 많아지면 동일한 버킷에 chaining 되는 데이터가 많아져 캐시의 효율성이 감소한다.