[자료구조] HashMap 파헤치기 2 ( keySet(), values(), iterator() )

 

 

 

 

지난 포스팅에서는

HashMap의 기본 개념에

대해서 다루었다.

 

 

HashMap은 key와 value로 구성된 Map 데이터를 해싱함수를 통해 산출된 인덱스 위치의 버킷(배열)안에 저장하는 자료구조이다. 해싱함수(function)는 key 값(X)을 받아 인덱스(Y)를 산출한다.

 

그래서 key값을 알면, 버킷의 위치를 바로 알 수 있어 HashMap은 시간 복잡도가 O(1)인 빠른 성능을 자랑한다. 그러나 key는 무한하지만 인덱스는 한정되어 있어 key들 간의 인덱스를 향한 충돌은 불가피하다. 그래서 충돌이 일어나는 인덱스에 또 다른 자료구조가 만들어 지는데 충돌 초기에는 Linked List 방식으로 Map 데이터가 저장된다.

 

그러다가 충돌횟수가 어느 임계점을 넘으면 Linked List 방식의 시간복잡도 O(n)의 성능은 효율성이 떨어진다. 그래서 임계점을 넘은 인덱스 위치의 자료구조는 Red-Black Tree로 바뀌어 탐색 성능을 O(log n) 까지 끌어 올린다.

 

여기까지가 지난 포스팅에서 다루었던 내용이다. 오늘은 HashMap의 메소드들에 대해서 파헤쳐 보겠다.

 

Map 데이터

 

 

 

HashMap 클래스 안에는 중첩 클래스로 Node 클래스가 있다. Node 클래스는 HashMap의 버킷 안에 저장될 Map 데이터이다. Node 객체는 필드값으로 key와 value를 갖고 있으며 key는 final로 선언되어 한번 초기화되면 수정이 불가능하다.

 

Node클래스의 가장 큰 특징은 Map.Entry<K,V> 인터페이스를 implements한다는 것이다. Map.Entry<K,V>는 Map 인터페이스의 중첩 인터페이스이다. 인터페이스를 implements 하면 구현클래스는 해당 인터페이스의 형식을 지켜야 한다. 그러므로 Map.Entry<K,V>의 구현클래스가 Node<K,V> 클래스인 것이다.

 

 

Map.Entry<K,V> 인터페이스의 추상메소드들이다. 해당 인터페이스를 구현하려면 기본적으로 key와 value를 반환하는 로직(getKey(), getValue())과 value를 재설정하는 로직(setValue())을 구현해야한다. key는 final 속성으로 수정이 불가능하므로 setKey()는 없다.

 

로직을 구현한다 하더라도, Map.Entry<K,V>의 메소드들은 get과 set 같은 기본적인 작업만 가능하다. 좀 더 구체적이고 복잡한 데이터 조작을 위해서는 key와 value를 개념적으로 구분할 필요가 있다.

 

keySet() 과 values()

 

HashMap에서 데이터를 "개념적으로" 3개 집단으로 나눌 수 있다.

 

1. key 의 집합 ( Set<K> keySet() )

2. value 의 집합 (Collection<V> values() )

3. key와 value를 합친 Node 객체의 집합 (Set<Map.Entry<K,V>> entrySet() )

 

쉬운 이해를 위해, 3번은 제외하고 key 집합과 value 집합만 다루어 보겠다. 두 집합은 서로 성격이 다르니, 성격에 따라 다르게 개발자에 의해 분리되어 활용되어질 수 있다. 그러므로 Node로 묶여있는 key 필드와 value 필드에 독립적으로 접근 가능한 접근모듈을 만들어 줄 필요가 있다. 그것이 바로, keySet()과 values()이다.

 

 

 

keySet()과 values()는 접근 모듈의 기능을 구현할 객체가 필요하다. 그래서 HashMap 클래스는 중첩 클래스로 KeySet 클래스와 Values 클래스를 갖고 있다. KeySet 중첩 클래스는 Set 인터페이스에서 왔고 Values 중첩 클래스는 Collection 인터페이스에서 왔다.

 

 

 

 

 

KeySet 객체의 메소드를 통해 Node의 key 필드에 접근하여 반환한다. 그리고 Values 객체는 메소드를 통해 Node의 value 필드에 접근하여 반환한다. 이렇게 key 필드와 value 필드는 접근모듈로 인해 분리되어 접근이 가능한데, 이때 유용하게 사용가능한 모듈이 반복자( iterator() )이다.

 

iterator()

 

 

 

접근모듈의 기능을 구현하는 KeySet 클래스를 살펴보자. 메소드에 iterator()가 있다. iterator는 반복자를 의미한다. 반복자는 중요한 메소드이다. HashMap은 버킷에 Map 데이터를 index 순서대로 저장하지 않는다. 그래서 단순히 for문이나 while 문으로 탐색하지 못한다. 탐색에 필요한 모듈인 iterator()가 필요하다.

 

 

 

 

접근 모듈 세 가지, KeySet, Values, EntrySet은 모두 각자의 iterator를 갖고 있다. KeySet은 KeyIterator(), Values는 ValueIterator(), EntrySet은 EntryIterator()를 갖는다.

 

 

Iterator 인터페이스 추상메소드는 3개다. hasNext()는 자료구조 안에 데이터의 유무를 확인하는 메소드, next()는 데이터가 있다면 데이터 하나 가져오는 메소드, remove()는 가장 최근에 next()를 통해 가져왔던 데이터를 자료구조 안에서 삭제하는 메소드이다.

 

 

Iterator 인터페이스를 implements하면 위의 세 가지 추상메소드를 구현해야한다. hasNext()와 remove()는 KeyIterator 클래스, ValueIterator 클래스, EntryIterator 클래스에서 모두 같은 로직이기에 코드의 중복을 방지하고자 HashIterator 클래스를 상속하여 처리했다.

 

 

 

 

next()는 로직은 같지만 접근하는 필드가 다르므로 iterator 종류별로 클래스에 구현되어 있다. KeyIterator는 접근한 Map 데이터(Node객체) 의 key 필드 안에 저장된 key 객체 주소를, ValueIterator는 Node 객체의 value 필드 안에 저장된 value 객체 주소를, EntryIterator는 Node 객체의 주소를 반환한다.

 

 

 

각 클래스는 next()는 HashIterator로 부터 상속한 nextnode()를 호출한다.

 

Iterator 객체가 생성되면 current 필드에는 next()로 반환될 Node 객체가, next 필드에는 다음 next() 호출 시, 반환될 Node 객체가 저장된다. next()가 호출될 때마다, current 필드와 next 필드가 바뀌면서 Node 객체가 하나씩 반환된다.

 

그러므로 Iterator 반복자는 재사용이 불가능하다. next와 current가 next 메소드가 호출된 횟수에 따라 달라지고 객체 안에 저장되기 때문이다. 그러므로 재사용하려면 새로 반복자 객체 하나를 다시 생성해야 한다.

 

 

 

 

많은 컬렉션 프레임원크 자료구조가 iterator 인터페이스를 상속한다. Iterator 인터페이스로 많은 자료구조의 반복자를 통일시키면, 자료구조가 추후에 바뀌더라도, iterator 구현 객체만 갈아끼우면 되기에 유지보수에 용이해지기 때문이다.

 

Set<K> keySet = map.keySet(); // Node 객체의 Key 필드 접근 모듈 객체 생성
Iterator<K> iterator = keySet.iterator(); // key 필드 반복자 생성
while(iterator.hasNext){ ... } // 반복자 사용

 

이렇게 Set 자료구조(keySet) 의 반복자를 사용하다가 Collection 자료구조의 반복자로 바꾸어야 하는 상황이이라면 반복자 생성 부분의 구현 객체만 수정해주면 된다.

 

Collection<V> values = map.values(); // Node 객체의 values 필드 접근 모듈 객체 생성
Iterator<K> iterator = values.iterator(); // values 반복자로 대체하면
while(iterator.hasNext){ ... } // 수정 없이 그대로 반복자 사용

 

이렇듯 인터페이스를 통해, 반복자를 통일시키면 유지보수에 용이해진다. 이를 객체의 부품화라고 한다.

 

put, get, containKey, containValue

 

반복자와 같이, key 필드와 value 필드를 keySet()과 values() 모듈로 분리하여 접근이 필요한 경우와는 달리, 굳이 분리하지 않아도 되는 로직들이 있다.

 

버킷에 단순 추가(put) 한다거나, 해당 key의 value를 return(get) 한다거나, 원하는 key나 value가 존재하는지 검색하는 행위(containKey, containValue )는 따로 접근 모듈이 필요없다.

 

반복자( iterator() )의 경우,

Map<String, Integer> map = new HashMap<String,Integer>(); // HashMap 생성
Set<Map.Entry<K,V> entrySet = map.entrySet(); // 접근 모듈 생성
Iterator<Map.Entry<K,V> iterator = entrySet.iterator(); // 반복자 생성
while(iterator.hasNext()){ ... } // 반복자 실행

 

다른 메소드의 경우

 

Map<String, Integer> map = new HashMap<String,Integer>(); //HashMap 생성
map.put("강민구",56); // map에 추가
Integer value = map.get("강민구"); // key에 해당하는 value를 갖고 오기

 

이와같이, 접근 모듈 생성없이 HashMap 객체의 생성만으로 메소드 사용이 가능하다. 이는 해당 메소드들이 별도로 key, value, Node를 따로 분리하여 접근할 필요가 없기 때문이다.

 

 

---

 

정리

 

1. 버킷 안에는 Map 데이터가 저장된다.

2. key 필드, value 필드, Node 객체를 독립적으로 접근할 수 있는 접근 모듈이 존재한다.

3. 접근 모듈은 반복자를 통해 데이터를 차례대로 가지고 올 수 있다.

4. 반복자는 인터페이스로, 여러 자료구조가 동일한 구조로 반복자를 사용하여 유지보수가 용이해진다.

5. 다른 HashMap의 메소드는 접근 모듈의 생성없이 사용가능하다.