자바의 HashSet, HashMap 코드와 함께 더 알아보기
https://www.youtube.com/@ez./videos
유튜브 “쉬운 코드”님의 유튜브를 참고하여 작성합니다.
안녕하세요
안드로이드 개발자가 되기 위해 노력하는 서경원입니다.
이해가 안되는 내용이나 제가 잘못 적은 부분이 있다면 꼭 댓글 남겨주세요.
HashSet, HashMap을 알아보기 위해 먼저 Hash에 대해 설명하겠습니다.
Hash 란?
어떤 데이터를 고정된 길이의 문자열로 변환하는 함수를 의미합니다.
해시 함수를 통해 일정한 길이의 해시 코드를 출력하고 이 해시 코드를 통해 데이터의 무결성을 검증하거나 검색을 빠르게 하기 위해 사용됩니다.
그러면 Hash를 사용한 자료구조 형태에 대해 알아보겠습니다.
위처럼 나온 해시 코드를 모듈러 연산을 통해 저장하는 과정을 거칩니다.
size 8의 배열이 있다면 365를 8로 모듈러 연산을 하고 나온 값을 인덱스로 배열에 저장합니다.
365를 8로 모듈러 연산을 하면 5가 나옵니다.
인덱스 5에 해시 값과 함께 데이터를 저장합니다.
해시 충돌
그런데 만약 위처럼 모듈러 연산을 한 값이 같게 나온다면 어떻게 될까요???
이러한 경우를 해시 충돌 이라고 합니다.
해시 충돌의 경우 주로 2가지 방식으로 해결합니다.
해시 충돌 해결 방법
1. Chaining
각 인덱스에 연결 리스트, Linked List와 같은 자료 구조를 사용하여 충돌된 데이터를 저장하는 방식입니다.
위처럼 Linked List 형태로 주로 구현하게 됩니다.
위와 같은 방식을 사용하게 되면 탐색 성능이 저하되는 단점이 존재합니다.
“안드로이드”를 탐색하려고 한다면, “안드로이드” 의 해시 코드를 새로 만듭니다.
365가 나올 것이고 모듈러 연산을 하여 나온 5라는 인덱스에 해당 데이터가 있는 지 확인합니다.
배열의 5번 인덱스에 해시 값이 365인 값이 존재하기 때문에 탐색에 성공하게 됩니다.
“IOS”를 탐색하려고 한다면, 위와 같은 방식을 거칩니다.
- “IOS”의 해시 코드를 새로 만든다.
- 만든 373이라는 해시 코드를 모듈러 연산한다.
- 모듈러 연산으로 나온 5라는 값으로 해당 배열 인덱스를 확인한다.
하지만, 해당 인덱스의 첫 번째 값은 “안드로이드”가 저장되어있고 값이 일치하지 않기 때문에, “안드로이드”의 다음 노드를 살펴봅니다.
만약, 링크드 리스트의 길이가 길어질 경우 탐색 시간에 O(N)의 시간이 걸리기 때문에 탐색이 빠르다는 Hash Table의 장점이 사라지게 됩니다.
2. Open Addressing
충될한 인덱스 그 다음 빈 인덱스에 저장하는 방식입니다.
위 방법에서 “IOS”를 탐색한다고 하면, 해당 인덱스에 값이 있는 지 먼저 확인합니다.
“안드로이드”와 값이 다르기 때문에 다음 인덱스를 확인하여 탐색을 진행합니다.
만약, 저장된 key가 없는 경우이며 모듈러한 해시 코드 값이 5라면, 비어있는 배열이 나올 때까지 탐색을 계속 진행하게됩니다.
즉, open addressing 방식에서 탐색은 빈 슬롯을 발견하거나, 해당 값을 찾은 경우 탐색을 종료합니다.
Open Addressing 방식에서는 삭제하는 경우를 조심해야 합니다.
“안드로이드” 데이터를 삭제한 뒤에 “IOS”를 탐색하게 된다면, 해당 배열에 빈 값이 들어있기 때문에 탐색을 종료할 것입니다.
그렇기 때문에, “IOS” 데이터를 해당 인덱스로 옮기거나, 더미 데이터를 넣어 올바른 탐색을 할 수 있도록 해야합니다.
리사이징
해시 자료구조에서 더 알아야할 것이 리사이징 입니다.
해시 코드를 배열의 크기로 모듈러한 값으로 인덱스를 정한다고 했는데,
배열의 값이 커지면 어떻게 될까요??
커진 배열의 값으로 다시 인덱스에 저장해주어야 합니다.
그래서, 리사이징을 하게 된다면 위와 같이 변하게 됩니다.
그러면, 이제 코드와 함께 HashMap, HashSet을 보겠습니다.
HashSet을 보기 전에, HashMap을 먼저 보겠습니다.
(코드는 자바 8 버전입니다.)
HashMap
- 빠른 검색 및 삽입: HashMap은 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이 해시 코드를 인덱스로 사용하여 데이터를 저장하고 검색합니다. 이로 인해 평균적으로 상수 시간(O(1))에 검색과 삽입이 가능합니다.
- 키-값 쌍 저장: HashMap은 키와 값을 쌍으로 저장합니다. 이를 통해 특정 키를 통해 연결된 값을 효율적으로 검색하거나 수정할 수 있습니다.
- 순서 보장하지 않음: HashMap은 데이터의 순서를 보장하지 않습니다. 데이터의 순서가 중요한 경우에는 LinkedHashMap을 사용하여 순서를 보장할 수 있습니다.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
transient Node<K,V>[] table;
transient int size;
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
}HashMap이 워낙 코드가 길어서 필요한 부분만 가져왔습니다.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
transient Node<K,V>[] table;HashMap의 핵심인 table 배열입니다.
앞서 Hash로 된 자료 구조를 설명했는데, HashMap에서는 이 table 배열에 key, hash값과 value값을 저장합니다.
그리고 Node class를 보면 next 객체가 존재하는 것을 볼 수 있습니다.
앞서 해시 충돌의 해결 방법 두 가지를 소개 드렸는데, 자바에서는 Chaining 방식을 사용합니다.
next 객체를 통해 Linked List 방식을 만들게 됩니다.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
} HashMap에서 value를 가져올 때 사용하는 get을 보겠습니다.
getNode 메서드의 인자로 hash 값과, key를 전달하여 호출합니다.
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null)첫 조건문을 살펴보면, table이 null이고 table의 length가 0인 경우에는 실행되지 않도록 하고,
table의 (n - 1) & hash 인덱스에 해당하는 값이 null 인 경우 실행되지 않도록 하고 있습니다.
(n - 1)과 hash의 & 연산을 해주고 있는 데, table의 length - 1을 비트 연산 해줌으로써 table의 범위를 넘어가는 인덱스를 확인하지 않도록 하기 위함입니다.
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;그 다음 조건문은 해당 배열의 인덱스에 해당하는 hash값과 key값을 비교하여 같다면 해당 Node를 return 합니다.
다음 조건문은 Linked List를 돌며 key를 찾는 로직입니다.
여기서 봐야할게 TreeNode입니다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
} TreeNode는 LinkedHashMap.Entry를 상속받고 있는데 이 LinkedHashMap.Entry는 HashMap의 Node를 상속 받고 있습니다.
그리고 이 TreeNode는 레드 블랙 트리 구조로 이루어져있다는 정도만 파악하고 넘어가겠습니다.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
}put의 내부는 자세히 보진 않고 제가 몰랐던 부분에 대해서 설명드리겠습니다.
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}putValue에서 기존에 저장되어있던 key를 찾게 되면, oldValue를 return합니다.
기존에 저장되어있던 key가 없다면 null을 return합니다.
put을 할 때, putValue를 return하기 때문에 기존에 key가 존재한다면 저장되어 있던 value를 return하고 key가 존재하지 않는다면 null을 return 하는 것을 알 수 있었습니다.
HashMap<String, String> map = new HashMap<>();
System.out.println(map.put("a", "b")); // null
System.out.println(map.put("a", "c")); // "b"
HashSet
- 중복된 요소 제거: HashSet은 중복된 요소를 허용하지 않습니다. 따라서 같은 값을 여러 번 추가하더라도 실제로는 한 번만 저장됩니다.
- 순서 보장하지 않음: HashSet은 요소들의 순서를 보장하지 않습니다. 저장된 순서와 반복된 순서가 항상 일치하지 않을 수 있습니다.
- 빠른 검색 및 삽입: HashSet은 해시 테이블을 사용하여 요소를 저장하므로 검색 및 삽입 연산에 O(1)의 평균 시간 복잡도를 제공합니다. 하지만 해시 충돌이 발생하거나 리사이징이 필요한 경우에는 성능이 늘어날 수 있습니다.
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
} HashSet의 코드입니다.
HashSet을 보기 전에, HashMap을 봤던 이유가 HashSet은 HashMap을 내부적으로 사용하고 있기 때문이었습니다.
HashMap을 사용하여 key에 data를 저장하고 value에는 PRESENT라는 Object의 객체를 더미 데이터로 넣어주고 있습니다.
추가로 설명할 점
java의 HashMap은 배열의 사이즈가 75%정도 차면 크기를 2배로 리사이징 합니다.
hash 자료 구조에서 data class를 사용한다면 equals와 hashCode 함수를 재정의 해주어야 합니다.
java에서 for문을 사용한 iteration 방식 시, list가 더 빠릅니다.
- list는 인덱스로 접근하기 때문에 각 인덱스마다 저장된 데이터를 확인하면 되지만, HashMap의 경우는 버킷(내부 배열)들을 모두 돌아야하기 때문입니다.
쉬운 코드님의 자료 구조에 대한 설명을 재밌게 보고 자바의 코드까지 궁금해져 공부하게 되었습니다.
예전이었다면 내부 코드를 보는 게 쉽지 않았었지만 오픈 소스 스터디 덕분에 코드를 들여다보는 게 익숙해진 것 같아 뿌듯했던 시간이었습니다.
'자바' 카테고리의 다른 글
| Java는 Stack과 Queue를 ArrayDeque로 써야 하는 이유!! (0) | 2023.08.28 |
|---|
