나의개발일지
[java] HashMap 본문
📌 HashMap이란?
오늘도 역시 HashMap에 대한 자바 공식문서를 보자
해석 및 요약을 해보자면
HashMap은 키-값 쌍을 저장하기 위해 해시 테이블을 사용하는 자료구조입니다. HashMap은 Map 인터페이스의 모든 선택적 메서드를 제공하며, null 값을 허용합니다(null 키도 허용). HashMap은 동기화되지 않으며, Hashtable과 달리 null을 허용하는 차이점이 있습니다.
순서를 보장하지 않는 Map인것 같다. 이름 부터 HashMap이니 당연하게도 hash가 사용된다 hash에 대한 설명은 이전 포스트를 확인 바란다.
2025.03.05 - [기본기를 다지자/자료구조] - [java] Hash
✏️ 생성자
HashMap()
기본 생성자로, 초기용량 16과 기본 로드 팩터 0.75를 사용하여 비어있는 HashMap을 생성
HashMap(int initalCapacity)
지정된 초기 용량을 사용하여 비어있는 HashMap을 생성합니다. 로드팩터는 기본값인 0.75가 사용된다.
HashMap(int initialCapacity, float loadFactor)
지정된 초기 요량과 로드 펙터를 사용하여 비어있는 HashMap을 생성한다. 초기 용량과 로드 팩터를 모두 사용자가 지정할 수 있다.
HashMap(Map<? extends K, ? extends V> m)
주어진 Map의 모든 키-값 쌍을 복사하여 새로운 HashMap을 생성합니다. 이 생성자는 다른 Map 객체를 기반으로 새로운 HashMap을 생성할 때 사용된다.
📌 HashMap의 로드펙터(Load Factor)
로드팩터란 말을 처음 들어봤다.. 여러 조사를 해보니 해시 기반 자료 구조에서 성능을 최적화하고 저장 공간을 효율적으로 관리하기 위한 개념이라고 한다.
로드 팩터란?
해시맵이 몇 퍼센트 채워졌을 때 내부 배열의 크기를 확장할지를 정의하는 값이다. 예를 들어, 로드 팩터가 0.75라면, 내부 배열이 75% 채워졌을 때 크기가 두 배로 증가한다.
음.. 그러면 ArrayList도 크기가 정해지고, 이를 초과하면 크기가 늘어나는데 로드팩터라는 개념이 없다.
왜일까? GPT에게 물어보았다.
로드팩터는 HashMap에서 해시 충돌 가능성을 줄이고 성능을 최적화 하기 위한 요소이다.
해시 충돌과 로드 팩터의 역할
- 해시 충돌이란: 해시맵에서 각 키는 해시 함수를 통해 해시 값으로 변환되어 배열의 인덱스에 저장됩니다. 하지만 서로 다른 키들이 같은 해시 값을 가질 수도 있는데, 이 경우 해시 충돌이 발생합니다. 충돌이 발생하면 해시맵은 같은 인덱스에 여러 개의 값을 저장해야 하며, 이는 성능 저하로 이어질 수 있습니다. 이 경우, 자바에서는 같은 인덱스에 값을 연결 리스트나 트리 구조로 저장하여 문제를 해결합니다.
- 로드 팩터의 역할: 로드 팩터는 해시맵이 얼마나 차면 리사이징(확장)할지를 결정합니다. 로드 팩터가 높으면 더 많은 요소를 배열에 저장할 수 있어 메모리 사용을 절약할 수 있지만, 충돌 가능성이 높아져 조회 성능이 나빠질 수 있습니다. 반대로, 로드 팩터가 낮으면 충돌 가능성이 줄어들어 성능은 좋아지지만, 더 자주 리사이징이 발생해 메모리를 더 많이 사용할 수 있습니다.
- 충돌 가능성 감소: 해시맵이 로드 팩터에 도달하면 배열을 더 큰 크기로 확장하면서 요소들을 재해시(rehashing) 합니다. 배열이 커지면 해시 충돌이 덜 발생하게 되고, 해시맵의 O(1) 조회 성능을 유지할 수 있습니다. 로드 팩터를 조정하면 충돌이 적게 발생하는 적절한 시점에 리사이징을 할 수 있게 되어 해시맵의 성능이 최적화됩니다.
로드 팩터가 성능에 미치는 영향
- 로드 팩터가 낮을 경우 (예: 0.5):
- 해시맵이 더 자주 리사이징되어 빈 공간이 많아지고 충돌 가능성이 줄어듭니다.
- 조회 속도가 빨라질 수 있지만, 자주 리사이징되면서 메모리 사용량이 증가하고 재배치 비용이 커집니다.
- 로드 팩터가 높을 경우 (예: 0.9):
- 해시맵이 더 많은 데이터를 담을 수 있고, 리사이징이 덜 발생해 메모리 효율성이 좋아집니다.
- 하지만 충돌 가능성이 증가해 성능이 저하될 수 있으며, 충돌이 많이 발생하면 조회 시간 복잡도가 O(1)에서 O(n)으로 악화될 수 있습니다.
📌 Java에서의 해시 충돌 처리 ( HashMap)
일단 해시 충돌에대해 알아보자
해시 충돌이란 해시맵에서 각 키는 해시 함수를 통해 해시 값으로 변환되어 배열의 인덱스에 저장됩니다. 하지만 서로 다른 키들이 같은 해시 값을 가질 수도 있는데, 이 경우 해시 충돌이 발생합니다. 충돌이 발생하면 해시맵은 같은 인덱스에 여러 개의 값을 저장해야 하며, 이는 성능 저하로 이어질 수 있습니다. 이 경우, 자바에서는 같은 인덱스에 값을 연결 리스트나 트리 구조로 저장하여 문제를 해결합니다.
결론적으로 같은 해시값이 오면 이를 연결 리스트나, 트리 구조로 저장하여 문제를 해결 하는 것 같다.
코드에서 확인해 보자
먼저 삽입 연산인 put메서드를 구현한 것을 확인해 보자
putVal 메서드를 호출하여 반환값을 반환한다. 그러면 putVal메서드를 가보자 ( hash 메서드는 이전 포스트 참고 )
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
해시 충돌 부분을 살펴보자
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
충돌이 발생하였을때, 이미 해당 인덱스에 노드가 있으면 그 노드와 해시값을 비교한다. 해시 값과, 키가 동일하다고 판단되면, 해당 노드를 e로 설정하여 값을 덮어쓴다.
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
만약 현재 버킷이 트리 구조로 되어있으면 ,트리의 삽입 로직을 사용한다. 이는 해시 충돌이 많이 발생하여 연결 리스트가 트리로 변환된 경우이다.
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
버킷이 트리가 아닌 연결 리스트인 경우, 연결 리스트를 순회하며 키와 해시 값을 비교한다. 해당 리스트에 동일한 키가 없으면 연결 리스트 끝에 새로운 노드를 추가한다.
연결 리스트의 길이가 임계값( TREEIFY_THRESHOLD )을 넘으면 리스트를 트리로 변환한다 ( treeifyBin() ) 호출
임계값( TREEIFY_THRESHOLD )은 8 이다.
코드를 살펴보니 해시 충돌이 발생하면 처음에는 연결 리스트로 공통된 해시값을 저장하다가, 임계값이 넘어가면 트리로 저장한다는 것을 알아냈다. -> 그러면 처음부터 트리로 저장하면 되는 게 아닌가?
이유를 조사해 보았다.
1. 대부분의 경우 해시 충돌이 거의 발생하지 않음
2. 트리 구조는 비용이 크고 복잡함
3. 연결 리스트의 단순성과 초기 효율성
연결 리스트에서 트리 변환 이유
1. 성능 최적화 -> 노드가 많아지면 연결리스트의 탐색은 O(N) 트리는 O(log N)
📌 HashMap 메서드
HashMap에는 여러개의 메서드가 있다. 하나씩 정리 해보자
| 메서드 | 반환값 | 설명 |
| clear() | void | 맵의 모든 엔트리(키-값 쌍)를 제거한다. |
| clone() | Object | 이 HashMap 인스턴스의 앝은 복사본을 반환한다. 키와 값은 복사되지 않고 동일한 참조를 가진다. |
| compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFuction) | V | 주어진 키와 현재 값에 대한 매핑을 계산하고, 그 결과로 매핑을 업데이트하거나 추가한다. |
| computeIfAbsent(K key, Function<? super K, ? extends V> mappingFuction) | V | 주어진 키가 값에 매핑되어 있지 않거나 null 이면, 주어진 함수를 사용하여 값을 계산하고 추가한다. |
| computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) | V | 주어진 키가 값에 매핑되어 있고, 그 값이 null이 아닐 때, 새로운 매핑을 계산한다 |
| containsKey(Object key) | boolean | 맵에 주어진 키가 있는지 확인한다 |
| containValue(Object value) | boolean | 맵에 주어진 값이 하나 이상의 키에 매핑되어있는지 확인한다. |
| entrySet() | Set<Map, Entry<K,V>> | 맵에 모든 키-값 쌍을 Set으로 반환한다 |
| forEach(BiConsumer<? sumper K, ? super V> action) | void | 맵의 각 엔트리에 대해 주어진 작업을 수행한다 |
| get(Object key) | V | 주어진 키에 대한 값을 반환하고, 해당 키에 대한 매핑이 없으면 null을 반환한다 |
| getOrDefault(Object key, V defaultValue) | V | 주어진 키에 대한 값이 있으면 그 값을 반환하고, 없으면 기본값을 반환한다. |
| isEmpty() | boolean | 맵이 비어 있는지 확인한다. |
| keySet() | Set<K> | 맵에 있는 모든 키를 Set으로 반환한다. |
| marge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remapptingFuction) | V | 주어진 키가 값에 매핑되어 있지 않거나 null이면 주어진 값으로 매핑한다. 값이 있으면 주어진 함수를 사용해 값을 병합한다. |
| put(K key, V value) | V | 주어진 키에 대해 주어진 값을 맵에 추가하고, 기존 값을 반환한다. |
| putAll(Map<? extends K, extends V> m) | void | 주어진 맵의 모든 엔트리를 이 맵에 복사한다. |
| putIfAbsent(K key, V value) | V | 주어진 키가 값에 매핑되어 있지 않으면, 주어진 값을 추가하고 null을 반환한다. 그렇지 않으면 기존 값을 반환한다. |
| remove(Object key) | V | 주어진 키에 대한 매핑을 제거한다. |
| remove(Object key, Object value) | boolean | 주어진 키가 지ㅓㅇ된 값에 매핑되어 있으면, 그 엔트리를 제거한다. |
| replace(K key, V value) | V | 주어진 키가 어떤 값에 매핑되어 있을 때만, 그 값을 새로운 값으로 교체한다. |
| replace(K key, V oldValue, V newValue) | boolean | 주어진 키가 주어진 oldValue에 매핑되어 있을 때만, 그 값을 새로운 값으로 교체한다. |
| replaceAll(BiFuction<? super K, ? super V, ? extends V> fuction) | void | 각 엔트리의 값을 주어진 함수로 계산한 결과로 대체한다. |
| size() | int | 맵에 있는 키-값 쌍의 수를 반환한다. |
| values() | Collection<V> | 맵에 있는 모든 값을 Collection 형태로 반환한다. |
많은 메서드가 있다.. 나머지는 다 알겠는데 BiFunction 이라는 것은 뭐지? 궁금하다.
✏️ BiFunction
자바 Doc에는 이렇게 나와있다. 해석 해 보자면
BiFunction 인터페이스는 두 개의 입력값을 받아 하나의 결과를 반환하는 함수형 인터페이스입니다. 이는 Java 8에서 도입된 함수형 프로그래밍을 지원하는 주요 인터페이스 중 하나로, apply 메서드를 통해 두 개의 인자를 처리하는 함수 로직을 정의할 수 있습니다.
이 인터페이스 에서는 재정의 할 수 있는 메서드는 2개가 있다.
| 메서드 | 설명 |
| andThen | BiFunction을 연속적으로 연결하는데 사용 |
| apply | 두개의 인자 (t, u)를 받아서 그 결과를 반환하는 함수 |
Compute 메서드를 예시로 사용해보겠다.
public static void main(String[] args) {
// HashMap 생성
HashMap<String, Integer> map = new HashMap<>();
// 초기 데이터 삽입
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
// BiFunction을 사용하여 값을 계산하고 갱신 (키가 있는 경우)
map.compute("A", new BiFunction<String, Integer, Integer>() {
@Override
public Integer apply(String key, Integer value) {
// 기존 값에 10을 더하는 로직
return (value == null) ? 10 : value + 10;
}
});
// Lambda 표현식을 사용하여 "B"의 값 계산 및 갱신
map.compute("B", (key, value) -> (value == null) ? 10 : value + 20);
// 값이 없는 키 "D"에 대해 새로운 값을 계산하여 추가
map.compute("D", (key, value) -> (value == null) ? 100 : value + 10);
// 결과 출력
System.out.println(map); // 출력: {A=11, B=22, C=3, D=100}
}
결과는 이렇게 나온다
BiFunction이라 신기한 기능이다 나중에 한번 포스팅으로 다뤄봐야겠다.
🤔 느낀점
요번 해시맵을 공부하면서 의도치않게 해시도 같이 공부하였는데 자바에 대해 자세히 들여다 보니 생각보다 고민하여 만든 언어라는게 다시한번 깨닫는 계기가 된거 같다.
'기본기를 다지자 > 자료구조' 카테고리의 다른 글
| 레드-블랙 트리 (개념 + 삽입) (0) | 2025.04.01 |
|---|---|
| [java] TreeMap (0) | 2025.03.27 |
| [java] Hash (0) | 2025.03.05 |
| [java] Map (1) | 2025.03.03 |
| [java] Stack (ArrayDeque) (0) | 2025.02.20 |
