Chapter 11) 컬렉션과 프레임워크 - HashMap과 HashTable

◇ HashMap

Map Interface를 구현하였으므로 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{
	// 이를 통해 데이터 무결성을 확보
    transient Entry[] table;

    static class Entry implements Map.Entry{
        final Object key;
        Object value;
        ...
    }
}

 

◇ Hashing

해시함수(hash function)를 이용하여 데이터를 해시테이블에 저장하고 검색하는 기법

• 구현체 클래스:
  • HashSet, HashMap, Hashtable 등이 있다.
  • 가능하면 HashMap>Hashtable 사용

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

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

1. 검색하고자 하는 값의 key로 해시함수를 호출
2. 해시함수의 계산결과(hashCode)로 해당 값이 저장되어있는 LinkedList를 찾는다
3. LinkedList에서 검색한 key와 일치하는 데이터를 찾는다.

다만 LinkedList는 검색에 불리한 자료구조.

그래서 LinkedList의 크기가 커질수록 검색속도가 떨어진다.

하지만 배열의 경우에는 원하는 요소가 몇 번째에 있는지만 알면 아래의 공식에 의해 빠르게 원하는 값을 찾을 수 있다.

배열의 인텍스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n

하나의 LinkedList에 최소한의 데이터만 저장되기 위해서는

1. 저장될 데이터의 크기를 고려하여 HashMap의 크기를 적절하게 지정해주어야 하고
2. 서로 다른 Object에 대해서 중복된 해시코드의 반환을 최소화해야 한다. 
   • Object.hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일하다.
   • 단, String.hashCode()의 경우에는 문자열을 기반으로 생성하기 때문에 서로 다른 객체이더라도 문자열의 내용이 동일하면 hashCode의 값은 동일하다.

1page에 정리한 해시맵의 핵심 내용