Java 해시 저장에 대한 자세한 설명과 간단한 예

Java 해시 저장소

Java에서 해시 저장소의 데이터 구조는 주로 HashSet, HashMap, LinkedHashSet, LinkedHashMap 및 HashTable 등을 의미합니다. Java의 해시 저장 메커니즘을 이해하려면 먼저 equals() 및 hashCode()라는 두 가지 메서드를 이해해야 합니다. equals() 메소드와 "==" 관계 연산자와의 차이점에 대해서는 다른 글에서 설명했습니다. hashCode()는 Object 클래스에 정의된 메소드입니다:

public native int hashCode();

int 값을 반환하는 로컬 메소드이며 Object 클래스에서는 구현되지 않습니다. 이 방법은 주로 해싱을 사용하는 데이터 구조에 사용되며 일반적으로 해시 기반 컬렉션에서 작동합니다. 예를 들어 객체를 컨테이너(HashMap이라고 가정)에 삽입할 때 해당 객체가 컨테이너에 이미 존재하는지 확인하는 방법입니다. 컨테이너는 어디에 있나요? 컨테이너에는 수천 개의 요소가 있을 수 있으므로, equals() 메서드를 사용하여 요소를 순차적으로 비교하는 것은 매우 비효율적입니다. 해싱의 가치는 속도이며 키를 빠르게 찾을 수 있도록 어딘가에 저장합니다. 요소 집합을 저장하는 가장 빠른 데이터 구조는 배열이므로 키 정보를 저장하는 데 사용합니다(키 자체가 아니라 키 정보라는 점에 유의하세요). 그런데 배열이 용량을 조절할 수 없기 때문에 문제가 있습니다. 불확실한 개수의 값을 Map에 저장하고 싶은데 배열의 용량에 따라 키 수가 제한되는 경우 어떻게 해야 할까요?

정답은 배열이 키 자체를 저장하는 것이 아니라, 키 객체를 통해 숫자를 생성하고 이를 배열의 첨자로 사용하는 것입니다. 이는 Object 에 정의되어 있으며 클래스에서 재정의된 hashCode() 메서드에 의해 생성될 수 있습니다. 고정된 배열 용량 문제를 해결하기 위해 서로 다른 키가 동일한 첨자를 생성할 수 있는데, 이러한 현상을 충돌이라고 합니다. 따라서 컨테이너에 있는 값을 조회하는 과정은 hashCode()를 통해 삽입할 객체의 해시 코드를 먼저 계산한 후, 그 해시 코드를 이용하여 배열을 조회하는 과정이다. 충돌은 종종 외부 링크를 통해 처리됩니다. 즉, 배열은 값을 직접 저장하지 않고 값 목록을 저장한 다음 목록의 값에 대해 선형 쿼리를 수행합니다. 쿼리의 이 부분은 자연스럽게 발생합니다. 더 느리게. 그러나 해시 함수가 충분히 좋으면 배열의 각 위치에 있는 값이 더 적어집니다. 따라서 해싱 메커니즘은 몇 가지 요소만 비교하여 배열의 특정 위치로 빠르게 이동할 수 있습니다. HashMap이 그렇게 빠른 이유는 다음과 같습니다.

public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
   inflateTable(threshold);
  }
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key);
  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;
 }

핵심은 언제가 아닙니다. 비어 있으면 키 개체에 따라 해시 코드 해시를 얻은 다음 해시 코드를 통해 배열의 첨자 i를 얻습니다. table[i]로 표시된 목록을 반복하고 equals()를 통해 키가 존재하는지 확인합니다. 존재하는 경우 이전 값을 새 값으로 업데이트하고 이전 값을 반환합니다. 그렇지 않으면 새 키-값 쌍을 HashMap에 추가합니다. . 여기에서 보면 hashCode 메소드는 equals 메소드 호출 횟수를 줄여 프로그램 효율성을 높이기 위해 존재한다는 것을 알 수 있다.

여기서 주의할 점은 hashCode()가 항상 고유 식별 코드를 반환할 수 있어야 하는 것은 아니지만, equals() 메서드는 두 개체가 동일한지 여부를 엄격하게 확인해야 한다는 것입니다.

읽어주셔서 감사합니다. 도움이 되기를 바랍니다. 이 사이트를 지원해 주셔서 감사합니다!

자바 해시 저장에 대한 더 자세한 설명과 간단한 예시는 PHP 중국어 홈페이지를 참고해주세요!