해시 테이블 (Hash Table) 배우기 Part 1 - Hash Table 이란?

Java 의 컬렉션 클래스 (Collection Class) 중에 여러가지 Data Structure 가 있는데 그중에 Hash Table 에 대해서 알아 보겠습니다. 우선 Hash Table 은 왜 필요할까요? 그리고 Hash Table 가 가진 특징은 뭘까요? 그전에 Java 의 가장 기본적인 Data Structure 인 Array 와 Linked List 에 대해서 먼저 간단하게 복습해보죠.

Array 복습

Array 의 큰 특징은 정해진 사이즈와 저장되어 있는 데이터를 쉽게 인덱스 (index) 를 통해서 불러올수 있다는 점입니다. 예를 들어 한 사용자가 유능한 프로그래머인 당신에게 과일 이름을 관리해주는 프로그램을 만들어 달라고 부탁했어요. 그래서 당신은 보기와 같이 String 오브젝트를 10개 저장하기 위한 sampleList 란 이름을 가진 array 를 선언 (declare) 합니다.

String[] listFruit = new String[10];

그리고 몇가지 정보를 다음과 같이 지정합니다.

listFruit[0] = "사과";
listFruit[1] = "당근";
listFruit[2] = "오렌지";

그러면 sampleList 에는 3가지 String 오브젝트 데이터가 저장되어 있고 인덱스를 통해서 불어올수 있습니다.

// 사과를 첫번째 줄에 출력하고 오렌지를 두번째 줄에 출력한다
System.out.println(listFruit[0]);
System.out.println(listFruit[2]);

이처럼 array 의 가장 장점은 인덱스를 통해 정보를 쉽게 설정하고 불러올수 있다는 점입니다. 그렇지만 여기서 한가지 문제점이 있습니다. 이렇게 과일 이름은 10개면 충분할것 같아서 10개만 저장할수 있는 array 를 만들었는데 나중에 알고 보니 과일 이름이 몇백개가 넘는거에요. 그래서 당신은 다음과 같이 array 사이즈를 다시 제설정합니다.

String[] listFruit = new String[1000];

긴급한 문제는 해결되었지만 뭔가 부족한것 같습니다. 우선 1000 이라는 숫자가 충분해 보여도 과일들 종류가 더 많거나 미래에 더 종류가 많아진다면 어떻게 할까요? 그리고 큰 숫자를 지정하면 그만큼 남는 메모리도 낭비겠죠. 그렇다고 해서 사이즈가 커질때마다 새로운 array 를 만들어서 카피해 버리면 O(N) 이라는 Big-O 퍼포먼서도 문제가 됩니다.

아무래도 array 는 동적으로 커지는 (dynamically growing) 하는 데이터를 관리하기에는 문제가 있는것 같네요. 그렇다면 Linked List 는 어떨까요?

 Linked List 복습

Linked List 는 저장하고 싶은 데이터는 물론 그 다음 데이터를 포인터를 사용해 체인처럼 링크해주는 데이터 구조로 만들어져 있어서 Linked List 라고 부릅니다. Linked List 의 장점은 사이즈를 쉽게 줄이고 크게 만들수 있다는 점입니다. 데이터를 새로 더할려면 원래 연결되어 있는 부분을 끓어서 새로운 데이터를 붙이고 다시 연결 시켜주면 되니까요. 하지만 Linked List 의 단점은 쉽게 원하는 데이터를 찾을수가 없다는 점 입니다. 원하는 데이터를 찾기 위해서는 링크 전체를 횡당 (traverse) 시켜야 되니까 데이터를 찾는 시간이 O(N) 입니다.

그러면 Array 의 쉽게 데이터를 불러올수 있는 장점과 Linked List 의 쉽게 사이즈를 바꿀수 있는 장점을 합친 Data Structure 가 있을까요? 그래서 만들어진게 Hash Table 입니다.

Hash Table 이란?

Hash Table 은 빠른 insertion, deletion, 그리고 lookup 이 우선 순위일때 주로 사용되는 데이터 구조 입니다. Insertion, Deletion, 그리고 Lookup 의 Big-O 퍼포먼스가 O(1) 에 가깝습니다. 어떻게 그게 가능할까요?

Hash Table 은 hash function 이란 함수와 array 로 만들어져 있는 hash table 이 조합되어서 만들어져 있는 Data Structure 입니다. 여기서 Hash Function 을 만드는 방식은 다양한데 주로 mod (%) 를 사용해서 유일한 가격을 구합니다. Hash Table 에서 필요한 함수에는 put() 그리고 get() 두가지가 있습니다. 즉 다음과 같습니다.

public class HashMap
{
	Public void put(object key, object value);
	Public void get(object value);

}

하지만 array 와 Linked List 의 장점을 합친 Hash Table 에서도 Collision 이란 치명적인 단점이 있습니다. Collision 이란 hash function 을 통해서 맵핑되는 가정중에 다른 key 가 이미 데이터가 저장되어있는 Hash Table 의 슬롯으로 맵핑될때 부치지는 문제점을 말합니다. 다음시간에는 Collision 문제를 해결하는 방식인 Linear Probing 과 Separate Chaining 에 대해서 알아보겠습니다.