해시 테이블 (Hash Table) 배우기

해시 테이블 (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 퍼포먼서도 문제가 됩니다.