HashMap: 비밀의 방, 마법과 충돌

HashMap을 비밀의 방(버킷)이 있는 성으로 상상해 봅시다. 각 방 앞에는 마법의 문이 있습니다(해시 함수). 이 마법 메커니즘은 어떻게 작동하며 두 마법 개체가 같은 장소에서 충돌하면 어떻게 되나요? 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이 이를 레드-블랙 트리로 변환합니다. 이렇게 하면 검색 속도를 높이고 로드가 많은 경우 속도 저하를 방지할 수 있습니다.

equals() 및 hashCode() 작동 방식

HashMap 마법이 올바르게 작동하려면 동일한 값을 가진 두 개의 동일한 키가 동일한 해시 코드를 반환하고 또한 equals() 메서드를 사용하여 올바르게 비교되는 것이 중요합니다. 두 물체가 다른 방식으로 표현되어도 동일한지 확인하는 주문과 같습니다.

hashCode(): 각 객체에는 고유한 해시 코드가 있어야 합니다. 이를 통해 HashMap은 키를 배치해야 하는 버킷을 효율적으로 찾을 수 있습니다.
equals(): 두 객체의 해시 코드가 동일한 경우 equals() 메서드는 객체가 실제로 동일한지 확인합니다.
이 검사가 없으면 HashMap이 두 개의 서로 다른 키를 혼동하여 잘못된 프로그램 동작을 초래할 수 있습니다.

결론

HashMap의 세계는 해시 함수와 충돌을 통해 열쇠가 방을 찾고 성을 정돈하는 데 도움이 되는 마법의 세계입니다. 각 키에는 해시 함수 덕분에 고유한 인덱스로 연결되는 자체 경로가 있습니다. 그리고 동일한 버킷에서 두 개의 키가 충돌하면 마법이 계속 작동하여 올바른 경로를 찾을 수 있도록 연결된 목록이나 레드-블랙 트리 형태로 새로운 문이 열립니다.

그래서 hashCode(), equals() 및 마법의 충돌 통로 덕분에 HashMap은 Java 개발자의 무기고에서 가장 강력한 도구 중 하나로 계속해서 가장 혼란스러운 상황에서도 효율성과 정확성을 보장합니다.

위 내용은 HashMap: 비밀의 방, 마법과 충돌의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!