컬렉션 프레임워크 (3)

HashMap과 Hashtable

Hashtable과 HashMap의 관계는 Vector와 ArrayList의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용할 것을 권한다.
HashMap은 Map을 구현했으므로 Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터로 저장한다는 특징을 갖는다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{

    transient Entry[] table;
    
    static class Entry implements Map.Entry {
    	final Object key;
        object key;
    }
    
}

HashMap은 Entry라는 내부 클래스를 정의하고, 다시 Entry타입의 배열을 선언하고 있다. 키(key)와 값(value)은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기 보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성적인 측면에서 더 바람직하기 때문이다.

HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉 (Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.

키(Key) 컬렉션 내의 키(key) 중에서 유일해야 한다.
값(value) 키(key)와 달리 데이터의 중복을 허용한다.

ex) 한정된 범위 내에 있는 순차적인 값들의 빈도수는 배열을 이용하지만, 한정되지 않은 범위의 빈순차적인 값들의 빈도수는 HashMap을 이용해서 구할 수 있다.

해싱과 해시함수

해싱이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap 등이 있다.

해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 되어 있다.

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결 되어 있는 링크드 리스트에 저장하게 된다.

실생활에 비유한 예를 들어보자면, 한 간호사가 많은 환자들의 데이터 중에서, 원하는 환자의 데이터를 쉽게 찾을 수 있는 방법이 없을까를 고민하다가 주민등록번호의 맨 앞자리인 생년을 기준으로 데이터를 분류해서 10개의 서랍(배열)에 나눠 담는 방법을 생각해놨다. 예를 들면 71년생, 72년생과 같은 70년대생 환자들의 데이터는 같은 서랍에 저장된다. 이렇게 분류해서 저장해두면 환자의 주민번호로 태어난 년대를 계산해서 어느 서랍에서 찾아야 할지를 쉽게 알 수 있다.

해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘이며, 위의 예에서 사용된 해시함수의 알고리즘은 주어진 키(주민번호)의 첫번째 문자를 뽑아서 정수로 반환하기만 하면 되는 것이다.

실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다. Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이다.

String클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다. 그래서 서로 다른 String인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출하면서 같은 해시코드를 얻는다.

HashSet와 마찬가지로, 서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. HashMap에서도 같은 방법으로 객체를 구별하여, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.
그래서 새로운 클래스를 정의할 때 euqals()를 재정의 오버라이딩해야 한다면 hashCode()도 같이 재정의해서 equals()의 결과가 true인 두 객체의 해시코드 hashCode()이 결과 값이 항상 같도록 해주어야한다. 그렇지 않으면 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 equal()의 호출결과가 true지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.

TreepMap

TreeMap은 이름에서 알 수 있듰이 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다. 그래서 검색과 정렬에 적합한 컬렉션 클래스이다.

검색에 관한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하자!

정리

각 컬렉션 클래스마다 장담점이 있으므로 구현원리와 특징을 잘 이해해서 상황에 가장 적합한 것을 선택하여 사용할 줄 알아야한다.

컬렉션	특징
ArrayList	배열기반. 데이터의 추가와 삭제에 불리, 순차적인 추가삭제는 제일 빠름.임의의 요소에 대한 접근성(accessibility)이 뛰어남
LinkedList	연결기반. 데이터의 추가와 삭제에 유리. 임의의 요소에 대한 접근성이 좋지 않다.
HashMap	배열과 연결이 결합된 형태. 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고성능을 보인다
TreeMap	연결기반. 정렬과 검색(특히 범위검색)에 적합. 검색성능은 HashMap보다 떨어짐
Stack	Vector를 상속받아 구현
Queue	LinkedList가 Queue인터페이스를 구현
Properties	Hashtable을 상속받아 구현
HashSet	HashMap을 이용해서 구현
TreeSet	TreeMap을 이용해서 구현
LinkedHashMap LinkedHashSet	HashMap과 HashSet에 저장순서유지기능 추가

그동안 '자바의 정석'을 참고하며 컬렉션 프레임워크를 정리하였다.
백엔드 개발자가 되기 위해, 스프링과 JPA에 대해서 학습하는것도 매우 중요하지만 가장 기초가 되는 자바 언어를 탄탄히 학습할 필요를 느꼈다. 앞으로도 '자바의 정석'책을 참고하여 겉으로만 알고 있는 자바 지식을 다시 한번 꼼꼼히 점검할 필요가 있는 거 같다.