HashMap을 비밀의 방(버킷)이 있는 성으로 상상해 봅시다. 각 방 앞에는 마법의 문이 있습니다(해시 함수). 이 마법 메커니즘은 어떻게 작동하며 두 마법 개체가 같은 장소에서 충돌하면 어떻게 되나요? HashMap의 비밀 세계로 뛰어들어 봅시다. 먼저 HashMap이 무엇으로 구성되어 있는지 살펴보겠습니다.
테이블 배열: 이 배열은 주요 데이터 저장소입니다. 각 배열 셀(또는 버킷)에는 값 체인 또는 많은 요소의 경우 이진 트리를 저장할 수 있는 고유 인덱스가 포함되어 있습니다.
LoadFactor: LoadFactor는 HashMap을 확장하기 전에 채울 수 있는 양을 지정합니다. 기본 로드 계수는 0.75이며, 이는 메모리 절약과 액세스 속도 간의 균형을 유지합니다. HashMap이 75% 차면 테이블 크기를 두 배로 늘리고 요소를 재분배하여 효율성을 유지합니다.
임계값: 임계값은 HashMap이 테이블 확장을 결정하는 지점입니다. (용량 * 부하 인자)로 계산됩니다. 예를 들어 용량이 16이고 loadFactor가 0.75인 경우 임계값은 12가 됩니다. HashMap이 12개 요소에 도달하면 크기가 늘어납니다.
크기는 HashMap의 현재 키-값 쌍 수를 추적합니다.
HashMap의 각 키-값 쌍은 다음을 포함하는 노드라는 구조에 저장됩니다.
key - 쌍의 키
value—쌍의 값
hash - hashCode() 키를 기반으로 계산된 해시입니다.
다음 - 충돌 시 체인의 다음 요소에 대한 링크.
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;
}
....
}
각 노드는 충돌 시 동일한 버킷의 다음 노드에 연결되어 연결 목록을 생성합니다. 버킷에 8개 이상의 요소가 누적되면 이러한 목록은 자동으로 균형 이진 트리로 전환됩니다.
HashMap이 방이 많은 거대한 성이라고 상상해 보세요. 각 방마다 고유번호가 있는데, 열쇠는 어떤 방으로 갈지 어떻게 결정하나요? 이것은 특정 열쇠가 어느 버킷(방)에 놓일지 결정하는 데 도움이 되는 마법의 도구인 해시 함수의 작업입니다.
키를 추가하면 putVal 메소드가 키의 hashCode() 메소드를 호출하여 해시를 생성한 후 버킷 전체에 고르게 분산되도록 정제됩니다.
인덱스 계산: int index = hashCode & (length- 1) 공식을 사용하여 HashMap은 테이블 배열에서 버킷을 가리키는 인덱스를 계산합니다.
여기서 hashCode는 해시 함수를 통해 키가 받는 고유 코드입니다. 그런 다음 길이 - 1에 대해 비트 AND 연산을 수행합니다. 이는 해시 코드의 나머지 부분을 버킷 수로 나눈 값을 계산하는 것과 동일하므로 버킷 배열의 인덱스를 결정합니다.
import java.util.HashMap;
public class MagicalHashMap {
public static void main(String[] args) {
// Создаем новый HashMap
HashMap<String, String> rooms = new HashMap<>();
// Добавляем элементы в HashMap
rooms.put("apple", "A room full of apples");
rooms.put("banana", "A room full of bananas");
// Поиск по ключу
System.out.println("Room for 'apple': " + rooms.get("apple"));
System.out.println("Room for 'banana': " + rooms.get("banana"));
}
}
결과적으로 각 키는 해시 함수를 통과하여 비트별 AND를 사용하여 인덱스가 계산되는 고유한 방에 있게 됩니다.
충돌 검사: 버킷이 비어 있으면 새로운 키-값 쌍이 추가됩니다. 그렇지 않은 경우 putVal은 키가 일치하는지 확인합니다.
일치 * - 값이 업데이트됩니다.
*일치하지 않음 - 갈등이 발생함 - 이에 대해 더 자세히 알아보세요.
두 개의 열쇠가 같은 방에 있으면 어떻게 되나요?(여러 개의 열쇠가 하나의 양동이로 이어짐) 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;
}
....
}
이 예에서 KeyWithSameHash 클래스에는 모든 인스턴스에 대해 동일한 값을 반환하는 재정의된 hashCode() 메서드가 있으므로 모든 키가 테이블 배열의 동일한 셀에 위치하게 됩니다.
import java.util.HashMap;
public class MagicalHashMap {
public static void main(String[] args) {
// Создаем новый HashMap
HashMap<String, String> rooms = new HashMap<>();
// Добавляем элементы в HashMap
rooms.put("apple", "A room full of apples");
rooms.put("banana", "A room full of bananas");
// Поиск по ключу
System.out.println("Room for 'apple': " + rooms.get("apple"));
System.out.println("Room for 'banana': " + rooms.get("banana"));
}
}
모든 키에 대해 hashCode() 값이 42가 되므로 키가 추가될 때마다 테이블의 버킷 인덱스는 동일하게 됩니다.
하지만 열쇠를 누르면 머리가 부딪히는 대신 추가 문이 열리고 방이 새로운 방으로 이어지는 마법의 복도로 변합니다. 이 새로운 방은 본질적으로 충돌을 해결하는 방법입니다.
연결 목록: 동일한 해시 코드를 가진 두 개의 키가 동일한 버킷에 있으면 HashMap은 해당 버킷에 연결 목록을 만듭니다. 키는 이 목록에 계속 저장되며, 필요한 경우 키가 실제로 동일한지 확인하기 위해 equals() 메서드를 사용하여 검사가 수행됩니다.
레드-블랙 트리: 한 버킷의 충돌 횟수가 너무 많아지면(복도가 너무 길어짐) HashMap이 이를 레드-블랙 트리로 변환합니다. 이렇게 하면 검색 속도를 높이고 로드가 많은 경우 속도 저하를 방지할 수 있습니다.
HashMap 마법이 올바르게 작동하려면 동일한 값을 가진 두 개의 동일한 키가 동일한 해시 코드를 반환하고 또한 equals() 메서드를 사용하여 올바르게 비교되는 것이 중요합니다. 두 물체가 다른 방식으로 표현되어도 동일한지 확인하는 주문과 같습니다.
hashCode(): 각 객체에는 고유한 해시 코드가 있어야 합니다. 이를 통해 HashMap은 키를 배치해야 하는 버킷을 효율적으로 찾을 수 있습니다.
equals(): 두 객체의 해시 코드가 동일한 경우 equals() 메서드는 객체가 실제로 동일한지 확인합니다.
이 검사가 없으면 HashMap이 두 개의 서로 다른 키를 혼동하여 잘못된 프로그램 동작을 초래할 수 있습니다.
HashMap의 세계는 해시 함수와 충돌을 통해 열쇠가 방을 찾고 성을 정돈하는 데 도움이 되는 마법의 세계입니다. 각 키에는 해시 함수 덕분에 고유한 인덱스로 연결되는 자체 경로가 있습니다. 그리고 동일한 버킷에서 두 개의 키가 충돌하면 마법이 계속 작동하여 올바른 경로를 찾을 수 있도록 연결된 목록이나 레드-블랙 트리 형태로 새로운 문이 열립니다.
그래서 hashCode(), equals() 및 마법의 충돌 통로 덕분에 HashMap은 Java 개발자의 무기고에서 가장 강력한 도구 중 하나로 계속해서 가장 혼란스러운 상황에서도 효율성과 정확성을 보장합니다.
위 내용은 HashMap: 비밀의 방, 마법과 충돌의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
