코딩테스트 문제를 풀다가 막히는 문제가 있었다. 내가 지금까지 배운 여러가지 자료구조를 생각해보았지만 딱히 올바른게 떠ㅎ오르지 않아서 힌트를 보았다. 힌트를 보니 '이분 탐색, 해시를 사용한 집합과 맵' 이라는 힌트가 있었다. 해시 예전에 배운것 같은데 정확한 개념이 떠오르지 않고 구현도 할줄 몰랐다. 애초에 이게 자바에서 어떻게 사용해야하는지에 대한 개념도 없었다. 항상 배운것들은 그때마다 정리를 해놔야 까먹지 않는데 늦은 정리를 해보자.
해시? 해시테이블?
Hash 단어부터가 너무 어렵다. 코딩은 영어로 되어있다보니 단어로 유추하기도 힘들다. 그래서 두 개념의 차이점을 아는 것이 가장 중요한것 같다. 차이점을 알아야 제대로 쓸 수 있으니까.
해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조이다. 단순하게 key - value로 이루어진 자료구조라고 생각하면 된다.
Hash Function
해시와 해시테이블을 제대로 알기전에 Hash Funtion(해시 함수) 라는 것을 알아야 한다. 자료구조를 배우는 이유는 원하는 값을 최대한 효율적으로 찾을수 있게하기 위해서 여러가지 저장구조를 배우는 것이다. 데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각해서 저장해야 한다. 해시 함수의 정의는 key를 **고정된 길이**의 hash로 변경해주는 역할을 한다. 이 과정을 **hashing**이라고 한다. key를 해시함수라는 함수에 Input으로 넣어서 Ouput으로 나오는 것이 Hash(해시)라고 생각하면 되고, 이 Hash(해시)가 저장위치가 된다고 생각하면 된다. 결국 Hash Function는 key로 해시를 만들어내는 함수이다.
해시테이블 구성
key
고유한 값, hash function의 Input이 된다.
key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야한 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일수 있다.), 고정된 길이의 해시로 변경한다.
hash function
key를 고정된 길이의 hash로 변경해주는 역할을 한다.
서로 다른 key가 hashing 후 같은 hash값이 나오는 경우가 있다. 이를 해시충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다.
해시충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않다.
value
저장소(버킷,슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다.
hash table
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.
데이터가 저장되는 곳을 버킷, 슬롯이라고 한다.
해시는 색인 또는 인덱스, hash function은 key->hash로 만들어 주는 함수, 해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.
장점
해시테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로O(1)의 시간복잡도를 가지고 있다.
단점
해시 충돌이 발생(개방 주소법, 체이닝 과 같은 기법으로 해결해 줘야 한다.)
순서/관계가 있는 배열에는 어울리지 않는다.
공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다.
hash function의 의존도가 높다. 해시함수가 복잡하다면 hash를 만들어 내는데 오래 걸릴 것이다. 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 한다. Direct-address table의 장점은 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않는다는 것이다. 하지만 실제 사용하는 키는 명개 되지 않을 경우에는 전체 키의 갯수만큼의 테이블 크기를 유지하는 것은 메모리 낭비이다. 그래서 실제 키 개수보다 적은 해시테이블을 운용한다. 그렇기에 해시 충돌이 발생할수 밖에 없고, 해시 충돌을 해결하기 위해 다양한 방법들이 고안되었다.
해시 충돌
만약 A,B 두가지 key가 있다고 하자. A와 B를 hash function으로 해시 값을 얻었는데 hash값이 2로 똑같이 나왔다. 이런 현상을 haash collision 이라고 한다.
해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다. 해시 충돌은 필연적으로 나타날 수 밖에 없다.
해결 방법 1. Chaining
체이닝은 저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다.
장점
미리 충돌을 대비해서 공간을 많이 잡아놓을 필요가 없다. 출돌이 나면 그때 공간을 만들어서 연결만 해주면 된다.
단점
같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아진다.해결 방법 2. Open Addressing(개방주소법)개방 주소법은 충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법이다. 개방주소법의 해시 테이블은 hash와 value가 1:1관계를 유지한다. 위의 그림에서 John과 Sandra의 hash가 동일해 충돌이 일어난다. 이때 Sandra는 바로 그 다음 비어있던 153 hash에 값을 저장한다. 그 다음 Ted가 테이블에 저장을 하려 했으나 본인의 hash에 이미 Sandra로 채워져 있어 Ted도 Sandra처럼 바로 다음 비어있던 154 hash에 값을 저장한다.
이런 식으로 충돌이 발생할 경우 비어있는 hash를 찾아 저장하는 방법이 개방주소법이다. 이때, 비어있는 hash를 찾아가는 방법은 여러가지가 있다.
선형탐색
해시값에서 고정폭으로 건너 뛰면서 비어있는 해시가 나오면 저장하게 된다.
52번 해시에서 충복이 일어나 고정폭(1) 씩 건너뛰면서 빈 해시를 찾으려면 57까지 5번의 연산을 해야한다. 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다.
제곱 탐색
고정폭이 아닌 1칸 -> 4칸 -> 9칸 -> 16칸 씩 건너 뛰면서 빈 칸은 찾는다. 해시값이 같은 해시들이 들어오면 공간을 많이 확보해놔야 한다.
해시함수 매핑 개선
특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라고 할 수 있다.
division method
가장 기본적인 해시 함수이다. 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 변환한다. 간단하면서도 빠른 연산이 가능한 것이 장점이다.
해시의 중복을 방지하기 위해 테이블의 크기 m은 소수로 지정해서 사용하는것이 좋다. 하지만 남는 공간이 발생해 메모리상으로 비효율적이다.
multiplication method
숫자 키 k, A는 0<A<1 사이의 실수 일때 `h(k) = (ka mod 1)*m 으로 계산한다.
2진수 연산에 최적화된 컴퓨터구조를 고려한 해시함수이다.
univeral hasing
여러개의 해시함수를 만들고, 이 해사함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법.
서로 다른 해시함수가 서로 다른 해시값을 만들어내기 때문에 같은 공간에 매핑할 확률을 줄이는 것이 목적
자바에서 사용하는 Hash
HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java2에서 처음 선보인 Java Collections Framework에 속한 API이다. HashTable 또한 Map 인터페이스를 구현하고 있기때문에 HashMap과 HashTable이 제공하는 기능은 같다.
차이점
보조 해시 함수
HashMap은 보조 해시함수를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충동(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
동기화
HashMap의 경우 동기화를 지원하지 않는다. 그래서 Hash Table은 동기화 처리라는 비용때문에 HashMap에 비해 더 느리다고 한다. 프로그래밍상의 편의성 때문에 멀티쓰레드 환경에서도 HashTable을 쓰기보다는 HashMap을 다시 감싸서 Map m == Collections.syschronizedMap(new HashpMap()); 과 같은 형태가 더 선호된다.
HashMap
HashMap에서 사용하는 충돌기법 방식은 Seaparate Chaining 이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데 HashMap에서 remove()메서드는 비번하게 호출될 수 있기 때문이다. 게다가 HashMap에 저자된 key-value 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing은 버킷의 밀도가 높아질수록 Worst Case 빈도가 높아지지만, Chaining은 해시 출동이 잘 발생하지 않도록 조정하면 Worst Case를 줄일 수 있다.
하나의 해시 버킷에 8개 이상의 키-값 쌍이 모이면 LinkedList를 Tree구조로 바꾼다. 그리고 버킷이 6개에 이르게 되면 다시 LinkedList 구조로 변경한다.
HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다. 해시 버킷의 수를 늘려서 해시 충돌의 확률을 줄이는 것이다
