이 내용을 보기 전에 Java 의 Collection Framework 에 대한 기초적인 내용에 대해서 알아보고 싶은 경우 아래의 링크를 통해 내용을 확인할 수 있다. 자바의 HashMap Class에 대해 확인해보자.
https://hongjw1938.tistory.com/5?category=884192
자료구조(Java) - Collection Framework 2
이전 포스팅에 이어서 Map 인터페이스를 구현한 Collection Class들에 대해서 소개한다. ④ HashTable, HashMap, TreeMap HashTable은 Map 인터페이스를 구현한 Key - Value 쌍을 저장할 수 있는 형태의 Collectio..
hongjw1938.tistory.com
이번 포스팅에서는 HashMap에 대해 좀 더 깊이 들여다볼 수 있도록 진행할 예정이다. (내용이 많아 하나 하나 다루도록 할 예정)
우선 이전의 포스팅에서 기술하였듯이, HashMap은 Key - Value의 쌍으로 이루어진 자료구조로 Key 값은 중복되어서는 안되는 값으로 구성하여 Value 값이 그에 매칭되도록 저장하는 방식이다. 그렇다면 어떻게 중복되지 않은 Key를 만들까?
해싱(Hashing)
해싱이란 무엇일까? 위에 기술한 대로 Map 이라는 자료구조에선 Key는 중복되는 값이어서는 안된다. 해싱은 그것을 위한 기술이라고 볼 수 있다.
해싱은 어떠한 문자열 / Object 등의 데이터를 좀 더 짧고 인지하기 쉬운 숫자 등의 형태로 바꾸어 주는 것으로 해싱 작업으로 변경된 값이 기존의 값을 대표하도록 하는 방식을 의미한다.
이러한 해싱은 어떠한 값을 함수에 독립변수로 전달하여 그로 인한 결과물을 도출하는 것이라고 보면 된다. 즉, f(x) = y 가 되는 것이며, x가 원래의 값이라면 y는 해싱되어 나오는 결과값이다. f(x)는 해시 함수이다.
왜 이런 해싱이 필요한가? 해싱의 목적은 사실 여러 가지가 있다.
① 인덱싱
- 테이블에서 올바른 위치를 바로 찾을 수 있게 한다.
② 암호화 / 복호화
- 데이터를 알 수 없는 값으로 바꾸어 보호하고 인증된 사용자만이 볼 수 있게 한다.
③ 비교
- 대량의 데이터라면 전체를 비교하기 보다 짧은 해싱 결과값으로 비교하는 것이 더욱 효과적이다.
여기서 주로 살펴볼 것은 1번의 목적인 인덱싱이다.
예를 들어 우리가 저장소에 사람의 데이터를 저장하는데 이름을 Key로 사용하고 싶다고 생각해보자. 단순히 이름들을 그대로 사용하여 순서대로 저장하면 어떨까?
다음에 저장소에서 그 데이터를 찾을 때는 Character 간에 비교를 해가며 어쩌면 Full Scanning을 해야할지도 모른다.
만약 100만개의 데이터가 있다면 최악의 경우 100만번 째에서 데이터를 찾게 될수도 있다.
그렇다면 해싱을 이용하면 어떻게 다를까? 각각의 이름들을 간단한 숫자로 짧게 변경하여 그 값을 위치 기반으로 사용하여 저장할 수 있지 않을까?
다음에 데이터를 찾을 땐, Key를 전달하면 그 Key의 값을 가지고 해당 위치에서 바로 찾을 수 있는 것이다.
위의 그림 처럼 저장하면, 데이터를 검색 시 해싱 후 인덱싱된 값을 찾아 필요한 시간이 O(n)에서 O(1)로 줄어들게 된다.
그렇다면, 어떻게 해싱을 진행할까? 해시 함수의 예를 다음의 코드를 통해 살펴보자.
private Object[] hashArray;
public class HashTest{
public HashTest(int capacity){
hashArray = new Object[capacity];
}
// 전달된 Key값의 길이를 전체 저장소의 길이로 나눈 값으로 Indexing
private int hashCode(String key){
return key.length() % hashArray.length;
}
}
위의 예시 처럼, 해싱을 위한 method를 직접 구현하여 Key를 인덱싱할 수 있다.
인덱싱을 위한 해싱은, One-way operation이다. 즉, 닫시 원래의 값을 해싱된 값을 통해 찾아낼 필요가 없다.
즉, "reverse engineering" 이 불 필요하다. 실제로 좋은 해싱 함수는 그러한 방식으로 원래의 값을 유추할 수 있어서는 안된다.
또 하나 확인해야할 것은 충돌(Collision) 문제이다.
위의 예시를 다시 한 번 보자. 이름을 Key로 전달한다면 이름의 길이가 같다면 결국 배열의 동일한 위치에 저장될 것이다.
그렇다면 기존의 저장된 값을 덮어 쓰지 않겠는가?
그래서 실제로 이러한 충돌이 일어날 확률이 극도로 적은 함수가 좋은 함수이며, 충돌이 발생하더라도 그에 따른 대처가 가능한 구조로 만들어야만 한다. 이에 대해서는 추후 더 알아볼 것이다.
※ 간단한 해싱 방법 예
1) Sizing-Up 방식
- 저장소의 크기를 전체 Value의 가능한 크기만큼 미리 만들고 사용하는 방식
- 모든 데이터를 충돌 없이 저장할 수 있다는 장점이 있다.
- 작은 수준의 데이터 크기라면 문제 없지만 큰 데이터를 저장 시 어마어마한 메모리 낭비가 된다.
- 예를 들어, 13자리 주민 번호를 저장한다면 약 1조개의 저장 슬롯이 필요하다.
2) Division-remainder 방식
- 저장소의 크기를 전달 될 Parameter Key 값에 나누어 인덱싱하는 방식. 위의 예시가 이러한 방식이다.
- 이 방식은 충돌이 일어날 가능성이 많아 충돌에 대비한 추가적인 대책이 필요하다.
3) Folding 방식
- 이는 Key로 사용할 기존 값을 여러 부분으로 나누어 각 부분을 더해 4자리의 숫자를 만들어 인덱싱한다.
- 예로, 전화 번호가 123-4567 이라면 이것을 12, 34, 56, 7 로 나누어 다 더하고 저장소 크기로 나누어 인덱싱한다.
- 반드시 4자리로 만들 필요는 없다. 이 또한 충돌이 일어날 가능성이 높다.
4) Radix transformation 방식
- 이는 예를 들어 10진수 숫자의 Key를 16진수 등으로 바꾸듯이 다른 sequence로 인덱싱하는 방식
5) Digit rearragnement 방식
- 각 자리의 숫자를 상호 이동시키거나 거꾸로 돌리는 등의 작업을 해서 인덱싱 하는 방식
이외에도 다양한 좋은 해싱 알고리즘이 존재하며, 이러한 내용은 직접 검색을 해서 찾아보는 것이 더욱 유용하다. 각각의 내용이 깊이가 있고 이 부분에서 다루기 적합하지 않다.
※ 자바의 해싱 함수
자바의 모든 클래스들은 최상위인 Object 클래스를 상속 받는다. Object는 클래스에는 다음과 같은 hashCode 메소드가 있다.
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
@HotSpotIntrinsicCandidate
public native int hashCode();
자바의 해싱함수는 위의 코드와 같으며 이 코드는 내부적으로 각 값이 저장된 메모리 주소를 기반으로 해싱하여 각 데이터가 고유의 인덱싱된 값을 갖도록 하여 저장할 수 있게 된다.
자바의 Collections Framework는 각각의 사용 용도에 알맞게 위 hashCode 메소드를 오버라이딩하여 사용한다.
실제로 자바의 HashMap 클래스에서는 Key-Value 쌍으로 이루어진 데이터를 Entry 라는 개념으로 삽입하여 저장하는데, 이 때, 각 Entry Node를 정의하는 inner 클래스에 아래와 같이 정의되어 있다.
// 전달된 값을 기반으로 hashCode를 생성해 int 값으로 반환
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
충돌(Collision)
지금까지 해싱(Hashing)에 대해 알아보았으니, 이번엔 충돌(Collision)에 대해서 알아보자.
충돌은 이전에 말하였듯, 동일한 Key 값에 여러 Value 값이 매핑되는 경우를 말한다. 만약, 배열(array)를 만들어 사람에 대한 정보를 저장한다면, 여러 가지가 있겠지만 위의 예시 처럼 이름의 길이로 Key를 해싱한다고 하자.
그렇다면 이름의 길이가 3글자로 같은 경우가 많은 한국같은 국가에서는 거의 모든 Value 값이 index 3에 해당하는 배열의 위치에 저장되지 않을까? 이렇게 된다면 데이터의 무결성을 보장할 수 없게 된다.
이러한 충돌의 문제를 해결하는 방법은 무엇일까? 우선, 완벽한 해시 함수(Hash Function)을 구현한다면 어떨까? 어떠한 값을 넣더라도 절대 겹치지 않는 완전한 해시 함수를 구현하는 것이다.
그런데 이러한 방법이 과연 가능할까? 이런 만병통치약 같은 함수는 없을 것이다. 있다 하더라도 자료구조로 사용할 만큼의 성능이 충분할지도 의심스럽다.
다행이, 현실의 이러한 문제를 해결하기 위한 Rehashing 기법이 여럿 존재한다. 아래의 예시를 보자.
※ 충돌을 해결할 방법
1) Open Addressing
이 방법은 저장될 Table을 보고 충돌이 일어난다면 다른 비어 있는 장소를 찾아 이동하여 저장하는 방법이다. 이 방법은 여러 가지로 나뉠 수 있다 아래 예시들을 살펴보자.
① Linear Probing - 선형 조사
크기가 7인 배열이 있다고 생각해보자. 이 때, 저장할 값을 해시 함수를 통해 해싱하여 3이라는 Key로 만들었다고 가정한다. 그런데 만약 이미 3번 Index가 이미 값이 들어 있다면 충돌이 발생한다.
그러니 4번 Index가 비어있는지 확인한다. 또 충돌이 발생한다면 다음 Index로 넘어가는데 이 때, 최대 Index 값에 도달했다면 0번으로 돌아가서 순환하여 저장할 장소를 찾는 것이 Linear Probing 이다. 다음의 그림을 보자
위 그림과 같이, 저장할 값을 현재 배열의 크기로 나누어서 저장할 위치를 지정하면, 그 값이 각각의 Index에 저장된다. 그런데 47을 넣을 때, 47을 7로 나누면 5인데 이미 해당 위치에는 40이라는 숫자가 있어 충돌이 발생하였다.
따라서, 6번 Index를 확인했는데 또 충돌이 발생해 0번으로 돌아가 다시 순환하도록 구성된 것이다. 이를 코드로 구현한다면 아래와 같이 구현할 수 있다.
package com.test;
// Test 를 위한 Object 클래스 별도 생성
public class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId(){
return this.id;
}
public String getName(){
return this.name;
}
}
class LinearProbingMap {
private Employee[] hashTable;
public LinearProbingMap(){
// 배열 형태의 저장소로 구성
hashTable = new Employee[10];
}
// Employee의 id를 넘겨서 hashing할 것
private int hashKey(int id){
return id % hashTable.length;
}
// 이미 Employee 배열에 해당 value가 null이 아닌 상태인지 확인
private boolean occupied(int index){
return hashTable[index] != null;
}
// table에 value 넣는 method
public void put(Employee employee){
int hashedKey = hashKey(employee.getId());
// 이미 Value가 있다면, 즉 충돌이라면
if(occupied(hashedKey)){
// Linear Probing 하는 코드
int stopIndex = hashedKey; // 최초 시작 Index로 다시 이 값으로 온다는 것은 저장할 곳이 없다는 의미
if(hashedKey == hashTable.length - 1){ // 최대 Index 값 도달 시
hashedKey = 0;
} else {
hashedKey++;
}
// 만약 ++한 곳도 이미 value가 있고 기존의 hash 값과 같지 않은 경우라면,
// 1을 한 번 더 더하고 length를 나눔. 왜 나누냐면 length 이상으로 가면 값을 넣을 수 없으니까
while(occupied(hashedKey) && hashedKey != stopIndex){
hashedKey = (hashedKey + 1) % hashTable.length;
}
}
// 위에서 Linear probing을 했지만 그래도 안된다면 array가 full한 상태
if(occupied(hashedKey)){
System.out.println("Sorry, you can't put any more value into that index" + hashedKey);
} else {
hashTable[hashedKey] = employee;
}
}
// key를 바탕으로 해당 key와 일치하는 key를 찾아야함.
private int findKey(int id){
int hashedKey = hashKey(id);
// key를 hashing 시에 null이 아니고, hasing한 key로 저장한 table의 key가 찾는 key와 일치 시
if(hashTable[hashedKey] != null && hashTable[hashedKey].id == id){
return hashedKey;
}
// 일치하지 않는 다면 아래의 반복을 수행하여 Linear Probing
int stopIndex = hashedKey;
if (hashedKey == hashTable.length - 1) {
hashedKey = 0;
} else {
hashedKey++;
}
while (hashedKey != stopIndex
&& hashTable[hashedKey] != null
&& !hashTable[hashedKey].id == key) {
hashedKey = (hashedKey + 1) % hashTable.length;
}
if(hashTable[hashedKey] != null && hashTable[hashedKey] == key){
return hashedKey;
} else {
return -1;
}
}
}
② Quadratic Probing - 이차원 조사
Linear Probing 바로 다음 저장소 위치를 확인했다면 이는 충돌 발생 시 다음 Index와의 차이의 제곱을 더한 만큼 이동 시켜 조사하는 방법이다.
예를 들어 100의 크기의 배열이 있는데 해싱 후 Key 값이 5가 나왔다고 하자.
1번 충돌 발생 시 : 5 + (1^2) = 6 Index 조사
2번 충돌 발생 시 : 5 + (2^2) = 9 Index 조사
3번 충돌 발생 시 : 5 + (3^2) = 14 Index 조사
위와 같은 방식으로 조사를 하는데 Linear Probing의 경우에는 바로 인접한 경우를 우선적으로 찾기 때문에 특정 Index 근처로 군집(Clustering) 현상이 발생할 수 있다.
이 방식으로 하면 그러한 문제를 해결할 수는 있지만 이 또한 초기 해시 Key 값이 유사하다면 유사한 군집이 군데 군데 나타나게 된다. 이것을 2차 군집(Secondary Clustering) 이라고 한다.
군집 현상이 발생한다는 것은 전체 저장소 내 충돌이 그만큼 많이 발생한다는 의미이다. 이로 인해 저장소 내 값을 찾거나 새로운 값을 저장 시 성능이 비효율적으로 동작할 수 있게 된다.
이러한 Probing 방식의 문제점은 데이터를 중간에 삭제했을 경우이다. Table 내 검색을 할 때도 Probing을 해가며 찾게 되기 때문에 삭제 후 중간에 값이 비어있다면 검색 중에 문제가 발생할 수 있다.
따라서, 삭제 후 해당 부분에 별도의 "DELETED" 표식을 하거나 삭제 후 Rehashing(재해싱)을 다시 수행해야 한다. Rehashing을 한다면 성능에 영향이 있을 수 있다.
이외에도 더블 해싱(해싱을 2번 수행)하는 등의 방법도 있다.
2) Chaining
Chaining은 하나의 저장소 위치에 다수의 값들을 저장할 수 있도록 구현한 방식이다.
예를 들어, 기존에 배열을 생성해 각 Key를 기반으로 Indexing하여 저장하였는데, 이 저장될 위치 각각을 ArrayList / LinkedList 등의 List 형태로 구현하여 충돌이 발생하면 동일한 Key에 복수의 값이 저장되도록 구현하는 것이다.
그림으로 곧바로 이해해보자.
위의 그림과 같이 각 Indexing된 위치에 여러 개의 값들이 연결되어 저장된 것을 확인할 수 있다. 때문에 데이터를 찾을 때도, 해당 Key의 위치로 가서 선형 탐색을 수행하게 된다.
데이터를 추가로 넣을 때에는, LinkedList 방식이라면 Head에 데이터를 넣고, ArrayList 방식이라면 마지막에 데이터를 넣을 것이다. LinkedList라면 탐색을 통해 끝까지 가야 하고, ArrayList 라면 첫 부분에 넣으면 다시 다 옮겨야하기 때문이다.
데이터를 찾을 때는, 전달된 Key를 해싱 후 위치를 찾아 선형 탐색을 해가며 해싱되기 전의 Key 값을 비교하여 찾고자 하는 데이터를 반환하는 방식으로 수행된다.
이 방식으로 구현 시에는 데이터가 특정 Index에 몰려들지 않도록 구현하는 것이 중요하다. 자바에서는 실제로 위와 같은 방식으로 HashMap 클래스를 구현하였다. 아래의 코드 처럼 간단히 구현해볼 수 있다.
package com.test;
import java.util.LinkedList;
import java.util.ListIterator;
public class ChainedHashTable {
private LinkedList<Employee>[] hashTable;
public ChainedHashTable(){
hashTable = new LinkedList[10];
// 배열의 각 부분에 LinkedList 객체 추가함
for(int i=0; i < hashTable.length; i++){
hashTable[i] = new LinkedList<Employee>();
}
}
private int hashKey(int id){
// return id % hashTable.length;
return Math.abs(id.hashCode() % hashTable.length);
}
public void put(Employee employee){
int hashedKey = hashKey(employee.getId());
hashTable[hashedKey].add(employee);
}
public Employee get(int id){
int hashedKey = hashKey(id);
// iterator 객체를 통해 정확한 객체를 반환하기 위해 LinkedList를 탐사사
ListIterator<Employee> iterator = hashTable[hashedKey].listIterator();
Employee employee = null;
while(iterator.hasNext()){
employee = iterator.next();
// 정확한 해당 객체를 찾으면 break
if(employee.getId() == id){
return employee;
}
}
return null;
}
public Employee remove(int id){
int hashedKey = hashKey(id);
ListIterator<Employee> iterater = hashTable[hashedKey].listIterator();
Employee employee = null;
// NullPointerException 방지
int index = -1;
while(iterater.hasNext()){
employee = iterater.next();
index++;
if(employee.getId() == id){
break;
}
}
if(employee == null){
return null;
} else {
hashTable[hashedKey].remove(index);
return employee;
}
}
public void printHashtable(){
for(int i=0; i < hashTable.length; i++){
if(hashTable[i].isEmpty()){
System.out.println("Position " + i + " : empty");
} else {
System.out.print("Position " + i + " : ");
ListIterator<StoredEmployee> iterator = hashTable[i].listIterator();
while(iterator.hasNext()){
System.out.print(iterator.next().employee);
System.out.print(" -> ");
}
System.out.println("null");
}
}
}
}
이렇게 간단히 해싱과 충돌에 대해 알아보았다. 이러한 배경 지식을 바탕으로 다음 포스팅에서 자바의 HashMap에 대해 더 깊이 살펴보는 포스팅을 진행할 것이다.
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 트리(Tree), 이진 트리(Binary Tree) (0) | 2020.08.22 |
|---|---|
| 자료구조 - HashMap 들여다보기(2) (1) | 2020.08.20 |
| LinkedList 직접 구현해보기 (Java) (0) | 2020.08.15 |
| ArrayList 직접 구현해보기 (Java) (0) | 2020.08.05 |
| 자료구조(Java) - Comparable / Comparator (2) | 2020.07.27 |
