1. 해시(Hash), 해시 함수(Hash Function), 해싱(Hashing)
해시(Hash)는 데이터를 다루는 기법 중 하나로, 단방향 암호화 기법인 해시 함수를 이용하여 생성된 고정된 길이의 비트열을 의미한다.
해시를 만들기 위해서는 해시 함수가 필요한데, 해시 함수(Hash Function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
매핑 전 원래 데이터의 값을 key로, 매핑 후의 데이터 값(= 해시값, 해시코드)을 value로 변환하는 과정을 해싱(Hashing)이라고 한다.
2. 해시 테이블(Hash Table)
2.1. Hash Table
Map은 key-value 형태의 pair들을 저장하는 ADT이다. 같은 key를 가지는 pair는 최대 한 개만 존재할 수 있다. 즉 key는 중복이 불가하다.
해시 테이블은 맵의 구현체 중 하나이다. Hash Table은 배열과 해시 함수를 사용하여 맵을 구현한 자료구조이다.
2.2. Hash Function
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 특히 해시 테이블에서의 해시 함수는 임의의 데이터를 정수로 변환하는 함수이다.
해시 테이블은 해시 함수를 이용하여 키를 해시값을 매핑하고, 이 해시값을 배열의 크기로 나눈 나머지를 배열의 인덱스로 사용한다. 그리고 해당 인덱스 위치에 데이터를 저장한다.
예를 들어 배열의 크기(capacity)가 8인 경우, 해시 함수를 통해 얻은 해시값을 8로 나눈 나머지가 배열의 인덱스가 된다. 이때 8개의 각각의 공간을 버킷(bucket) 또는 슬롯(slot)이라고 한다.
key -> (해시 함수) -> 해시값 -> (해시값 % 배열의 크기) -> 배열의 인덱스 -> 해당 인덱스 위치에 데이터를 넣는다.
3. 해시 충돌(Hash Collision)
해시 충돌은 다음 두 가지 경우에 발생한다.
-
key 값은 다른데 해시값이 같을 때
-
key 값도 해시값도 다른데 hash % map_capacity 결과가 같을 때
해시 충돌의 해결법은 다음과 같다.
3.1. Separating Chaining
-
데이터 삽입: Separating Chaining은 Linked List를 사용하는 방식이다. 인덱스가 충돌날 때, 인덱스가 가리키고 있는 Linked List에 노드를 추가하여 데이터를 추가한다.
-
데이터 조회: 데이터를 조회할 때는 해당 인덱스가 가리키고 있는 Linked List를 선형 탐색하여 해당 key 값의 value를 찾는다.
-
데이터 삭제: 데이터를 삭제할 때도, 해당 인덱스가 가리키고 있는 Linked List에서 해당 노드를 삭제한다.
3.2. Open Addressing
Open Addressing은 해시 충돌에 대해 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고 해시 테이블 배열의 빈 공간을 사용하는 방식이다. Open Addressing 방식으로는 Linear Probing, Quadratic Probing, Double hashing 등이 있다. 그 중 Linear Probing은 다음과 같다.
-
데이터 삽입: Linear Probing은 해시 충돌이 발생할 때, 해당 인덱스 뒤에 있는 버킷 중에 비어 있는 버킷을 찾아서 데이터를 넣는 방식이다.
-
데이터 조회: 데이터를 조회할 때는 해당 인덱스의 데이터와 비교한 후, key 값이 같지 않으면 Linear Probing 방식이기 때문에 뒤의 인덱스를 탐색해서 해당 key 값이 나오거나 뒤의 인덱스 key 값이 없을 때까지 탐색한다. 그리고 뒤의 인덱스의 데이터와 key 값을 비교한 후 같으면 해당 데이터를 반환한다.
-
데이터 삭제: 데이터를 삭제할 때는 해당 인덱스 위치에 더미 데이터를 넣어준다. 만약 해당 데이터 삭제 시 더미 데이터를 넣지 않으면 어떻게 될까? 위 사진에서 John Smith의 데이터를 삭제하고, Sandra Dee 데이터를 조회하는 상황을 예로 들어보자. Sandra Dee의 인덱스인 152에 접근한다. 그러나 해당 위치에는 아무 데이터가 없기 때문에 데이터를 찾지 못하고 탐색을 끝내버린다. 반면, John Smith 데이터를 삭제할 때 삭제 표시를 해주는 더미 데이터를 넣어준다면, Sandra Dee 데이터를 조회할 때 인덱스 152에 접근하고, 삭제 표시가 있기 때문에 Linear Probing 방식이기 때문에 뒤 인덱스들까지 탐색하게 된다. 그리고 인덱스 153을 탐색할 때 데이터를 찾고 반환한다.
Separating Chaining 방식과 Open Addressing 방식 비교
-
Separating Chaining: Linked List를 사용하기 때문에 추가할 수 있는 데이터의 수가 비교적 많다.
-
Open Addressing: 추가적인 메모리 공간을 사용하지 않기 때문에 Separate chaining 방식에 비해서 메모리를 덜 사용한다.
3.3. Resizing
Separate changing 방식의 경우, 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 검색 성능이 떨어진다. 따라서 버킷의 개수를 늘려주는 것이 좋다. 또한 Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해야 한다. 이를 리사이징(Resizing)이라고 한다.
리사이징은 더 많은 버킷을 가지는 배열을 새로 만든 다음에, 다시 새로운 배열에 기존 데이터의 해시값을 통해 인덱스(해시값 % 배열의 크기)를 다시 계산해서 해당 인덱스 위치에 데이터를 복사한다.
4. 자바의 HashMap
-
구현: 해시 테이블 사용
-
데이터 조회/삽입/삭제 시간: 보통 모든 데이터를 상수 시간에 접근한다. (시간 복잡도 O(1))
-
해시 테이블은 배열을 사용하기 때문에 데이터 조회 시 시간 복잡도가 O(1)인건 맞으나, 왜 해시 테이블의 데이터 삽입, 삭제 시 시간 복잡도도 O(1)일까? 바로 여기서 인덱스는 데이터의 고유한 위치이기 때문에 데이터를 삽입, 삭제할 때 다른 데이터로 채울 필요가 없다. 해시 충돌을 해결하기 위한 Separating Chaining 방식 또한 배열과 Liked List를 사용하기 때문에 데이터 삽입, 삭제 시 데이터를 옮겨 채우는 과정이 필요하지 않다.
-
최악의 경우는 모든 데이터를 삽입, 삭제할 때마다 해시 충돌이 발생하는 경우이다.
-
-
해시 충돌 해결 방법: Separating Chaining
-
default initial capacity: 16
-
resize 타이밍: map capacity의 3/4 이상 데이터가 존재할 시
-
resize 규모: 2배
자바의 HashMap과 HashTable
HashTable과 HashMap의 차이점은 다음과 같다.
- Thread-safe 여부
- HashTable: Thread-safe하다
- HashMap: Thread-safe 하지 않다.
따라서 멀티스레드 환경이 아니라면 HashTable은 HashMap 보다 성능이 떨어진다.- Null 값 허용 여부
- HashTable: key에 null을 허용하지 않는다.
- HashMap: key에 null을 허용한다.
다만 HashMap이 동기화를 지원하지 않는다고 해서 HashTable을 사용하는 것은 좋지 않다. 그 이유는 HashTable 클래스는 자바에서 컬렉션 프레임워크가 만들어지기 전부터 존재하던 것으로, 호환을 위해 남겨준 것이다. 즉 구형인 HashTable을 사용하기 보다 동기화를 지원하는 HashMap인 ConcurrentHashMap를 사용하자.
참고 자료
