저장 구조
먼저 해시 맵은 해시 테이블에 따라 저장됩니다. 그 안에는 배열이 있습니다. 요소가 저장 될 때, 먼저 키의 해시 값을 계산하고 해시 값에 따라 배열에서 요소의 해당 첨자를 찾으십시오. 이 위치에 요소가 없으면 현재 요소를 직접 넣으십시오. 요소가있는 경우 (여기로 기억) 현재 요소를 요소 A의 전면에 연결 한 다음 현재 요소를 배열에 넣으십시오. 따라서 해시 맵에서 배열은 실제로 링크 된 목록의 첫 번째 노드를 저장합니다. 아래는 Baidu Encyclopedia의 사진입니다.
위 그림과 같이 각 요소는 요소의 키와 값이 저장되는 항목 객체이며 다음 객체를 가리키는 데 사용할 수있는 포인터가 있습니다. 동일한 해시 값 (즉, 충돌)을 가진 모든 키는 지퍼 방법 인 링크 된 목록을 사용하여 함께 문자합니다.
내부 변수
// 기본 초기 용량 정적 최종 최종 int default_initial_capacity = 16; // 최대 용량 정적 최종 최종 int maximum_capacity = 1 << 30; // 기본 부하 계수 정적 최종 플로트 기본 _load_factor = 0.75f; // HAST 테이블 <k, v> [] 테이블; // treshOld intshint intshint intshint intshind intshint intshind intshint intshind intshind intshind intshind intshind intshind intshold a. 해시 배열의 하중 계수 최종 플로트로드 변수;
위의 변수에서 용량은 해시 테이블의 길이, 즉 테이블의 크기 및 기본값은 16입니다.로드 계수로드 변형기는 해시 테이블의 "전체도"이며 JDK의 문서는 다음과 같습니다.
하중 계수는 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 찼는지를 측정 한 것입니다. 해시 테이블의 항목 수가 하중 계수의 곱을 초과하고 현재 용량을 초과하면 해시 테이블이 버킷 수의 약 두 배를 갖도록 해시 테이블이 다시 해싱됩니다 (즉, 내부 데이터 구조가 재건 됨).
일반적인 의미는 : 로딩 계수는 확장 전에 해시 테이블을 얼마나 가득 채울 수 있는지를 측정하는 것입니다. 해시 테이블의 "키-값 쌍"의 수가 현재 용량 및 로딩 계수의 제품을 초과하면 해시 테이블 해시 (즉, 내부 데이터 구조가 재건 됨) 및 해시 테이블의 용량이 원래의 두 배가됩니다.
위 변수 정의에서 볼 수 있듯이 기본로드 계수 Default_load_factor는 0.75입니다. 이 값이 클수록 공간 활용률이 높지만 쿼리 속도 (Get and Put 포함)는 속도가 느려집니다. 로딩 계수를 이해 한 후 임계 값도 이해할 수 있습니다. 실제로 용량* 하중 계수와 같습니다.
건설자
public hashmap (int initialcapacity, float loadfactor) {if (initialcapacity <0) 새로운 불법 불법 행위 ( "불법 초기 용량 :" + initialcapacity); if (InitialCapacity> maximum_capacity) 초기 커피 = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) 새로운 불법 불법 행위 ( "불법 하중 계수 :" + loadfactor); // 2> = InitialCapacity int 용량 = 1; while (용량 <initialcapacity) // 지정된 용량 용량보다 큰 가장 작은 전력을 계산합니다 << = 1; this.loadfactor = loadfactor; 임계 값 = (int) math.min (용량 * loadfactor, maximum_capacity + 1); 표 = 새로운 항목 [용량]; // 해시 테이블에 공간을 할당하십시오 usealthashing = sun.misc.vm.isbooted () && (용량> = holder.alternative_hashing_threshold); init ();}여러 생성자가 있으며 결국 위를 호출 할 것입니다. 두 개의 매개 변수를 허용합니다. 하나는 초기 용량이고 다른 하나는 로딩 계수입니다. 처음에는 먼저 가치 조합이 합법적인지 여부를 결정하고 문제가 있으면 예외가 발생합니다. 중요한 것은 아래의 용량 계산이며, 논리는 초기 용량보다 큰 2의 가장 작은 전력을 계산하는 것입니다. 실제로, 목적은 지정된 초기 용량보다 용량을 더 이상 또는 동일하게 만드는 것이지만,이 값은 2의 지수 배수이어야합니다. 이는 주요 문제입니다. 그 이유는 주로 해시 값을 매핑하기 때문입니다. 먼저 해시 맵의 해시 메소드를 살펴 보겠습니다.
최종 int 해시 (객체 k) {int h = 0; if (usealthashing) {if (k instanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h = 해시드; } h ^= k.hashcode (); //이 함수는 각 비트 위치에서 // 상수 배수에 의해서만 다른 해시 코드가 결합 된 // 충돌 횟수 (기본 부하 계수에서 약 8)를 갖도록합니다. h ^ = (h >>> 20) ^ (h >>> 12); 반환 h ^ (h >>> 7) ^ (h >>> 4);} 정적 int indexfor (int h, int length) {return h & (longth-1);}HASH () 메소드는 키의 해시 값을 다시 계산하고 비교적 복잡한 비트 작업을 사용합니다. 특정 논리를 모르겠습니다. 어쨌든, 그것은 분명히 더 나은 방법으로 갈등이나 무언가를 줄일 수 있습니다.
아래 indexfor ()는 해시 값을 기반으로 해시 테이블의 요소 첨자입니다. 일반적으로 해시 테이블에서 해시 값을 사용하여 테이블 길이를 변조합니다. 길이 (즉, 용량)가 2의 전력 인 경우 H & (길이 -1)은 동일한 효과입니다. 또한, 2의 전력은 짝수 숫자 여야하며, 그 다음 1을 빼면 홀수이고 바이너리의 마지막 비트는 1이어야합니다. 그러면 마지막 H & (길이 -1)는 1 또는 0 일 수 있으며, 이는 균등하게 해당 될 수 있습니다. 길이가 홀수 인 경우 길이 -1이 짝수이고 마지막 비트는 0입니다.이 시점에서 H & (길이 -1)의 마지막 비트는 0 일 수 있고 모든 결과 위트 스크립트가 짝수이므로 공간의 절반이 낭비됩니다. 따라서 해시 맵의 용량은 2의 전력이어야합니다. 기본값 기본값 _initial_capacity = 16이고 maximum_capacity = 1 << 30이 모두 다음과 같습니다.
입력 객체
Hashmap의 키 값 쌍은 Hashmap의 내부 클래스 인 Entry Objects로 캡슐화됩니다. 구현을 살펴 보겠습니다.
정적 클래스 항목 <k, v>는 map.entry <k, v> {최종 K 키; v 값; 입력 <k, v> 다음; int 해시; 입력 (int h, k k, v v, enth <k, v> n) {value = v; 다음 = n; 키 = k; 해시 = h; } public final k getkey () {반환 키; } public final v getValue () {return 값; } public final v setValue (v newValue) {v OldValue = value; 값 = NewValue; OldValue를 반환하십시오. } public final boolean equals (object o) {if (! (o instanceof map.entry)) return false; map.entry e = (map.entry) o; 개체 k1 = getkey (); 객체 k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {object v1 = getValue (); 객체 v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) true를 반환합니다. } false를 반환합니다. } public final int hashcode () {return (key == null? 0 : key.hashcode ()) ^ (value == null? 0 : value.hashcode ()); } public final String toString () {return getKey () + "=" + getValue (); } void RecordAccess (Hashmap <k, v> m) {}}이 클래스의 구현은 간단하고 이해하기 쉽습니다. getkey (), getValue ()와 같은 메소드는 통화를 위해 제공됩니다. 평등을 결정하려면 키와 가치가 모두 같아야합니다.
작업을하십시오
받기 전에 먼저 넣으므로 먼저 put () 메소드를보십시오.
public v put (k key, v value) {if (key == null) return putfornullkey (value); int hash = 해시 (키); int i = indexfor (Hash, table.length); for (Entry <k, v> e = 테이블 [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 = 값; e.recordaccess (this); OldValue를 반환하십시오. }} modcount ++; Addentry (해시, 키, 값, i); 귀환 null;}이 방법에서는 먼저 키가 무효인지를 결정하십시오. 그렇다면 putfornullkey () 메소드를 호출합니다. 즉, 해시 맵은 키가 null을 허용합니다 (실제로 값은 값이 될 수 있습니다). null이 아닌 경우 해시 값을 계산하고 표에서 위시를 가져옵니다. 그런 다음 해당 링크 목록으로 이동하여 동일한 키가 이미 존재하는지 여부를 쿼리하십시오. 이미 존재하면 값이 직접 업데이트됩니다. 그렇지 않으면 삽입을 위해 addentry () 메소드를 호출하십시오.
putfornullkey () 메소드를 살펴보십시오.
private v putfornullkey (v value) {for (Entry <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) {v OldValue = e.Value; e.Value = 값; e.recordaccess (this); OldValue를 반환하십시오. }} modcount ++; Addentry (0, null, 값, 0); 귀환 null;}키가 NULL 일 때 값이 존재하면 값이 업데이트된다는 것을 알 수 있습니다. 그렇지 않으면 addentry ()가 삽입하도록 호출됩니다.
다음은 addentry () 메소드의 구현입니다.
void addentry (int Hash, k key, v value, int buctIndex) {if ((size> = threshold) && (null! = 테이블 [buctIndex])) {resize (2 * table.length); hash = (null! = 키)? 해시 (키) : 0; BucketIndex = indexfor (Hash, table.length); } createEntry (해시, 키, 값, buctIndex);} void createEntry (int hash, k key, v value, int buctIndex) {enther <k, v> e = 테이블 [buctIndex]; 표 [bucetIndex] = new Entry <> (해시, 키, 값, e); 크기 ++;}먼저 용량을 확장할지 여부를 결정하십시오 (용량 확장 용량은 첨자 값을 재 계산하고 요소를 복사 할 수 있음)를 한 다음 배열 첨자를 계산 한 다음 최종적으로 CreateEntry ()에서 헤더 삽입 방법을 사용하여 요소를 삽입하십시오.
작동하십시오
public v get (Object Key) {if (key == null) return getFornUllKey (); Entry <k, v> entry = getentry (키); return null == Entry? null : entry.getValue ();} private v getfornullkey () {for (enther <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) return e.value; } return null;} 최종 항목 <k, v> getEntry (개체 키) {int hash = (key == null)? 0 : 해시 (키); 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! = null && key.equals (k))) return e; } return null;}이것은 put ()보다 간단합니다. 또한 키가 null인지 확인한 다음 링크 된 목록의 트래버스 쿼리를 결정해야합니다.
성능 최적화
Hashmap은 모든 Java 프로그램의 어느 곳에서나 볼 수있는 효율적이고 보편적 인 데이터 구조입니다. 기본 지식을 먼저 소개하겠습니다. 아시다시피, Hashmap은 hashcode () 및 equals () 키를 사용하여 값을 다른 버킷으로 나눕니다. 버킷의 수는 일반적으로 맵의 레코드 수보다 약간 더 크기 때문에 각 버킷에는 적은 값 (바람직하게는 하나)이 포함됩니다. 키를 검색 할 때 버킷 (hashcode ()를 사용하여 버킷 수를 모듈로 사용)와 일정한 시간에 찾고있는 물체를 빠르게 찾을 수 있습니다.
당신은 이미이 모든 것을 알고 있어야합니다. 해시 충돌이 해시 맵의 성능에 치명적인 영향을 줄 수 있음을 알고있을 것입니다. 다중 해시 코드 () 값이 동일한 버킷에 속하면이 값은 링크 된 목록에 저장됩니다. 최악의 경우, 모든 키는 동일한 버킷에 매핑되므로 해시 맵은 링크 된 목록으로 퇴보합니다. 검색 시간은 O (1)에서 O (n)으로입니다. 먼저 정상적인 상황에서 Java 7 및 Java 8의 해시 맵 성능을 테스트합시다. hashcode () 메소드의 동작을 제어하기 위해 키 클래스를 다음과 같이 정의합니다.
클래스 키를 비교할 수있는 <key> {private final int value; key (int value) {this.value = value;}@retridepublic int compareto (key o) {return integer.compare (this.value, o.value);}@overridepublic boolean (대상 O) {if (this == o) return (getclass); o. getClass ()) return false; key key = (key) o; return value == key.value;}@attredepublic int hashcode () {return value;}}키 클래스의 구현은 상당히 표준입니다. equals () 메소드를 다시 작성하고 상당히 괜찮은 hashcode () 메소드를 제공합니다. 과도한 GC를 피하기 위해 매번 다시 만들기 시작하는 대신 불변의 핵심 객체를 캐시했습니다.
클래스 키를 비교할 수있는 <key> {public class 키 {public static final int max_key = 10_000_000; private static final key [] keys_cache = new key [max_key]; static {for (int i = 0; i <max_key; ++ i) {keys_cache [i] = new key (i);} 공개 value) {int value) {int value of (int value);이제 테스트를 시작할 수 있습니다. 당사의 벤치 마크는 연속 키 값을 사용하여 다양한 크기 (10의 승수, 1 ~ 1 백만)의 해시 맵을 만듭니다. 테스트에서는 키를 사용하여 다양한 크기의 해시 맵에 걸리는 시간을 검색하고 측정합니다.
import com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simplebenchmark; public class mapbenchmark 확장 SimpleBenchmark {private hashmap <키, 정수>지도; @paramprivate int Mapsize; @overrideprotected void 설정 () hashmap <> (맵 사이즈); for (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void timemapget (int reps) {for (int i = 0; i <reps; i ++) {map.get (i % mapsize);}}}}}}}}}}}}.흥미롭게도,이 간단한 Hashmap.get ()에서 Java 8은 Java 7보다 20% 빠릅니다. 전체 성능도 상당히 좋습니다. Hashmap에는 백만 개의 레코드가 있지만 단일 쿼리는 10 개의 나노초 미만이 걸렸으며, 이는 내 기계의 약 20 CPU 사이클입니다. 매우 충격적입니다! 그러나 이것은 우리가 측정하고 싶은 것이 아닙니다.
열쇠가 나쁘다고 가정하고 항상 같은 값을 반환합니다. 이것은 최악의 시나리오이며 해시 맵을 전혀 사용해서는 안됩니다.
클래스 키 구현 비슷한 <key> {//...@overridepublic int hashcode () {return 0;}}Java 7의 결과가 예상됩니다. 해시 맵의 크기가 커짐에 따라 get () 방법의 오버 헤드가 점점 커지고 있습니다. 모든 레코드가 동일한 버킷의 매우 길고 링크 된 목록에 있으므로 평균 한 레코드를 검색하려면 목록의 절반을 가로 질러야합니다. 따라서, 시간 복잡성은 O (n)이라는 그림에서 볼 수 있습니다.
그러나 Java 8은 훨씬 더 잘 수행됩니다! 로그 곡선이므로 성능은 훨씬 더 좋습니다. 심각한 해시 충돌의 최악의 시나리오에도 불구하고,이 동일한 벤치 마크는 O (LOGN)의 JDK8에서 시간 복잡성을 갖습니다. JDK 8의 곡선 만보면 더 명확 해집니다. 이것은 로그 선형 분포입니다.
큰 O 기호가 여기에 사용 되더라도 왜 그렇게 큰 성능 향상이 있습니까 (Big O는 점근 상한을 설명)? 실제로이 최적화는 JEP-180에서 언급되었습니다. 버킷의 레코드가 너무 커지면 (현재 Treeify_threshold = 8) Hashmap은 특수 Treemap 구현으로 동적으로 대체합니다. 이로 인해 O (logn)가 더 나은 결과를 초래할 수 있습니다. o (n). 어떻게 작동합니까? 충돌이있는 키에 해당하는 레코드는 단순히 링크 된 목록에 추가되며 이러한 레코드는 Traversal을 통해서만 찾을 수 있습니다. 그러나이 임계 값을 초과 한 후 해시 값은 해시 값을 트리의 분기 변수로 사용하여 목록을 이진 트리로 업그레이드하기 시작합니다. 두 해시 값이 동일하지 않지만 동일한 버킷을 가리키면 더 큰 값이 오른쪽 하위 트리에 삽입됩니다. 해시 값이 동일하면 Hashmap은 키 값이 비슷한 인터페이스에 의해 가장 잘 구현되어 순서대로 삽입 할 수 있기를 희망합니다. 이것은 Hashmap의 키에 필요하지 않지만 구현하는 경우 가장 좋습니다. 이 인터페이스가 구현되지 않으면 심각한 해시 충돌이 발생할 때 성능 향상을 달성 할 것으로 기대해서는 안됩니다.
이 성능 향상의 사용은 무엇입니까? 예를 들어, 악의적 인 프로그램은 해싱 알고리즘을 사용하고 있음을 알고 있다면 많은 요청을 보내서 심각한 해시 충돌이 발생할 수 있습니다. 그런 다음 이러한 키에 지속적으로 액세스하면 서버의 성능에 크게 영향을 줄 수있어 서비스 거부 공격 (DOS)이 발생합니다. JDK 8의 O (N)에서 O (LOGN)까지의 도약은 유사한 공격을 효과적으로 방지 할 수 있으며, 해시 맵 성능의 예측 가능성을 약간 향상시킬 수 있습니다. 이 개선이 결국 상사가 JDK 8로 업그레이드하는 데 동의하도록 설득하기를 바랍니다.
테스트에 사용되는 환경은 다음과 같습니다. Intel Core i7-3635QM @ 2.4 GHz, 8GB 메모리, SSD 하드 디스크, 기본 JVM 매개 변수를 사용하여 64 비트 Windows 8.1 시스템에서 실행됩니다.
요약
해시 맵의 기본 구현은 상기 분석 된 바와 같이, 마지막으로 요약이 이루어집니다.