[ Hashmap Java 기본 동작 원리 ]
Java의 HashMap은 매핑을 저장하기 위해 내부 클래스 Node<K,V>를 사용하고
해싱 알고리즘에서 작동하며 get 및 put 작업을 위해 키에 hashCode() 및 equals() 메서드를 사용한다.
HashMap은 단일 연결 리스트를 사용하여 요소를 저장하며 이를 bin 또는 bucket 이라고 한다.
put 메소드를 호출하면 키의 hashCode를 사용하여 매핑을 저장하는 데 사용할 bucket 을 결정하고 bucket 이 식별되면 hashCode 를 사용하여 동일한 hashCode를 가진 키가 이미 있는지 확인한다.
동일한 hashCode를 가진 기존 키가 있는 경우 해당 키에 대해 equals() 메서드가 사용되어 true를 반환하면 값을 덮어쓰고, 그렇지 않으면 이 단일 연결 목록 bucket에 대한 새 매핑이 만들어진다.
동일한 hashCode를 가진 키가 없으면 매핑이 bucket 에 삽입된다.
HashMap get()의 경우 키 hashCode를 사용하여 값을 찾을 bucket 을 결정하고 bucket 이 식별된 후 hashCode 및 equals 메소드를 사용하여 항목을 찾는다.
일치하는 항목이 있으면 값이 반환되고 그렇지 않으면 null이 반환된다.
[ HashMap의 대표적인 특징 ]
1. HashMap static inner class 정적 내부 클래스를 사용한다. Node<K,V>맵에 항목을 저장하기 위한 것이다.
2. HashMap최대 하나의 null 키와 여러 null 값을 허용한다.
3. 클래스 HashMap 는 맵에 항목을 삽입하는 순서를 유지하지는 않는다.
4. HashMap 단일 linked list 에 대한 head reference 를 포함하는 여러 개의 buckets or bins 이 있다.
이는 bucket 수만큼 연결된 목록이 있다는 것을 의미한다.
처음에는 bucket 크기가 16이고 map 의 항목 수가 75% (DEFAULT_LOAD_FACTOR -> 0.75f라서) 를 넘으면 32로 늘어납니다.
(즉, bucket 12개를 삽입하면 bucket 크기가 32가 됩니다.)
5. HashMap은 unsynchronized 이다는 점과, 최대 하나의 null key 와 여러 개의 null value 을 허용한다는 점을 제외하면 Hashtable과 거의 유사하다 .
6. HashMap uses hashCode() and equals() methods on keys for the get and put operations.
So HashMap key objects should provide a good implementation of these methods.
7. 이것이 바로 Wrapper 클래스 Integer와 String클래스가 HashMap의 key로 좋은 이유다.
( Wrapper 클래스 : equals()와 hashCode()를 재정의할 필요 없음 )
Wrapper class라서 immutable 하고 throughout the execution of the program 프로그램 돌아갈동안 Object state가 바뀌지 않기 때문이다.
Java HashMap은 thread 로부터 non-safe하므로 Multi-Thread application 에서 사용하면 안된다!
Multi-Thread application -> ConcurrentHashMap 클래스를 사용해야 한다.
왜 HashMap은 Multi-threaded Environments에 적합하지 않을까 ?
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class ExceptionExample {
public static void main(String[] args) {
Map<String, Long> phoneBook = new HashMap<String, Long>();
phoneBook.put("이병건", 01012345678L);
phoneBook.put("단군", 01045662235L);
phoneBook.put("철면수심", 01036987456L);
Iterator<String> keyIterator = phoneBook.keySet().iterator();
while (keyIterator.hasNext()){
String key = keyIterator.next();
if ("이병건".equals(key)){
phoneBook.put("이세화", 01021215454L);
}
}
}
}
결과
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
at ExceptionExample.main(ExceptionExample.java:16)
HashMap은 내부적으로 bucket 배열을 사용하여 데이터를 저장한다.
그래서 HashMap 에 새로운 항목을 추가하거나 기존 항목을 수정할 때 버킷 배열의 크기를 조정할 수는 있는데 hashMap을 iterate하면서 반복하는 도중에 hashMap 의 구조가 변경되면 예기치 않은 결과가 발생할 수 있다.
위의 코드에서도 while문을 돌면서 이병건 이라는 key 값을 찾으면 phoneBook.put("이세화", 01021215454L) 라는 새로운 항목을 추가하라니까 HashMap 의 내부 구조가 변경됨을 감지하고 ConcurrentModificationException을 throw 한다.
HashMap class의 여러 메서드를 살펴보던 중
forEach() 메서드 내부에서 modCount 값을 확인하여 ConcurrentModificationException을 방지하고 있었다.
forEach() 메서드가 호출될 때 마다 현재의 modCount 값을 저장하고, 모든 Node 를 순회하면서 각 키에 대해 action.accept() 를 호출한다.
그런 다음 모든 Node 를 순회한 후에 modCount 값을 다시 확인하고,
만약 그 동안에 hashMap 이 변경되었다면 아까 keyIterator가 작동했던 것처럼 ConcurrentModificationException 를 throw 하게 되어있다.
이러한 이유로 HashMap 은 동기화되지 않은 다중 스레드 환경에서 안전하지 않다.
HashMap을 다중 스레드 환경에서 안전하게 사용하기 위해서는 ConcurrentHashMap과 같이 동기화된 방식으로 구현되어 있어 여러 thread 가 안전하게 사용할 수 있는 Map을 사용해야 한다.
remove 에서는?
import java.util.Map;
public class ExceptionExample {
public static void main(String[] args) {
Map<String, Long> phoneBook = new HashMap<String, Long>();
phoneBook.put("이병건", 01012345678L);
phoneBook.put("단군", 01045662235L);
phoneBook.put("철면수심", 01036987456L);
Iterator<String> keyIterator = phoneBook.keySet().iterator();
while (keyIterator.hasNext()){
String key = keyIterator.next();
if ("이병건".equals(key)){
//keyIterator. remove (): #1
//phoneBeok.remove（"철면수심"）；#2
}
}
}
}
첫 번째 주석만 keyIterator.remove() 주석을 해제하면 코드가 정상적으로 실행된다.
이는 반복자의
왜냐하면 iterator는map object 의 내부 상태에 대한 references 를 가지고 있는 별도의 객체 (separate object) 이기 때문에 remove() 메서드를 사용하여 맵에서 요소를 안전하게 제거하여 ConcurrentModificationException이 발생하지 않는다.
이처럼 Iterator 를 통해 요소를 제거할때 iterator 는 map의 내부를 참조하고 있어서 바로 업데이트가 되기 때문에 모든 요소가 일관성을 유지할 수 있게 해줘서 Exception 이 발생하지 않는다.
두 번째 주석인 phoneBook.remove("철면수심") 을 주석 해제하면 (#1은 주석 처리된 채로 남겨두고),
이후의 keyIterator.next() 호출은 ConcurrentModificationException 을 발생시킬 것이다.
이는 HashMap 을 직접 수정하면서 동시에 iterator가 순회하고 있기 때문에 iterator가 HashMap의 상태 변화를 감지하지 못하고 예외를 throw 한다.
[ Java의 Object 클래스에 있는 hashCode() 메서드 ]
hashCode() 메서드는 객체의 hashCode 값 을 반환한다.
이 메서드는 주로 java.util.HashMap과 같은 hash table 에서 사용된다고 한다.
hashCode() 메서드의 일반적인 규약
- 동일한 object 에 대해 동일한 Java 애플리케이션 실행 중에 두 번 이상 호출될 때, hashCode() 메서드는 변경되지 않은 경우에는 항상 동일한 정수를 반환해야 한다.
- equals 메서드에 사용된 정보가 수정되지 않는 한, hashCode() 메서드는 같은 object 에 대해 일관된 정수를 반환해야 한다.
- 두 객체가 equals() 메서드에 따라 동일하면, 각 object 의 hashCode() 메서드를 호출해도 동일한 정수 결과를 반환해야 한다.
class Person {
public String name;
public Person(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person p = (Person) o;
return Objects.equals(name, p.name);
}
@Override
public int hashCode() {
return Objects.hash(name); // name 필드의 해시코드를 반환한다.
}
}
public class ClassTest {
public static void main(String[] args) throws Exception {
Person p1 = new Person("홍길동");
Person p2 = new Person("홍길동");
// 두 객체의 해시 코드
System.out.println(p1.hashCode()); // 54150093
System.out.println(p2.hashCode()); // 54150093
// 해시코드가 달라도, equals를 재정의 했기 때문에 동등함
System.out.println(p1.equals(p2)); // true
// SET를 생성하고 두 객체 데이터를 추가한다.
Set<Person> people = new HashSet<>();
people.add(p1);
people.add(p2);
// 그리고 SET의 길이를 출력한다.
System.out.println(people.size()); // 1
}
}
hashCode 메서드를 재정의함에 따라, 두 객체의 hashCode 는 같은 값이 나오는 걸 볼수 있고,
Set 자료형에도 중복된 데이터 적재로 판단되어 한번만 추가됨을 볼수 있다.
[ Hash Bucket 동적 확장 ]
Hash Bucket 의 갯수가 적다면 메모리 사용을 아낄 수 있지만 hash collision 로 인해 성능상 손실이 발생한다.
그래서 HashMap은 Key-Value 쌍 데이터 갯수 가 일정 갯수 이상이 되면, Hash Bucket 의 갯수를 2배로 늘린다.
이렇게 Hash Bucket 갯수를 늘리면
값도 작아져, hash collision 으로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
Hash Bucket 갯수의 기본값은 16이고, 데이터의 갯수가 임계점에 이를 때마다 해시 버킷 갯수의 크기를 2배씩 증가시킨다.
Bucket 의 최대 개수는 230개다.
그런데 이렇게 bucket 개수가 2배로 증가할 때마다, 모든 Key-Value 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다.
HashMap 생성자의 인자로 초기 Hash Bucket 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.
1. load factor의 default = 0.75 즉 3/4이고
2. default initial capacity = 16 으로
리사이징과 관련된 두가지 중요한 개념이라고 합니다!! (Java 17 기준입니다)
1. Initial Capacity (초기 용량)
- 기본값: HashMap의 초기 용량은 16입니다. 즉, HashMap을 생성할 때 특별히 초기 용량을 지정하지 않으면 16개의 hash bucket 이 생성됩니다.
- 의의: 초기 용량은 HashMap이 데이터를 저장할 수 있는 기본 bucket 수를 의미합니다. 이 값을 적절히 설정하면 HashMap의 성능을 향상시킬 수 있습니다.
2. Load Factor (부하 계수)
- 기본값: HashMap의 기본 load factor는 0.75입니다. 이는 HashMap의 버킷이 75% 가득 차면 리사이징을 시작한다는 의미입니다.
- 의의: Load factor는 HashMap의 성능과 메모리 사용 간의 균형을 결정합니다. 기본값인 0.75는 공간과 성능 간의 좋은 균형을 제공합니다. 즉, 버킷이 75% 가득 차면 추가적인 키-값 쌍을 수용하기 위해 버킷 수를 두 배로 늘려야 합니다.
3. 리사이징 과정 (Re-Hashing)
- 초기 용량(16)과 load factor(0.75)를 곱하면 리사이징이 발생하는 임계점(즉, 최대 저장 가능 개수)을 알 수 있습니다.
-
Threshold value = Bucket size * Load factor - 예를 들어, bucket size가 16 이고 load factor is 0.75 이면 threshold value 는 12가 되는 원리입니다. 즉, 12개의 key-value 쌍이 저장되면 HashMap은 리사이징을 시작합니다.
-
- 리사이징이 발생하면 HashMap은 새로운 버킷을 생성하고, 기존의 모든 키-값 쌍을 새로운 해시 버킷으로 재배치합니다.
DEFAULT_INITIAL_CAPACITY
기본 초기 용량으로, HashMap 의 초기 크기를 나타냅니다.
이 값은 16으로 설정되어 있으며, 즉 HashMap 이 처음 생성될 때 기본적으로 16개의 bucket 을 가지게 됩니다.
( 1 << 4는 비트 시프트 연산자를 사용하여 1을 왼쪽으로 4비트(shift) 이동시키는 것을 나타냅니다.
이렇게 하면 2의 4승(2^4) -> 16 )
MAXIMUM_CAPACITY
최대 용량으로, HashMap 의 최대 크기를 나타냅니다.
이 값은 2의 30승, 즉 1073741824 로 설정되어 있으며, HashMap 의 크기가 이 값을 초과할 수 없습니다.
DEFAULT_LOAD_FACTOR
기본 load factor 로, HashMap 이 언제 축소 및 확장되어야 하는지 결정하는 요인 중 하나입니다.
이 값은 0.75로 설정되어 있으며, 즉 HashMap 의 용량이 요소 수의 75%를 초과할 경우 HashMap 이 확장됩니다.
TREEIFY_THRESHOLD
Treeify 임계값으로, HashMap 의 bucket 이 LinkedList -> Tree 로 변환되는 임계값을 나타냅니다.
한 bucket 에 요소가 일정 수 이상 쌓이면 LinkedList 대신에 Tree 로 변환됩니다.
private static final int THRESHOLD = 8; // LinkedList에서 Tree로 전환 기준이 값은 8로 설정되어 있습니다.
UNTREEIFY_THRESHOLD
Tree 를 해제하는 임계값으로, HashMap 의 bucket 이 Tree -> LinkedList 로 변환되는 임계값을 나타냅니다.
한 bucket 에 요소가 일정 수 이하로 줄어들면 Tree 가 LinkedList 로 다시 변환됩니다.
private static final int THRESHOLD_DOWN = 6; // Tree에서 LinkedList로 전환 기준이 값은 6으로 설정되어 있습니다.
public void put(K key, V value) {
int index = getIndex(key);
Node<K, V> node = table[index];
if (node == null) {
table[index] = new Node<>(key, value);
size++;
} else {
// 기존에 노드가 있을 경우
if (node.tree != null) {
// TreeMap 사용
node.tree.put(key, value);
} else {
// LinkedList 사용
if (checkForTree(node)) {
// 요소가 많아지면 Tree로 전환
node.tree = new TreeMap<>();
while (node != null) {
node.tree.put(node.key, node.value);
node = node.next;
}
table[index] = new Node<>(key, value);
} else {
// LinkedList에 추가
while (node.next != null) {
node = node.next;
}
node.next = new Node<>(key, value);
}
}
}
}
LinkedList 를 사용할 것인가 Tree 를 사용할 것인가에 대한 기준은 하나의 Hash Bucket 에 할당된 Key-Value 쌍의 개수이다.
Java 17 HashMap에서는 상수 형태로 기준을 정하고 있다.
즉 하나의 Hash Bucket 에 8개의 Key-Value 쌍이 모이면 LinkedList 를 Tree 로 변경한다.
만약 해당 bucket 에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 LinkedList 로 변경한다.
Tree 는 LinkedList 보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 Tree 와 LinkedList 의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다.
8과 6으로 2 이상의 차이를 둔 것은,
만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 Tree 와 LinkedList 를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.
<reference : https://d2.naver.com/helloworld/831311>
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 기존 해시 맵의 배열을 oldTab에 저장
Node<K,V>[] oldTab = table;
// oldTab의 길이를 oldCap에 저장합니다. 만약 oldTab이 null인 경우 0으로 초기화
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// oldCap이 최대 용량(MAXIMUM_CAPACITY) 이상인 경우, 새로운 CAPACITY를 Integer.MAX_VALUE로 설정하고 oldTab을 반환
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 새로운 용량이 최대 용량보다 작고, oldCap이 기본 초기 용량(DEFAULT_INITIAL_CAPACITY)보다 큰 경우,
// 용량을 두 배로 확장하고 CAPACITY도 두 배로 증가시킴
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 새로운 용량과 로드 팩터를 곱한 값을 CAPACITY로 설정
// 단, 최대 용량보다 작고, 이 값이 최대 용량보다 작은 경우에만 해당 값을 사용합니다.
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 새로운 해시 맵 배열을 생성
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 기존 해시 맵을 새로운 해시 맵으로 업데이트
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
oldThr << 1: newThr = oldThr << 1;// threshold를 두 배로 증가
oldThr이 8 (즉, 이진수로 00001000)일 때, 8 << 1의 결과는 16이 된다.
이진수로 보면, 00001000 → 00010000 (왼쪽으로 한 비트 이동)
h >>> 16 을 사용하여 h의 상위 비트를 하위 비트로 XOR(배타적 논리합)을 진행한다.
이렇게 함으로써 hash code 의 상위 비트가 하위 비트와 결합되어 확산이 된다.
1. 키의 해시 코드가 0x12345678(16진수)라고 가정합니다.
2. 32비트 이진수로 표현하면:
0x12345678 = 00010010 00110100 01010110 01111000 (2진수)
이때, 앞쪽 16비트는 상위 비트, 뒤쪽 16비트는 하위 비트입니다.
3. h >>> 16 연산을 하면 상위 16비트가 오른쪽으로 16비트 이동합니다. 즉:
h >>> 16 = 00000000 00000000 00010010 00110100 (상위 16비트를 하위로 이동)
4. 원래의 h 값과 h >>> 16 값을 XOR(배타적 논리합) 연산으로 결합합니다:
int hash = h ^ (h >>> 16);
여기서 ^는 XOR 연산자입니다. XOR는 두 비트가 같으면 0, 다르면 1을 반환합니다.
5. 두 값의 XOR 결과:
00010010 00110100 01010110 01111000 (원래 h)
^ 00000000 00000000 00010010 00110100 (h >>> 16)
--------------------------------------
00010010 00110100 01000100 01001100 (XOR 결과)
key.hashCode() 로부터 얻은 기본 hash code 를 조작하여 더 넓은 범위에 분포되도록 만든다.
이를 통해 hash collision 을 줄이고, 해시 테이블의 성능을 향상시키는 데 도움이 되어 보조 해시 함수로 쓰이는 것 같다.
참고 ) Bucket Entries
- 버킷의 정의:
- 버킷은 해시 함수의 결과로 나온 빠른 접근 위치(예: 배열 인덱스)를 의미합니다.
- 해싱의 아이디어는 복잡한 입력 값을 간단한 값으로 변환하여 데이터를 빠르게 저장하거나 추출하는 것입니다.
- 예제 해시 함수:
- 아래 예제에서는 사람의 이름을 거리 주소로 매핑하는 해시 함수를 설명합니다.
- 이름의 첫 글자(이니셜)를 숫자 값으로 변환합니다. A부터 Z까지 각각 0부터 25까지의 값을 가지도록 하여 두 이니셜(첫 번째 이름과 성)을 사용합니다.
- 첫 번째 이니셜을 26으로 곱하고 두 번째 이니셜을 더함으로써 0에서 675 사이의 값을 얻습니다. 이는 26 × 26의 고유한 버킷 ID를 생성합니다.
- 완벽한 해시와 비완벽한 해시:
- 완벽한 해시: 각 입력 값이 고유한 버킷 ID로 매핑되어 충돌이 발생하지 않을 경우, 간단한 배열을 사용할 수 있습니다.
- 이 경우, 676개의 거리 주소를 유지하는 배열을 만들고 버킷 ID를 사용하여 원하는 주소를 찾을 수 있습니다.
"George Washington"은 "GW" 해시를 통해 GwBucket[George의 주소]로 찾을 수 있습니다.
"Abraham Lincoln"은 "AL" 해시를 통해 AlBucket[Abe의 주소]로 찾을 수 있습니다.
-
- 비완벽한 해시: 만약 해시 함수의 결과로 같은 버킷 ID를 가진 여러 입력 값이 존재한다면(예: "John Smith"와 "Jane Seymour"가 같은 버킷 ID를 가진다면), 단순한 배열 대신 더 복잡한 데이터 구조가 필요합니다.
- 이 경우, 각 버킷 내에서 추가적인 검색이 필요합니다. 예를 들어, 링크드 리스트를 사용하거나 또 다른 해시 구조를 사용할 수 있습니다.
- "John Smith"와 "Jane Seymour"는 같은 hash(JS)로 매핑되며, JsBucket 안에 각각의 주소를 저장합니다.
- JsBucket은 각 사람의 이름과 주소를 연결하는 구조로 되어 있어, 첫 번째 해시 조회 후에 버킷 내에서 특정 정보를 찾기 위한 추가 검색이 필요합니다.
- 이 경우, 각 버킷 내에서 추가적인 검색이 필요합니다. 예를 들어, 링크드 리스트를 사용하거나 또 다른 해시 구조를 사용할 수 있습니다.
- 비완벽한 해시: 만약 해시 함수의 결과로 같은 버킷 ID를 가진 여러 입력 값이 존재한다면(예: "John Smith"와 "Jane Seymour"가 같은 버킷 ID를 가진다면), 단순한 배열 대신 더 복잡한 데이터 구조가 필요합니다.
요약
- 해시 함수는 복잡한 입력 값을 간단한 정수로 변환하여 빠르게 데이터를 찾거나 저장하는데 도움을 줍니다.
- 버킷은 해시 함수의 결과로 생성된 인덱스이며, 고유한 해시 값을 가지면 간단한 배열로 처리할 수 있지만, 충돌이 발생할 경우 더 복잡한 구조가 필요합니다.
- 완벽한 해시 함수는 충돌이 없지만, 비완벽한 해시 함수는 충돌을 해결하기 위한 추가적인 검색이 필요합니다.
Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다.
이유로는 두 가지가 있는데,
첫 번째는 Java 8에서는 해시 충돌이 많이 발생하면 LinkedList 대신 Tree 를 사용하므로 hash collision 시 발생할 수 있는 성능 문제가 완화되었기 때문이다.
두 번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다.
두 번째 이유가 좀 더 결정적인 원인이 되어 Java 8에서는 보조 해시 함수의 구현을 바꾸었다.
<출처 : https://d2.naver.com/helloworld/831311 , https://stackoverflow.com/questions/9073903/what-does-bucket-entries-mean-in-the-context-of-a-hashtable >
'java' 카테고리의 다른 글
| Java Arrays.sort(), Collection.sort() 정렬 알고리즘 (1) | 2024.10.19 |
|---|---|
| Java 시간 유형에 대한 고민 (1) | 2024.04.19 |
| method class instance object (0) | 2022.09.23 |
| 생성자 내부클래스 (1) | 2022.09.23 |
| Linked List vs Array List (0) | 2022.09.23 |
