[java] 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).

---

답변