[JAVA] 컬렉션프레임워크(CollectionFramework) 5 - HashMap

Map 구현체

HashMap

---

Hashtable과 HashMap은 Vector와 ArrayList와 같은 관계이다. (새로운 버전인 HashMap을 사용할 것을 권장하고 있다.)

Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖고있다.

그리고 해싱(hashing)을 사용하기 때문에 데이터검색에 뛰어난 성능을 보인다.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{
    transient Entry[] table;
 
    static class Entry implements Map.Entry{
        final Object key;
        Object value;
    }
}

HashMap에서 Entry라는 내부 클래스를 정의하고, 다시 Entry 타입의 배열을 선언하고 있다.

키는 저장된 값을 찾는데 사용되기 때문에 유일(unique)해야 한다.

public class MapTest {
    public static void main(String[] args){
        Map<String, String> phoneInfo = new HashMap<>();
        
        phoneInfo.put("홍길동", "00-000-0000");
        phoneInfo.put("임꺽정", "01-000-0000");
        phoneInfo.put("닌자"  , "02-000-0000");
        phoneInfo.put("대통령", "03-000-0000");
        
        // Map에서 Key 모음 가져오기
        Set<String> names = phoneInfo.keySet();
        System.out.println("주소록에 있는 사람들 : " + names);
        
        // Map에서 value 모음 가져오기
        Collection<String> numbers = phoneInfo.values();
        System.out.println("주소록전화번호 모음 : " + numbers);
        System.out.println();
        
        // Map에서 Entry가져와서, Entry에서 key와 value 가져오기
        Set<Map.Entry<String, String>> entrySet =  phoneInfo.entrySet();
        Iterator<Map.Entry<String, String>> iter = entrySet.iterator();
        while(iter.hasNext()){
            Map.Entry<String, String> entry = iter.next();
            System.out.println("주소록에 있는 사람들 : " + entry.getKey());
            System.out.println("주소록전화번호 모음 : " + entry.getValue());
        }
    }
}

-- result --

주소록에 있는 사람들 : [닌자, 홍길동, 임꺽정, 대통령]

주소록전화번호 모음 : [02-000-0000, 00-000-0000, 01-000-0000, 03-000-0000]

주소록에 있는 사람들 : 닌자

주소록전화번호 모음 : 02-000-0000

주소록에 있는 사람들 : 홍길동

주소록전화번호 모음 : 00-000-0000

주소록에 있는 사람들 : 임꺽정

주소록전화번호 모음 : 01-000-0000

주소록에 있는 사람들 : 대통령

주소록전화번호 모음 : 03-000-0000

해싱(Hashing)

---

HashMap과 HashSet 등에서 사용되는 해싱(hashing)에 대해 알아보자

해싱이란 해시함수(hash function) 을 이용해서 데이터를 해시테이블(hashtable)에 저장하고 검색하는 기법을 말한다.

해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 대량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합으로 되어 있다. (자바에서는 첨자(index)를 갖고 있는 배열방을 동적으로 늘려서 링크드리스트와 1:1관계를 유지시켜, 검색시간을 상수시간으로 유지시킨다고 한다.)

(이미지 출처)

저장할 데이터의 키를 해시함수에 넣어서 나온 결과 값을, 배열의 첨자로써 사용하고 그 곳에 연결되어 있는 링크드리스트에 저장하게된다.

(hashtable 관련 포스팅)

해싱을 구현하는 과정에서 제일 중요한 것은 해시함수 알고리즘이다. 

해시함수가 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야지 성능이 좋아지기 때문이다. 

(링크드리스트는 검색에 불리한 자료구조이기 때문에, 길어질 수록 성능이 나빠지기때문이다.)

실제로는 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다.

(Object클래스에 정의된 hashCode()는 객체의 주소를 이용한다.)

String 클래스의 경우에는 Object에서 상속받은 hashCode()를 오버라이딩하여서, 다른 String 인스턴스여도(주소가 달라도) 같은 내용의 문자열을 가졌다면 같은 해시코드를 리턴해준다.

HashSet에서와 마찬가지로 서로 다른 두 객체에 대해 eqauls()의 결과가 true이면서  hashCode()의 반환값이 같아야 같은 객체로 인식한다.

따라서 새로운 클래스를 정의할 때 eqauls()를 오버라이딩한다면 hashCode()도 같이 오버라이딩 해줘야 한다.

(equals()가 true이면 hashCode() 결과값은 항상 같아야한다.)

그렇지 않으면 HashMap에서 데이터를 넣을 때 해시 코드가 다른 두 객체를 서로 닫른 것으로 인식하고 따로 저장할 것이다.

treeSet의 예제코드같은 상황이 발생할 수 있다..

Set set = new HashSet();
set.add(new Pserson("kang", 28));
set.add(new Pserson("kang", 28));
 

set : [Person [name=kang, age=28], Person [name=kang, age=28]]

(출처 : JAVA의 정석)