자바로 게시판 만드는 코드를 구현해보다가 문득 ArrayList보다 HashMap으로 구현하는게 유리하지 않을까?라는 의구심이 들었다.

ArrayList를 활용해 만든 객체로 모든 것을 관리하기엔 탐색 과정에서 다소 성능이 떨어질 것이라는 생각과, 추가적인 기능들을 구현할 때 파라미터 수를 지속적으로 변경해주어야 한다는 불편함이 발생할 것이라는 데에서 의구심이 시작되었다.

HashMap

HashMap
Map<Key, Value> map = new HashMap<>();

• HashMap = Hash + Map
• Map
  key, Value 쌍으로 이루어진 자료형
  순서를 보장하지 않는다.
  키는 중복이 허용되지 않는다(고유해야 한다.)
• Hash
  해시 함수를 사용하여 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값

정리하면,

• HashMap은 데이터를 저장할 때 키(Key)와 값(Value)이 하나의 짝을 이루어 저장된다.
• HashMap은 자바의 Map 인터페이스의 구현체중 하나이다.

HashMap 메서드

1) 데이터 추가

• V put(K key, V value) : key와 value를 저장합니다. 
• void putAll(Map<? extends K, ? extends V> m) : Map m의 데이터를 전부 저장합니다.
• V putIfAbsent(K key, V value) : 기존 데이터에 key가 없으면  key와 value를 저장합니다. 

2) 데이터 삭제

• void clear( ) : 모든 데이터를 삭제합니다. 
• V remove(Object key) : key와 일치하는 기존 데이터( key와 value)를 삭제합니다. 
• boolean remove(Object key, Object value) : key와 value가 동시에 일치하는 데이터를 삭제합니다. 

3) 데이터 수정

• V replace(K key, V value) : key와 일치하는 기존 데이터의 value를 변경합니다. 
• V replace(K key, V oldValue, V newValue) : key와 oldValue가 동시에 일치하는 데이터의 value를 newValue로 변경합니다. 

4) 데이터 확인

• boolean containsKey(Object key) : key와 일치하는 데이터가 있는지 여부를 반환합니다. (있으면 true)
• boolean containsValue(Object value) : value가 일치하는 데이터가 있는지 여부를 반환합니다. (있으면 true)
• boolean isEmpty( ) : 데이터가 빈 상태인지 여부를 반환합니다. (빈 상태면 true)
• int size( ) : key-value 맵핑 데이터의 개수를 반환합니다. 

5) 데이터 반환

• V get(Object key) : key와 맵핑된 value값을 반환합니다. 
• V getOrDefault(Object key, V defaultValue) : key와 맵핑된 value값을 반환하고 없으면 defaultValue값을 반환합니다.
• Set<Map.Entry<K, V>> entrySet( ) : 모든 key-value 맵핑 데이터를 가진 Set 데이터를 반환합니다. 
• Set keySet( ) : 모든 key 값을 가진 Set 데이터를 반환합니다. 
• Collection values( ) : 모든 value 값을 가진 Collection 데이터를 반환합니다. 

출처 : https://kadosholy.tistory.com/120

HashMap 장단점

장점

• 탐색, 검색, 추가, 삭제 연산을 평균적으로 O(1)의 상수 시간에 처리할 수 있어서 빠른 속도를 보여준다.(특히 key-value 쌍으로 데이터를 저장하므로 탐색속도가 빠르다)
• HashMap 내부 구조는 배열과 연결 리스트로 구성되어 있어서 메모리 공간을 효율적으로 사용한다.

단점

• 너무 많은 저장이 일어날 경우 오히려 속도가 느려진다
• HashMap 내부 구조는 연결 리스트에 대한 포인터를 유지하기 때문에, 메모리 사용량이 크게 증가한다.(공간복잡도가 증가한다.)
• 해시함수 충돌이 발생할 경우 성능이 저하된다.(이를 해결하기 위해 체이닝이나 오픈 어드레싱 등의 기법을 사용한다.)

해시함수와 해시충돌

해시함수

해시함수는 key를 넣으면, 미리 약속해둔 길이로 변환시켜주는 기능을 한다.

• java에서 HashMap의 구조
  array[hf(key) % M] = value
• 여기서 M은 배열의 크기를 의미

해시함수의 특징

1. 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.
2. 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다(눈사태 효과)
3. 출력된 결괏값을 통해 입력값을 유추할 수 없다.

해시충돌

해시함수의 구조로 인하여 다른 key를 입력하더라도, % M 연산에 의해 같은 결괏값이 나오는 경우가 있는데, 이를 해시충돌이라 한다.

해시충돌 완화방법

• 개방 주소법(Open Addressing)
  해시 테이블 크기는 고정하면서 저장할 위치를 찾는다.
• 분리 연결법(Separate Chaining)
  해시 테이블의 크기를 유연하게 만든다.

결론

ArrayList와 HashMap중 어떤 것을 활용할지 고민될 때,
우선은 ArrayList로 구현해놓고,
Refactoring 과정에서 HashMap으로 수정하는 것이 유리하다는 생각이 들때, 수정하는 방향이 고생을 덜할 수 있을 것이라 생각한다.