HashMap

Hyeonsu Bang·2021년 9월 14일

Java Basic

목록 보기

1/11

HashMap

Map 을 구현하는 대표적인 클래스.

Key를 저장할 때 hash function을 사용하므로 HashMap이라 한다. Value가 저장될 때 key 값이 hashing 처리되고, 처리된 hash code가 compressed되어 index를 생성한다. 해당 index에 entry가 저장된다. 특징을 정리해보면 다음과 같다.

특징

Map의 성질을 가지고 있으므로 Key, Value pair의 구조를 가지고 있는 Entry 클래스로 데이터를 관리한다.
Key 는 반드시 객체여야 한다. 데이터를 저장하고 데이터에 접근할 때, Object의 hashCode()와 equals()를 통해 Key가 일치하는지 확인하기 때문이다. 기본자료형으로 Key를 지정하면 Wrapper class에 의해 boxing 된다.
논리적으로 같은 키의 값이 중복으로 입력되면, 마지막으로 입력된 키와 paring된 값으로 업데이트 된다. 즉 중복 키가 허용되지 않는다.
Key와 Value 에 null이 참조될 수 있다. 하지만 필요하지 않은 경우 지양해야 할 것이다.
배열 기반의 Map이다. 데이터를 검색할 때 hash로 접근하므로 단순 저장/검색으로 계산했을 때 평균 O(1)의 time complexity를 가진다. 따라서 저장된 데이터에 순차적으로 접근하여 검색하는 ArrayList보다 검색 속도가 빠르다. 검색하고자 하는 데이터가 정렬되어 있다면 O(n), binary search를 한다면 O(log n)까지 성능이 올라갈 수 있다. HashMap의 가장 큰 특징이라고 할 수 있다.
하지만 각 entry의 입력 순서를 기억하지 않으므로 데이터가 입력되는 순서가 중요하다면 LinkedHashMap을 사용하는 것이 선택지가 될 수 있다.
내부적으로 동기화가 되지 않기 때문에 multi thread 환경에서 HashMap에 대한 구조적인 변경(value 변경이 아닌 add나 delete, remove과 같이 entry를 조정하는 등의 변경)을 대비해 반드시 외부적으로 동기화를 선언해주거나, Collections.synchronizedMap(new HashMap()); 과 같이 동기화 설정을 해주는 것이 좋다. (동기화에 대해서는 개념만 알고 있기 때문에 지금은 이 정도로만 써둔다)

TL;DR

Hashing function을 사용하는 Map이다.

단순 데이터 탐색, iteration을 할 경우 ArrayList보다 훨씬 빠르다.

Key 중복이 안된다.

HashMap을 이루고 있는 개념

HashMap을 비롯한 Map 컬렉션을 구현하는 클래스들은 대부분 아래와 같은 개념으로 이루어져 있다.

Bucket

HashMap은 앞서 말한 것처럼 배열 기반의 Map이며, 각 array 내의 node를 bucket이라고 한다. entry, 저장된 요소를 bucket이라고 보면 되겠다.

Capacity

저장할 수 있는 bucket 의 수. HashMap의 용량 정도라고 생각하면 되겠다. HashMap은 기본 생성자로 생성할 경우 기본 capacity가 16이다. HashMap을 생성할 때에 생성자의 인자로 capacity를 설정해줄 수 있다

Threshold

역치. HashMap에 저장 공간이 커져야 되는 시점이다. load factor * capacity로 계산할 수 있다. load factor는 언제 값이 늘어나야 하는지 정해주는 단위이다. 기본 설정은 0.75f 로, 이는 capacity의 75%를 말한다.

예를 들어 기본 생성자로 HashMap을 생성했다고 하면, capacity는 16, load factor는 0.75f로 설정되어 있어, threshold는 16 * 0.75 = 12 이다. 즉 해당 HashMap은 16개의 entry를 저장할 수 있으며, map의 size가 12개에 도달했을 때 HashMap의 크기가 커지게 된다. 크기는 두 배 가까이로 커지게 된다. 따라서 16이었던 크기는 32로 커지게 된다.

Rehashing

HashMap이 threshold에 도달해 크기가 커질 때 내부적으로 모든 bucket에 대해 rehashing이 발생한다. 구조적인 변경이 발생한다는 의미이다. load factor를 낮게 설정해서 complexity를 낮출 수는 있지만, 그만큼 rehashing이 자주 일어날 수 있다. rehashing 자체가 자원 소모가 큰 편이므로 HashMap에 저장될 데이터가 예측 가능하다면 capacity를 적절히 높이 설정하여 이런 문제를 어느 정도 해결 할 수 있겠다.

HashMap methods, constructor

constructor

생성자는 기본 생성자와 더불어 위에서 언급한 capacity, load factor를 파라미터로 하는 생성자와, Map 구현 클래스를 파라미터로 받는 생성자가 있다.


HashMap<String, String> bandNameAndCountry = new HashMap<>;
bandName.put("radiohead", "Britain");
bandName.put("interpol", "America");

HashMap<String, String> bandNameAndCountry2 = new HashMap<>(bandNameAndCountry);

System.out.println(bandNameAndCountry.equals(bandNameAndCountry2)); // true

method

Map의 메서드를 모두 구현하고 있다. put, get, remove, containValues 등을 모두 사용할 수 있다.

getOrDefault

JDK 1.8부터 추가된 기능. Key를 통해 값을 얻어오지만, Key 가 존재하지 않거나 Key에 매핑된 Vaule가 없는 경우 default 값을 지정해서 리턴시킬 수 있다.

HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("hungry", "yes");
System.out.println(hashMap.getOrDefault("thirsty", "yeah")); // yeah

후술할 entrySet()과 keySet(), values() 등을 통해 HashMap을 iterate시킬 수 있다.

HashMap 기본 활용

HashMap의 entry를 다양한 방법으로 출력할 수 있다.

hashMap 예제

HashMap<String, String> hashMap = new HashMap<String, String>();
hashMap.put("food1", "hamburger");
hashMap.put("food2", "pizza");
hashMap.put("food3", "ramen");
hashMap.put("food4", "ramen");

entrySet()

Map의 entry를 Set view로 만든 뒤 iterate 시키는 방법이다.

for(Map.Entry<String, String> entries : hashMap.entrySet()) {
	System.out.println("key :"+ entries.getKey() + " value : "+entries.getValue()); 
}

//key :food1 value : hamburger
//key :food3 value : ramen
//key :food2 value : pizza
//key :food4 value : ramen

앞서 설명했듯 HashMap에서는 데이터의 저장 순서가 중요하지 않기 때문에, iterate 시켰을 때 순서가 다르게 나올 수도 있다.

keySet()

Key만 Set view로 변환하여 해당 Key를 통해 get()로 iterate하는 방법이다.

		
for(String s : hashMap.keySet()) {
	System.Out.println("key + "+s + " value : "+hashMap.get(s));
}

//key :food1 value : hamburger
//key :food3 value : ramen
//key :food2 value : pizza
//key :food4 value : ramen

Iterator 활용

Map을 iterate 시킬 때 사용하는 Iterator를 활용할 수 있다.

Iterator<Entry<String, String>> entries = hashMap.entrySet().iterator();
		
while(entries.hasNext()) {
	Entry<String, String> entry = entries.next();
	System.out.println(entry.getKey() + entry.getValue());
}

keySet() 를 통해 위 예제와 같이 get(key)로 iterate 시켜도 된다.

두 개의 HashMap 비교

두 개의 HashMap을 비교하고자 한다면 equals()를 통해 비교할 수 있다. 기본적으로 equals()가 객체에서 사용되었을 때에는 두 객체가 같은 인스턴스를 참조하고 있는지 확인하지만, HashMap에 equals()를 사용했을 때에는 두 개의 HashMap이 가지고 있는 entry들이 논리적으로 동등한지에 대해서만 확인한다. 앞에서 언급했듯 entry의 순서는 상관이 없다. 예를 들어서

HashMap<Integer, String> map1 = new HashMap<>();
 
map1.put(1, "A");
map1.put(2, "B");
map1.put(3, "C");
 
//Same as map1
HashMap<Integer, String> map2 = new HashMap<>();

map2.put(3, "C");
map2.put(1, "A");
map2.put(2, "B");
 
//Different from map1
HashMap<Integer, String> map3 = new HashMap<>();

map3.put(1, "A");
map3.put(2, "B");
map3.put(3, "C");
map3.put(3, "D");
 
System.out.println(map1.equals(map2));  //true
System.out.println(map1.equals(map3));  //false

위와 같을 경우 map1과 map2가 모두 new 키워드를 통해 생성된 객체이지만 equals() 비교 시 true가 리턴된다.

Key의 불변성 (immutability)

HashMap에서 POJO를 Key로 사용할 때에는 equals()와 hashCode()를 오버라이딩해서 논리적으로 동등한(객체의 데이터가 같은) 비교를 할 수 있도록 해야 한다. Key가 hashCode()의 값으로 저장되는데, 값을 가져올 때에 hashCode()로 bucket의 위치를 찾은 다음, 저장되어있는 hash code와 일치하는지 equals()로 판단한다. 따라서 hashCode()의 결과값이 같더라도 equals()에서 다른 값이라고 판단되면 다른 키로 인식하여 원하지 않는 결과가 나올 수 있다.

다음의 예를 보면

public class MutableKey{
	private String name;

	@Override
	public boolean equals(Object o){
		// 같은 인스턴스를 참조하고 있으면
		if(this == o){
			return true;
		}

		// 파라미터로 받은 객체가 null을 참조하거나 둘의 인스턴스가 다르면
		if(o == null || this.getClass() !=o.getClass()){
			return false;
		}

		MutableKey that = (MutableKey) o;

		//두 데이터의 값 일치를 비교해서 결과 리턴
		return Objects.equals(name, that.name);
	}

	@Override
	public int hashCode(){
		// name이 같을 경우 같은 hashcode 리턴
		return Objects.hash(name);
	}
}

이렇게 Key로 사용할 POJO 내에서 equals()와 hashCode()를 overriding 했을 경우, MutableKey 클래스의 name 필드를 따로 변경하지 않는 이상 HashMap의 키로 사용해도 항상 같은 hashcode를 리턴할 것이다.

HashMap<MutableKey, String> hashMap = new HashMap<MutableKey, String>();

hashMap.put(new MutableKey("name"), "John Doe");
String value = hashMap.get(new MutableKey("name"));
System.out.println(value); // John Doe

하지만 name field를 변경한 뒤 HashMap에서 값을 얻어오려고 하면, 변경된 변수에 대한 hash code를 가진 Key에 접근하려 하는 것과 같으므로 저장된 Value가 없어 null을 리턴하게 된다.

MutableKey key = new MutableKey("John Doe");

hashMap.put(key, "happy");
System.out.println(hashMap.get(key)); // happy

key.setName("punch");
System.out.println(hashMap.get(key)); // null