Hash
Java의 hashCode 메서드를 공부하던 중 깊이있게 이해하기 위해서는 먼저 Hash에 대해 이해할 필요성을 느끼고 Hash에 대해서 먼저 정리해보기로 한다. 그러면 Hash란 무엇일까? Hash는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값을 말한다.
해시 함수(Hash Function)이란?
해시 함수는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜주는 함수를 말한다.
해싱 함수의 특징 중 하나로는 결과값이 정해진 길이로 나오는데 1글자를 입력하거나 100글자 이상을 입력하더라도 똑같은 정해진 길이의 결과값을 반환한다. 그렇다보니 입력값이 다른데 같은 출력값이 나오는 해시 충돌이 발생할 가능성이 아주 낮지만 있다. 따라서 해시 충돌을 방지하기 위해 앞의 값을 연결하는 체이닝, 2개의 해시 함수를 준비하는 이중 해시 등의 다양한 방법등을 설계해서 사용하고 있다.
해시 함수의 특징
- 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.
- 입력값의 아주 일부만 변경되어도 전혀 다른 결과값을 출력한다.(눈사태 효과)
- 출력된 결과값을 토대로 입력값을 유추할 수 없다.
- 입력값은 항상 동일한 해시값을 출력한다.
참고: 해싱(Hashing)
Hashing이란 위 내용을 참고해 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업을 말함.
해시 테이블(HashTable)
어떤 사람이 만약에 내 채널에 있는 동영상을 다운받아서 그 사람 채널에 그대로 올리면 중복되는 동영상이라는 에러 메세지가 뜬다. 전 세계 수많은 유튜브 동영상과 큰 영상 파일 크기임에도 유튜브는 그 사람이 내 채널에 있는 영상을 자기 채널에 올리는 순간 바로 알려준다.
어떻게 가능한 것일까? 바로 해시 테이블 덕분이다. 해시 테이블은 데이터를 해싱을 사용하여 key와 value가 쌍을 이루는 형태로 저장하는 자료구조를 말하며 필요한 데이터를 키 값을 통해 아주 빠르게 탐색가능하다. 즉, key가 고유의 해시 함수를 통해 데이터를 접근하는 구조로 이루어져 있어 다른 자료구조인 이진탐색트리나 배열에 비해서 굉장히 빠른 속도로 탐색, 삽입, 삭제를 할 수 있기 때문에 컴퓨터 공학에서 반드시 알아야 하는 개념이다.
참고로 대표적인 해시함수로는 Division Method, Digit Folding, Multiplication Method, Univeral Hashing 등이 있고, 암호용 해시 함수는 매핑된 해싱 값만 알아가지고는 원래 입력값을 알아내기 힘들다는 사실을 이용해 암호학에 사용될 수도 있다.
Hash Table의 접근 방식
F(Key) -> HashCode -> Index -> Value
해시 테이블을 어떻게 데이터를 저장하고 접근하는지 살펴보자. 해시 테이블은 검색하고자 하는 키(key) 값을 입력받아서 해시함수를 사용하여 반환된 해시코드(hashCode)를 배열의 인덱스(index)로 삼아 데이터(value)를 저장 및 접근한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 여기서 사용하는 키 값은 문자열나 숫자 등이 될 수도 있다. 해시함수는 어떤 특정한 규칙을 이용해서 크기가 얼마나 큰지에 상관없이 입력받은 키 값으로 동일한 해시코드를 만들어 준다.
Direct Address Table
Java의 Object 클래스에는 hashCode 메서드가 있는데 왜 hashCode를 사용하는 것일까? int a가 있다면 a의 값을 그대로 키 값으로 즉, 주소로 사용하는 테이블을 사용하면 안되는 것일까? 먼저 이러한 간단한 형태의 테이블을 Direct Address Table이라고 한다. 앞서 말한것처럼 키 값이 100이라고 했을때 배열의 인덱스 100에 원하는 데이터를 저장한다.
위 그림처럼 키값이 21이기 때문에 인덱스 21에 원하는 데이터를 저장하게 되는데 이러한 자료구조는 탐색, 삽입, 삭제 연산을 모두 O(1)에 할 수 있지만 다음과 같은 한계점이 있다.
- 최대 키 값에 대해 알고 있어야 한다.
- 최대 키 값이 작을때 실용적으로 사용할 수 있다.
- 키 값들이 골고루 분포되어 있지 않다면 메모리 낭비가 심하다.
Hash Table 사용 이유
Hash Table의 가장 큰 장점은 검색 속도가 매우 빠르다는 것이다. 왜 빠른지에 대해 알아보자. 해시함수를 이용해서 만든 해시코드는 정수이다. 그래서 배열 공간을 고정된 크기만큼 미리 만들어 놓고 해시코드를 배열에 개수로 나머지 연산을 해서 배열에 나눠 담는 것이다. 그 말은 즉, 해시코드 자체가 배열의 인덱스로 사용되기 때문에 검색 자체를 할 필요없고, 해시코드로 바로 데이터의 위치를 다이렉트로 접근할 수 있어 빠르다는 것이다.
하지만 해시 함수에는 위 그림처럼 다음과 같은 문제가 발생할 수 있다.
- 서로 다른 키 값들(different keys) -> 같은 해시코드(same code)
- 다른 해시코드(different hashcode) -> 같은 인덱스(same index)
해시 함수는 때로 서로 다른 키 값으로 동일한 해시코드를 만들어 내기도 한다. 그 이유는 키 값은 문자열이고, 그 가짓수가 무한한데 반해서 해시코드는 정수개만큼 제공하지 못하기 때문에 알고리즘이 아무리 좋아도 어떤 키들은 중복되는 해시코드를 가질 수 밖에 없다.
그리고 때로는 해시 알고리즘이 서로 다른 해시코드를 만들어 냈는데 배열방은 한정되어 있기 때문에 같은 방(index)에 배정받는 경우도 있다. 이렇게 하나의 배열 인덱스에 겹쳐서 저장되어야 하는 경우를 Hash Collusion(해시 충돌)이라고 한다. 따라서 해시 테이블에 있어 충돌을 최소화하기 위해서는 좋은 해시 알고리즘은 매우 중요하고, 입력받은 키를 가지고 얼마나 골고루 잘분배하는냐에 좋은 알고리즘 인지가 결정이 된다.
해시 충돌
해시테이블은 해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조인데 해시 테이블 이전에도 설명했듯이 입력값이 다른데 같은 출력값이 나오는 경우가 아주 낮지만 가능성이 있다. 이렇게 입력값이 다르지만 해시 함수의 결과값이 같은 경우를 해시 충돌(Hash Collision)이라고 한다. 충돌에 대해서 이해하기 위해선 먼저 적재율(Load Factor)에 대해서 이해해야 한다.
적재율
적재율이란 해시 테이블의 크개 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K / N이다. 위에서 살펴본 Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하(대신 그만큼 메모리 낭비가 심하게 될 수도 있음)이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생할 가능성이 있다.
Hash Table의 구조 개선
만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K)만큼 걸리게 된다. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌이 전부 발생했음을 말한다. 따라서, 충돌을 최대한 줄여서 연산속도를 빠르게 하는 것이 해시 테이블의 핵심인데 이에 중요하게 작용하는 것이 바로 해시함수를 구현하는 해시 알고리즘이다. 해시 알고리즘이 견고하지 못하면 해시함수의 출력값들이 같은 경우가 빈번하게 발생되어 잦은 충돌이 이어질 수 있다.
따라서 해시 테이블의 중점사항은 충돌을 완화하는 것이며 그 방법으로는 2가지가 있다.
- 해시 테이블의 구조 개선
- 해시 함수 개선
충돌을 완화하기 위한 방법
Chaining
체이닝이란 충돌이 발생했을때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법을 말한다. 위에서 살펴본 그림이 체이닝(Chaining) 방법을 사용한 것이고, 충돌하게 되는 경우에는 나중에 들어온 값을 뒤에 연결함으로써 충돌을 처리한다.
위 그림을 보면 John Smith와 Sandra Dee의 인덱스가 152번으로 충돌하는데 이 때 먼저 들어온 John Smith 뒤에 Sandra Dee를 연결함으로써 충돌을 해결한다.
체이닝을 통해 해시테이블을 구현했을 때의 시간복잡도는 어떻게 될까? 삽입(Insertion)의 경우 연결리스트에 추가하기만 하면 되기 때문에 상수시간 O(1)이 걸리지만 탐색과 삭제의 경우는 최악일 때 키값의 개수인 K에 대해 O(K)가 걸리게 된다.
Open Addressing
위 방법과 달리 동일한 주소에 다른 데이터가 있을 경우 다른 주소를 이용하게 만드는 기법이다. Chaining과 달리 John Smith 뒤에 Sandra Dee를 연결하는 것이 아닌 다음 비어있는 주소를 찾아 153에 저장하는 것을 볼 수 있다. 이러한 원리로 탐색, 삽입 삭제가 이루어지는데 다음과 같이 동작한다.
- 삽입: 계산한 해시값에 대한 인덱스가 이미 차있는 경우 다음 인덱스로 이동하면서 비어있는 곳에 저장한다. 이렇게 비어있는 자리를 탐색하는 것을 탐사(Probing)이라고 한다.
- 탐색: 계산한 해시값에 대한 인덱스부터 검사하며 탐사를 해나가는데 이 때 "삭제" 표시가 있는 부분은 지나간다.
- 삭제: 탐색을 통해 해당값을 찾고 삭제한 뒤 "삭제" 표시를 한다.
Big O of Hash Table
Average Case
- 삽입(Insertion): O(1)
- 삭제(Deletion): O(1)
- 탐색(Access): O(1)
위 Big O는 해시 함수가 얼마나 빠른지, 그리고 얼마나 고르게 데이터를 분배해서 충돌의 횟수를 줄이는지에 달려있다.
Worst Case
- 한 인덱스에 모든 값을 넣는 경우 -> O(n)
- 이런 상황이 온다면 값을 삽입, 삭제, 탐색하는데 n의 시간이 걸리고, 해시 함수 자체가 상수값의 시간을 가진다고 해도 리스트와 다름없다.
HashTable 구현하기
구조는 체이닝을 사용했고, 해시 함수로는 각 문자의 아스키코드를 더하는 방식을 이용했다.
public class HashTable {
// Node형 연결리스트로 선언
private LinkedList<Node>[] data;
// 자신을 호출하면서 배열방의 크기를 지정
public HashTable(int size) {
this.data = new LinkedList[size];
}
// Key값을 통해 HashCode 생성 - 각 문자의 아스키코드를 더하는 방식
private int getHashCode(String key) {
int hashCode = 0;
for (char c : key.toCharArray()) {
hashCode += c;
}
return hashCode;
}
// HashCode와 data의 길이를 이용하여 index 지정
private int convertToIndex(int hashCode) {
return hashCode % data.length;
}
private Node searchKey(LinkedList<Node> list, String key) {
if (list == null) {
return null;
}
for (Node node : list) {
if (node.key().equals(key)) {
return node;
}
}
return null;
}
// Key를 통한 값 저장
public void set(String key, String value) {
int index = convertToIndex(getHashCode(key));
LinkedList<Node> list = data[index];
// 만약 해당 index에 값이 처음 입력되는 경우에는 LinkedList 생성
if (list == null) {
data[index] = new LinkedList<>();
}
Node node = searchKey(list, key);
if (node == null) {
list.addLast(new Node(key, value));
} else {
node.value(value);
}
System.out.println("hashCode: " + getHashCode(key) + ", index: " + index);
}
// Key를 통해 값 반환
public String get(String key) {
int index = convertToIndex(getHashCode(key));
LinkedList<Node> list = data[index];
if (list != null) {
for (Node node : list) {
if (node.key().equals(key)) {
return node.value();
}
}
}
return "Not Found";
}
}
class Node {
private String key;
private String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
public String key() {
return key;
}
public String value() {
return value;
}
public void value(String value) {
this.value = value;
}
}
출처
[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기
'기타 > 자료구조' 카테고리의 다른 글
| LinkedList(SinglyLinkedList vs DoublyLinkedList) (0) | 2023.07.15 |
|---|
