[java] Java HashMap은 동일한 해시 코드로 다른 객체를 어떻게 처리합니까?

내 이해에 따라 나는 생각한다 :

두 객체가 동일한 해시 코드를 갖는 것은 완벽하게 합법적입니다.
두 객체가 같으면 (equals () 메소드 사용) 동일한 해시 코드를 갖습니다.
두 객체가 같지 않으면 동일한 해시 코드를 가질 수 없습니다

나 맞아?

이제 정확하다면 다음과 같은 질문이 있습니다. HashMap내부적으로 객체의 해시 코드를 사용합니다. 두 객체가 동일한 해시 코드를 가질 수 있다면 HashMap어떤 키를 사용 하는지 추적 할 수 있습니까?

누군가 HashMap내부적으로 객체의 해시 코드를 어떻게 사용 하는지 설명 할 수 있습니까 ?

답변

해시 맵은 다음과 같이 작동합니다 (조금 단순화되었지만 기본 메커니즘을 보여줍니다).

여기에는 키-값 쌍을 저장하는 데 사용되는 많은 “버킷”이 있습니다. 각 버킷에는 고유 한 번호가 있습니다. 이는 버킷을 식별하는 것입니다. 키-값 쌍을 맵에 넣으면 해시 맵이 키의 해시 코드를보고 식별자가 키의 해시 코드 인 버킷에 쌍을 저장합니다. 예를 들어, 키의 해시 코드는 235-> 쌍은 버킷 번호 235에 저장됩니다. 하나의 버킷은 하나 이상의 키-값 쌍을 저장할 수 있습니다.

해시 맵에서 값을 조회 할 때 키를 제공하면 먼저 사용자가 제공 한 키의 해시 코드를 살펴 봅니다. 그러면 해시 맵이 해당 버킷을 조사한 다음 버킷과 비교하여 버킷에있는 모든 쌍의 키와 제공 한 키를 비교합니다 equals().

이제 이것이 맵에서 키-값 쌍을 찾는 데 매우 효율적인 방법을 알 수 있습니다. 키의 해시 코드에 의해 해시 맵은 어떤 버킷을 찾아야하는지 즉시 알고 있으므로 해당 버킷의 내용에 대해서만 테스트하면됩니다.

위의 메커니즘을 살펴보면 키 hashCode()및 equals()방법에 필요한 요구 사항도 확인할 수 있습니다 .

두 개의 키가 동일 하면 (비교할 때 equals()반환 true) hashCode()메서드는 동일한 숫자를 반환해야합니다. 키가이를 위반하면 동일한 키가 다른 버킷에 저장 될 수 있으며 해시 맵은 동일한 버킷에서 보이므로 키-값 쌍을 찾을 수 없습니다.
두 개의 키가 다르면 해시 코드가 동일한 지 여부는 중요하지 않습니다. 해시 코드가 동일하면 동일한 버킷에 저장되며,이 경우 해시 맵을 사용 equals()하여 구분합니다.

답변

세 번째 주장이 잘못되었습니다.

두 개의 동일하지 않은 객체가 동일한 해시 코드를 갖는 것은 완벽하게 합법적입니다. 그것은에 의해 사용되는 HashMap맵이 신속하게 찾을 수 있도록하는 “첫 번째 패스 필터”로 가능한 지정된 키를 가진 항목을. 그런 다음 동일한 해시 코드를 가진 키가 지정된 키와 동일한 지 테스트합니다.

두 개의 동일하지 않은 객체가 동일한 해시 코드를 가질 수 없다는 요구 사항을 원하지 않을 것입니다. 그렇지 않으면 가능한 ^{32 개의} 객체로 제한 됩니다. (다른 클래스가 동일한 해시를 생성 할 수 있기 때문에 다른 유형이 객체의 필드를 사용하여 해시 코드를 생성 할 수도 없었 음을 의미합니다.)

답변

HashMap 구조 다이어그램

HashMapEntry객체 의 배열입니다 .

HashMap객체의 배열로 간주하십시오 .

이것이 무엇인지 살펴보십시오 Object.

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
…
}

각 Entry객체는 키-값 쌍을 나타냅니다. 버킷이 둘 이상인 경우이 필드 next는 다른 Entry객체를 참조합니다 Entry.

때로는 두 개의 다른 객체에 대한 해시 코드가 동일 할 수 있습니다. 이 경우 두 개의 객체가 하나의 버킷에 저장되고 연결된 목록으로 표시됩니다. 진입 점이 가장 최근에 추가 된 개체입니다. 이 객체는 next필드 등 이있는 다른 객체를 나타냅니다 . 마지막 항목은 null입니다.

HashMap기본 생성자로을 만들 때

HashMap hashMap = new HashMap();

어레이는 크기 16 및 기본 0.75로드 밸런스로 생성됩니다.

새로운 키-값 쌍 추가

키의 해시 코드 계산
hash % (arrayLength-1)요소를 배치 할 위치 계산 (버킷 번호)
에 이미 저장된 키로 값을 추가하려고하면 HashMap값이 덮어 쓰기됩니다.
그렇지 않으면 요소가 버킷에 추가됩니다.

버킷에 이미 하나 이상의 요소가있는 경우 새로운 요소가 추가되어 버킷의 첫 번째 위치에 배치됩니다. 해당 next필드는 이전 요소를 나타냅니다.

삭제

주어진 키에 대한 해시 코드를 계산
버킷 번호 계산 hash % (arrayLength-1)
버킷의 첫 번째 Entry 객체에 대한 참조를 가져오고 equals 메소드를 사용하여 지정된 버킷의 모든 항목을 반복합니다. 결국 우리는 올바른 것을 찾을 것 Entry입니다. 원하는 요소를 찾지 못하면null

답변

http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html 에서 훌륭한 정보를 찾을 수 있습니다.

요약:

HashMap은 해싱 원칙에 따라 작동합니다

put (key, value) : HashMap은 키와 값 객체를 Map.Entry로 저장합니다. 해시 맵은 해시 코드 (키)를 적용하여 버킷을 가져옵니다. 충돌이있는 경우 HashMap은 LinkedList를 사용하여 객체를 저장합니다.

get (key) : HashMap은 Key Object의 해시 코드를 사용하여 버킷 위치를 찾은 다음 keys.equals () 메서드를 호출하여 LinkedList에서 올바른 노드를 식별하고 Java HashMap에서 해당 키의 관련 값 객체를 반환합니다.

답변

다음은 버전 HashMap의 메커니즘에 대한 대략적인 설명입니다 (Java 6과 약간 다를 수 있음) .Java 8

데이터 구조

해시 테이블
해시 값은 hash()on 키 를 통해 계산되며 지정된 키에 사용할 해시 테이블의 버킷을 결정합니다.
링크 된 목록 (단일)
버킷의 요소 수가 적을 때는 단일 링크 된 목록이 사용됩니다.
빨강 검정 트리
버킷의 요소 수가 많으면 빨강 검정 트리가 사용됩니다.

수업 (내부)

Map.Entry
키 / 값 엔터티 인 맵에서 단일 엔터티를 나타냅니다.
HashMap.Node
노드의 링크 된 목록 버전.

다음을 나타낼 수 있습니다.
- 해시 버킷.
  해시 속성이 있기 때문입니다.
- 단일 연결리스트의 노드는, (따라서도 LinkedList의 머리) .
HashMap.TreeNode
노드의 트리 버전.

필드 (내부)

Node[] table
버킷 테이블 (링크 된 목록의 헤드)
버킷에 요소가 포함되어 있지 않으면 null이므로 참조 공간 만 차지합니다.
Set<Map.Entry> entrySet
엔터티 집합입니다.
int size
엔터티 수
float loadFactor
크기를 조정하기 전에 해시 테이블이 허용되는 정도를 나타냅니다.
int threshold
크기를 조정할 다음 크기입니다.
공식:threshold = capacity * loadFactor

방법 (내부)

int hash(key)
키로 해시를 계산하십시오.

해시를 버킷에 매핑하는 방법?
다음 논리를 사용하십시오.

static int hashToBucket(int tableSize, int hash) {
    return (tableSize - 1) & hash;
}

용량에 대해

해시 테이블에서 capacity는 버킷 수를 의미합니다 table.length.
또한을 통해 계산되지 수 threshold및 loadFactor, 따라서 더 클래스 필드로 정의 될 필요가있다.

다음을 통해 유효 용량을 얻을 수 있습니다. capacity()

운영

키로 엔티티를 찾으십시오.
먼저 해시 값으로 버킷을 찾은 다음 링크 된 목록 또는 검색 정렬 트리를 반복합니다.
키로 엔티티를 추가하십시오.
먼저 키의 해시 값에 따라 버킷을 찾으십시오.
그런 다음 값을 찾으십시오.
- 발견되면 값을 바꾸십시오.
- 그렇지 않으면 링크 된 목록의 시작 부분에 새 노드를 추가하거나 정렬 된 트리에 삽입하십시오.
크기 조정 도달
하면 threshold해시 테이블의 용량을 두 배로 늘리고 table.length모든 요소에 대해 해시를 수행하여 테이블을 다시 작성합니다.
이것은 비용이 많이 드는 작업 일 수 있습니다.

공연

get & put
Time의 복잡성은 다음 O(1)과 같습니다.
- 버킷은 배열 인덱스를 통해 액세스되므로 O(1).
- 각 버킷의 링크 된 목록은 길이가 작으므로로 볼 수 있습니다 O(1).
- 트리 수 또한 제한되어 있습니다. 요소 수가 증가하면 용량을 늘리고 다시 해시하므로로 볼 수는 O(1)없습니다 O(log N).

답변

해시 코드는 해시 맵에서 확인할 버킷을 결정합니다. 버킷에 둘 이상의 객체가있는 경우 버킷에서 어떤 항목이 원하는 항목 ( equals()) 메서드 와 같은지 찾기 위해 선형 검색이 수행됩니다 .

즉, 완벽한 해시 코드가 있고 해시 맵 액세스가 일정하면 버킷을 반복 할 필요가 없습니다 (기술적으로 MAX_INT 버킷이 있어야합니다 .Java 구현은 동일한 버킷에서 몇 개의 해시 코드를 공유 할 수 있음) 공간 요구 사항을 줄입니다). 최악의 해시 코드가있는 경우 (항상 같은 숫자를 반환) 맵에서 모든 항목을 검색해야하기 때문에 해시 맵 액세스가 선형이됩니다 (모두 동일한 버킷에 있음).

대부분의 경우 잘 작성된 해시 코드는 완벽하지는 않지만 일정하게 액세스 할 수있을 정도로 독특합니다.

답변

당신은 포인트 3에 착각합니다. 두 항목은 동일한 해시 코드를 가질 수 있지만 동일하지는 않습니다. OpenJdk에서 HashMap.get 구현을 살펴보십시오 . 해시가 같고 키가 같은지 확인합니다. 세 점이 사실이라면 키가 같은지 확인할 필요가 없습니다. 전자가 더 효율적인 비교이므로 해시 코드가 키보다 먼저 비교됩니다.

이것에 대해 조금 더 배우고 싶다면 Open Addressing 충돌 해결 에 관한 Wikipedia 기사를 살펴보십시오. . OpenJdk 구현이 사용하는 메커니즘이라고 생각합니다. 이 메커니즘은 다른 답변 중 하나가 언급 한 “버킷”접근 방식과 미묘하게 다릅니다.