HashMap은 Java에서 어떻게 작동합니까?

HashMap오늘 인터뷰 중 가장 좋아하는 토론 주제는 이라는 점에 대부분의 분들이 동의하실 것입니다 . 가끔 동료들과 비슷한 토론을 했는데 정말 도움이 됐어요. 이제 나는 당신과 그런 토론을 할 것입니다. HashMap의 내부 구조와 작동 방식에 관심이 있는 분이라면 이미 HashMap 의 기본 사항을 잘 알고 계시리라 생각하므로 해당 부분은 건너뛰겠습니다. 하지만 이 내용이 처음이라면 Java Docs 사이트를 방문하는 것이 좋습니다 . 계속 진행하기 전에 이전 기사인 Java의 hashCode 및 equals 메소드 작업을 확인해 보시기 바랍니다. 이 기사의 내용:

1. 유일한 대답입니다.
2. 해싱이란 무엇입니까?
3. 수업에 대해 조금 Entry.
4. . put()_
5. 방법이 작동하는 방법 get().
6. 노트

유일하게 가능한 대답

누군가 나에게 " HashMap은 어떻게 작동하나요?"에 대해 설명해달라고 요청하면 ", 나는 간단히 대답하겠습니다: " 해싱의 원칙에 따르면 ." 이보다 더 간단할 수는 없습니다. 이를 이해하고 더 자세한 답변을 얻으려면 해싱의 기본 사항을 알아야 합니다. 오른쪽?

해싱이란 무엇입니까?

가장 간단한 형태의 해싱은 속성에 수식/알고리즘을 적용한 후 변수/개체를 고유한 코드로 변환하는 방법입니다. 실제 해시 함수는 다음 규칙을 따라야 합니다. 해시 함수는 동일하거나 동일한 개체에 적용될 때마다 동일한 해시 코드를 반환해야 합니다. 즉, 두 개의 동일한 객체가 동일한 해시 코드를 차례로 반환해야 합니다. 이에 대한 자세한 내용은 다음에서 읽을 수 있습니다. Java에서 hashCode 및 equals 메서드 사용

Entry 클래스에 대해 조금

정의에 따르면 맵은 “값과 키를 쌍으로 저장하는 객체”입니다. 아주 간단하죠? 그렇다면 HashMap에는 값과 키 쌍을 저장하는 일종의 메커니즘이 있어야 할까요? 답변 - 그렇습니다. 다음과 같은 HashMap내부 클래스가 있습니다 .Entry

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

당연히 클래스에는 Entry속성으로 저장된 키와 값이 있습니다. 키는 로 표시되어 final있으며 두 개의 추가 필드도 표시됩니다: next및 hash. 기사가 진행됨에 따라 이러한 필드의 목적을 이해하려고 노력할 것입니다.

Java put() 메소드는 무엇을 합니까?

메소드 구현에 대해 알아보기 전에 put()클래스의 인스턴스가 Entry배열에 저장된다는 점을 이해하는 것이 매우 중요합니다. HashMap 클래스는 이 변수를 다음과 같이 정의합니다.

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

이제 메소드 구현 코드를 살펴보십시오 put().

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

단계별로 알아 봅시다.

• 먼저 키가 존재하는지 확인합니다. 키가 존재하지 않는 경우( ) 해당 값 의 null해시 코드는 , 이므로 해당 값은 테이블의 0 위치에 배치됩니다 null.это – всегда 0


• 다음 단계에서는 메소드를 호출하여 얻은 키의 해시 코드를 사용하여 해시 값을 계산합니다 hashCode(). 이 해시 값은 객체가 배치될 배열의 위치를 ​​계산하는 데 사용됩니다 Entry. JDK 설계자는 잘못 작성된 함수가 hashCode()너무 높거나 낮은 해시 값을 반환할 수 있다고 가정했습니다. 이 문제를 해결하기 위해 그들은 또 다른 hash()함수를 도입하고 객체의 해시 값을 전달하여 해시 값이 배열의 크기와 일치하도록 만들었습니다.


• indexFor(hash, table.length)이제 객체가 배치될 정확한 위치를 계산하기 위해 함수가 호출됩니다 Entry.


• 이것이 주요 부분이 시작되는 곳입니다. 이제 우리가 알고 있는 두 개의 서로 다른 객체가 동일한 해시 코드를 가질 수 있다는 사실을 바탕으로 다음과 같은 질문을 합니다: 두 개의 서로 다른 객체가 [버킷] 배열의 동일한 위치에 배치됩니까? 대답은 입니다 LinkedList. 기억하신다면 클래스 Entry에는 " " 속성이 있습니다 next. 이 속성은 항상 체인의 다음 개체를 가리킵니다. 이것이 바로 행동입니다 LinkedList.

따라서 객체는 Entry형식으로 저장됩니다 LinkedList. 객체가 Entry특정 위치에 배치될 때 HashMap은 해당 위치에 이미 항목이 있는지 확인합니다. 항목이 없으면 개체가 이 위치에 배치됩니다. 그러나 이 위치에 이미 개체가 있으면 다음 속성이 확인됩니다. 반환되고 null현재 개체 Entry가 의 다음 링크가 됩니다 LinkedList. 다음 변수가 가 아닌 경우 을 null찾을 때까지 다음 변수에 대해 절차가 반복됩니다 null. 값은 다르지만 이전과 동일한 키를 가진 다른 객체를 넣으면 어떻게 될까요? 논리적으로 이로 인해 이전 값이 대체되어야 합니다. 어떻게 이런 일이 발생하나요? 일반적으로 객체의 위치를 ​​파악한 후 계산된 위치로 Entry이동하면서 각 객체에 대한 키 비교 메소드를 호출합니다 . 이러한 개체는 모두 유사한 해시 코드를 가질 수 있지만 메서드는 실제 유사성을 확인합니다. 이는 내의 값만 대체합니다 . 따라서 HashMap은 모든 키의 고유성을 보장합니다. LinkedListHashMapEntryEntryLinkedListequals()Entry

Java get() 메소드는 어떻게 작동합니까?

이제 키-값 쌍이 HashMap. 다음 큰 질문은: 객체가 HashMap에서 메소드로 전달되면 무슨 일이 발생합니까 get()? 물건의 가치는 어떻게 결정되나요? 메소드에서 키의 고유성을 결정하는 방식은 put()메소드가 적용되는 논리와 동일하므로 우리는 이미 답을 알고 있어야 합니다 get(). HashMap인수로 전달된 객체의 키를 결정한 후에 는 해당 의 값을 반환합니다 Entry. 일치하는 항목이 없으면 메서드는 를 get()반환합니다 null. 코드를 살펴보겠습니다.

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

put()위의 코드는 지금까지의 메소드와 유사하며 if (e.hash == hash && ((k = e.key) == key || key.equals(k))), 이후에는 단순히 객체의 값을 반환합니다.

노트

• 객체에 저장되는 데이터 구조는 이름 과 유형을 Entry갖는 배열입니다 .tableEntry
• 배열의 각 개별 위치는 LinkedList객체의 첫 번째 요소를 포함할 수 있으므로 버킷이라고 합니다 Entry.
• hashCode()물체의 위치를 ​​계산하려면 키가 필요합니다 Entry.
• equals()키는 맵( )에서 키의 고유성을 확인하는 데 사용됩니다 map.
• hashCode()및 값은 메소드 및 에서 equals()사용되지 않습니다 .get()set()HashMap
• 값이 있는 키의 해시 코드는 null항상 0입니다. 그리고 그러한 객체는 Entry항상 배열의 0 위치에 저장됩니다.

이 글을 통해 제 생각이 정확하게 전달되었으면 좋겠습니다. 오류를 발견하거나 궁금한 점이 있으면 댓글로 남겨주세요. 즐거운 학습!