Map
Map 자료구조의 특징은 키(Key)와 값(Value)이다.
키를 통하여 값에 접근할 수 있는 구조이다.
List나 배열은 인덱스로 접근한다. 인덱스는 단순히 순서만 나타낸다. 그러나 Map의 키는 개발자가 의미를 부여할 수 있다.
HashMap
JAVA에서 Map은 인터페이스이며, Map의 구현체 중 하나가 HashMap
데이터를 저장하려면 자료구조가 필요하다. HashMap은 자료구조로 배열(array)을 사용한다. 배열은 '인덱스'를 통해 바로 접근이 가능하다는 장점이 있다. HashMap은 해싱(Hashing)을 통해 Map 데이터가 저장 될 위치의 인덱스를 구한다. 그래서 이름이 HashMap이다.
key(X)를 해싱함수(function)에 넣어 인덱스(Y)를 산출한 후, 해당 인덱스에 Map 데이터를 저장하는 것이 HashMap의 기본 원리이다.
hasing은 index를 구하는 것이 목적이며 지켜야 할 조건이 있다.
1. hasing의 결과는 정수여야 한다.
2. hasing의 결과는 배열의 크기를 넘어서면 안 된다.
JAVA의 컬렉션 프레임워크 HashMap 클래스에서 자세히 확인해보자.
1. hasing의 결과는 정수여야 한다.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
...
}
key를 매개변수로 받은 hash 함수는 key의 해쉬코드와 key의 해쉬코드를 오른쪽으로 16비트 shift한 결과를 ^(xor)한 값을 반환한다. 이는 정수(int)다.
[chatGPT 에게 질문]
만약 string1 이랑 string2 둘다 string1.hashcode(), string2.hashcode() 결과가 같다면 쉬프트 연산이 무슨 소용이야 어차피 쉬프트 >>> 16하고 비트와이즈 XOR 연산해봐야 똑같은 해쉬코드가 리턴되잖아
[chatGPT의 답변]
좋은 질문입니다! 두 문자열 string1과 string2가 같은 해시 코드를 가지는 경우, (h = key.hashCode()) ^ (h >>> 16)의 의미에 대해 설명드리겠습니다.
두 문자열이 같은 해시 코드를 가지더라도 (h = key.hashCode()) ^ (h >>> 16) 연산은 해시 충돌을 줄이기 위한 추가적인 처리를 제공합니다. 이 연산의 주된 목적은 해시 코드를 변형하여 해시 테이블에서 보다 고르게 분포하도록 하는 것입니다. 다만, 두 문자열이 해시 코드 자체가 동일하다면, XOR 연산 후에도 동일한 해시 값을 갖게 됩니다.
해시 테이블에서 해시 충돌을 줄이는 방법 중 하나는 해시 코드의 상위 비트와 하위 비트를 섞어 보다 균일한 분포를 만드는 것입니다. 이를 통해 해시 버킷의 인덱스를 계산할 때 충돌이 줄어들고, 해시 테이블의 성능이 향상됩니다.
2. hasing의 결과는 배열의 크기를 넘어서면 안 된다.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
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);
...
}
hash는 hash(key)의 반환값이다. 인덱스 i 에 (n-1) & hash 의 결과를 넣어주는 것을 볼 수 있다.(tab[i = (n - 1) & hash]) (n-1)&hash 는 hash%n과 같은 결과를 낸다. n은 tab.length로 배열의 크기를 나타낸다. hash에 n을 % 연산하면 그 결과는 n보다 작은 정수가 된다. 그러므로 배열의 크기보다 작은 정수가 인덱스가 된다.
hash%n이 아닌 (n-1)&hash가 사용된 이유는 비트연산이기에 속도면에서 더 좋은 성능을 보이기 때문이 아닐까 추측해본다. 그리고 hash%n과 (n-1)&hash가 같은 결과를 내는 이유는 챗지피티에 물어본 결과 다음과 같다.
위의 그림과 같이 key만 알고 있다면 key를 hash해서 얻은 값을 index로 하여 value를 얻을 수 있다.
key를 통해 인덱스를 산출 후, 데이터에 접근하면 시간복잡도가 O(1)이다. HashMap의 데이터접근성능이 정말 뛰어나다고 할 수 있다.
여기서 이 배열을 버킷(bucket)이라 부른다. 앞으로 HashMap에 사용된 배열을 버킷이라 부르겠다. 버킷 안에 저장된 Map 데이터를 자바에서는 Node객체로 만들어 관리한다.
transient Node<K,V>[] table;
HashMap은 Node 배열을 table이라는 이름으로 관리한다. 이 table이 버킷이다.
버킷 안에는 Node객체들이 있으며, 노드의 필드값으로 hash값, key, value 그리고 next가 존재.
충돌 (Collision)
key만 있으면 해싱함수를 통해 바로 데이터에 접근할 수 있다는 장점이 있지만 이로 인해 생기는 단점이 있다. key는 무궁무진하지만 인덱스는 테이블(버킷) 크기만큼의 한계가 있다는 점이다.
충돌을 관리하기 위해 JAVA에서는 2가지 방법을 사용한다.
1. bucket resize()
버킷 사이즈를 조절하는 것이다. 버킷의 75%가 채워지면 충돌 확률은 크게 늘어난다. 그래서 기본적으로 HashMap은 버킷의 입실률이 75%가 넘으면 버킷의 사이즈를 늘린다.
버킷을 생성시 threshold(임계점)를 지정한다.
threshold에 다다르면 버킷을 사이즈를 2배 늘린다.
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
최초로 threshold가 생성된다.
DEFAULT_LOAD_FACTOR == 0.75
DEFAULT_INITIAL_CAPACITY == 100
이라면 threshold는 75가 된다.
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
<< : 왼쪽으로 1만큼 시프트 → 2배가 된다는 의미
[ex. 0000 0001 (10진수 : 1) → 0000 0010 (10진수 : 2)]
버킷의 데이터가 75개에 다다르면 '버킷사이즈' 와 '임계점'은 2배 증가한다.
2. Linked List + Red Black Tree
당연하게도 버킷의 사이즈를 조절한다고 충돌이 안 일어나는 것은 아니기 때문에 충돌 시 대응이 중요하다.
JAVA에서는 충돌의 횟수에 따라 충돌한 데이터들의 저장방식을 달리 한다.
충돌 초기에는 1. Linked List 방식으로 충돌에 대응한다. 이를 separate chaining 방식이라 부른다.
Node 객체는 next 필드를 가지고 있고, 어떤 Node 객체와 인덱스가 같아 충돌이 일어나면, 이미 자리잡고 있던 Node 객체의 next 필드 안에 새로 들어온 Node 객체의 참조 주소를 저장한다.
ex.
hash(자바) → 13579
hash(스프링) → 13579
자바Node.next → 스프링Node
binCount는 충돌횟수를 체크한다.
충돌횟수가 일정 횟수 (TREEIFY-THRESHOLD -1)를 넘어가면 Linked List 방식은 효율이 떨어지게 된다.
만약 어떤 Node 객체가 n번 충돌되어 n번째 Node의 next에 저장된다면 해당 Node를 탐색하는데 시간복잡도는 O(n)이 된다. 충돌이 많아지면 많아질수록 그 효율이 떨어지는 것이다. 그래서 일정 충돌 수가 넘어가면 데이터 저장방식이 바뀌는데 그것이 Red-Black Tree이다.
Linked List 방식은 Node 객체여야 하지만 충돌이 심해져 Red-Black Tree로 바뀌면 단순 Node 객체로는 Red-Black Tree를 구현 할 수 없다. 그래서 Node 객체를 TreeNode 객체로 바꾸어 주어야 한다.
TreeNode는 Node의 자손이다.
public class HashMap<K,V> {
static class Node<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;
}
}
}
public class LinkedHashMap<K,V> extends HashMap<K,V> {
static class Entry<K,V> extends Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
}
public class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent, left, right;
boolean red;
TreeNode(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
TreeNode 클래스는 LinkedHashMap의 중첩 클래스 Entry를 상속하는데 Entry 클래스는 HashMap의 Node 클래스를 상속한다. 그래서 자식 클래스인 TreeNode의 객체가 생성되면 super()에 의해 부모 클래스인 Node의 객체도 생성된다.
이렇게 트리화가 완료되면, 데이터를 탐색하는데 걸리는 시간 복잡도는 O(log n)이 된다.
그러므로 Linked List의 O(n)보다 효율적인 자료구조가 되는 것이다.
🔥 요약
1. HashMap은 해싱함수를 통해 인덱스를 산출한다.
2. HashMap은 인덱스를 통한 접근으로 시간 복잡도 O(1)의 빠른 성능을 자랑한다.
3. key는 무한하지만 인덱스는 한정되어 있어 충돌은 불가피하다.
4. 충돌을 줄이기 위해 HashMap은 버킷의 사이즈를 조절한다.
5. 충돌이 일어날 시, 충돌 수가 적으면 LinkedList 방식으로 충돌된 객체들을 관리하다가, 임계점을 넘으면 Red-Black Tree 방식으로 객체들을 저장한다.
6. 시간 복잡도는 Linked List가 O(n), Red-Black Tree가 O(log n)이다.
😁 자바 HashMap 클래스와 연관된 자바 연산
^ : 비트wise XOR (배타적 OR)연산
>>> : 비트 이동(shift) 연산
& : 비트 AND 연산자
📚 출처
[자료구조] HashMap 파헤치기 1 (Linked List + Red Black Tree)
나는 HashMap이 잘 이해되지 않았다. 인덱스가 없으니 배열이나 List에 비해 확실히 더 어렵고 직관적으로 이해하기가 힘들었다. 그래서 오늘 HashMap 자료구조가 어떤 원리로 돌아가는지 파헤쳐볼까
lordofkangs.tistory.com
[자료구조] HashMap 파헤치기 2 ( keySet(), values(), iterator() )
지난 포스팅에서는 HashMap의 기본 개념에 대해서 다루었다. HashMap은 key와 value로 구성된 Map 데이터를 해싱함수를 통해 산출된 인덱스 위치의 버킷(배열)안에 저장하는 자료구조이다. 해싱함수(func
lordofkangs.tistory.com
댓글