Hashmap과 Hashset은 Java Collection Framework의 중요한 두 멤버입니다. Hashmap은 MAP 인터페이스의 공통 구현 클래스이며 Hashset은 세트 인터페이스의 공통 구현 클래스입니다. Hashmap 및 Hashset에 의해 구현 된 인터페이스 사양은 다르지만, 기본 해시 저장 메커니즘은 정확히 동일하며 해시 세트 자체조차도 해시 맵을 사용하여 구현합니다.
실제로 해시 세트와 해시 맵 사이에는 많은 유사점이 있습니다. 해시 세트의 경우 시스템은 해시 알고리즘을 사용하여 수집 요소의 저장 위치를 결정하여 수집 요소를 빠르게 저장하고 검색 할 수 있도록합니다. 해시 맵의 경우 시스템 키 값이 전체적으로 처리되며 시스템은 해시 알고리즘을 기반으로 키 값의 저장 위치를 항상 계산하여 맵의 키 값 쌍을 빠르게 저장하고 검색 할 수 있습니다.
컬렉션 스토리지를 소개하기 전에 컬렉션은 Java 객체를 저장한다고 주장하지만 실제로 Java 객체를 세트 컬렉션에 넣지는 않지만 세트 컬렉션에서 이러한 객체에 대한 참조 만 유지합니다. 즉, Java 컬렉션은 실제로 실제 Java 객체를 가리키는 여러 참조 변수 모음입니다.
1. 해시 맵의 기본 기능
JDK 소스 코드 hashmap.class에서 주석을 읽은 후 많은 해시 맵 기능을 요약 할 수 있습니다.
Hashmap은 키와 값이 모두 null을 허용하지만 Hashtable은 그렇지 않습니다.
Hashmap은 스레드 insecure이고 Hashtable은 스레드 안전입니다
해시 맵의 요소 순서가 항상 동일하지는 않으며 동일한 요소의 위치도 시간이 지남에 따라 변경 될 수 있습니다 (크기 조정)
해시 맵을 가로 지르는 시간 복잡성은 용량과 기존 요소의 수에 비례합니다. Traversal의 효율을 보장하려면 초기 용량을 너무 높게 설정할 수 없거나 균형 계수를 너무 낮게 설정할 수 없습니다.
이전 관련 목록과 유사하게, Hashmap은 스레드 보험이므로 반복 프로세스 중에 반복기가 컨테이너 구조를 변경하려고 할 때 FAIL-FAST가 생성됩니다. 동기화 된 해시 맵은 collections.synchronizedmap (hashmap)을 통해 얻을 수 있습니다.
2. 해시 테이블 데이터 구조 분석
해시 테이블 (해시 테이블, 해시 테이블)은 키워드를 기반으로 메모리 스토리지 위치에 직접 액세스하는 데이터 구조입니다. 즉, 해시 테이블은 키워드와 스토리지 주소 사이의 직접 매핑을 설정합니다.
아래 그림과 같이, 키는 해시 함수를 통해 버킷의 인덱스 위치를 얻습니다.
해시 기능을 통해 인덱스를 얻는 것은 필연적으로 같은 상황, 즉 충돌이 발생합니다. 충돌을 해결하는 몇 가지 방법은 다음과 같습니다.
열린 주소 지정 :이 방법의 기본 아이디어는 충돌이 발생할 때 순서대로 테이블 아래의 N 위치를 스캔하고 무료가있는 경우 작성하는 것입니다. 특정 알고리즘은 더 이상 설명되지 않으며 다음은 회로도입니다.
별도의 체인 :이 방법의 기본 아이디어는 충돌이 발생할 때 링크 된 목록에서 동일한 인덱스 값으로 항목을 함께 연결하는 것입니다. 특정 알고리즘은 더 이상 설명되지 않으며 다음은 회로도입니다.
JDK의 해시 맵에서 충돌을 해결하는 방법은 별도의 체인링 방법을 사용하는 것입니다.
3. 해시 맵 소스 코드 분석 (JDK1.7)
1. 해시 맵 요소를 읽고 쓰십시오
기입
해시 맵에 저장된 요소는 입력 유형입니다. 소스 코드의 소스 입력 코드는 다음과 같습니다.
정적 클래스 항목 <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; } // 키의 get and set 메소드, 값은 생략됩니다. 값은 후속 반복자에 사용됩니다 ... 공개 최종 부울 평등 (Object O) {if (! (o instanceof map.entry)) 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를 반환합니다. } // 여기, 여기, 키의 해시 코드와 값 해시 코드를 수행하여 엔트리의 해시 코드를 얻으려면 공개 최종 int hashcode () {return objects.hashcode (getkey ()) ^ objects.hashcode (getValue ()); } public final String toString () {return getKey () + "=" + getValue (); } /** *이 메소드는 항목의 값이 * Hashmap에서 이미 * 인 Key K에 대한 Put (k, v)의 호출에 의해 * 덮어 쓸 때마다 호출됩니다. * / void RecordAccess (Hashmap <k, v> m) {} / ** *이 메소드는 항목이 * 테이블에서 제거 될 때마다 호출됩니다. */ void RecordRemoval (Hashmap <k, v> m) {}}항목에는 키, 값, 해시 및 다음 항목에 대한 참조가 포함됩니다. 이것은 단일 링크 목록으로, 맵. 엔트리 인터페이스를 구현합니다.
recordacess (hashmap <k, v> 및 recordremoval (hashmap <k, v>)은 해시 맵에서 구현되지 않지만 LinkedHashMap의 두 가지 방법은 LRU 알고리즘을 구현하는 데 사용됩니다.
GET : Hashmap에서 해당 항목을 얻으려면 요소를 읽습니다. 다음은 get의 소스 코드입니다.
public v get (Object Key) {// 키가 null 인 상황 (key == null) return getfornullkey (); // 키 입력 항목을 기반으로 항목을 찾으십시오. return null == Entry? NULL : Entry.GetValue (); }getfornullkey 소스 코드
private v getfornullkey () {if (size == 0) {return null; } // (Entry <k, v> e = 테이블 [0]; e! = null; e = e.next) {if (e.key == null) return e.value; } return null; }키 널이있는 입력은 표 [0]에 저장되지만 표 [0]의 충돌 체인이 반드시 널처럼 키를 갖지 않으므로 통과해야합니다.
키에 따라 입력하십시오.
최종 항목 <k, v> getEntry (개체 키) {if (size == 0) {return null; } int hash = (key == null)? 0 : 해시 (키); // 해시를 통해 테이블에서 인덱스 위치를 가져온 다음 충돌하는 링크 목록을 통과하여 (Entry <k, v> e = 테이블 [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; }위는 해시 맵이 항목과 소스 코드를 읽는 프로세스입니다. 시간 복잡성 O (1)
풋 : 쓰기 요소
해시 맵에서의 PUT 작업은 PUT 작업 중에 해시 맵 확장 작업이 있기 때문에 상대적으로 복잡합니다.
새 요소가 작성되면 해시 맵에 요소를 작성하는 키가 있으면 값을 교체하는 작업이 수행됩니다. 이는 업데이트와 동일합니다. 다음은 풋 소스 코드입니다.
public v put (k key, v value) {// 테이블이 비어있는 경우 크기의 임계 값에 따라 if (table == empty_table)를 채우십시오. } // 키로 항목을 NULL로 채우는 경우 (key == null) PUTFORNULLKEY (value)를 반환합니다. // 인덱스 인덱스의 매핑을 얻으려면 해시를 생성합니다 int hash = hash (key); int i = indexfor (Hash, table.length); // 현재 인덱스의 충돌 체인을 전환하여 (Entry <k, v> e = 테이블 [i]; e! = null; e = e.next) {object k; // 해당 키가 존재하는 경우 OldValue를 교체하고 OldValue를 반환합니다. e.Value = 값; e.recordaccess (this); OldValue를 반환하십시오. }} // 새로 쓰여진 항목의 키는 충돌 체인 modcount ++에 존재하지 않습니다. // 새 항목 addentry (해시, 키, 값, i) 삽입; 널 리턴; }Addentry 및 CreateEntry 소스 코드 :
void addentry (int hash, k key, v value, int bucketindex) {// 새 항목을 삽입하기 전에 먼저 현재 해시 맵의 크기와 임계 값 크기를 판단하고 if ((size> = threshold) && (null! = 테이블 [bucketIndex])) {resize (2 * table.length); hash = (null! = 키)? 해시 (키) : 0; BucketIndex = indexfor (Hash, table.length); } createEntry (해시, 키, 값, BucketIndex); } void createEntry (int hash, k key, v value, int buctIndex) {enther <k, v> e = 테이블 [buctIndex]; // 헤드 삽입 방법, 새로 쓰여진 항목이 현재 인덱스 위치에서 충돌 체인의 첫 번째 항목의 전면에 삽입됩니다. 표 [bucetIndex] = new Entry <> (해시, 키, 값, e); 크기 ++; }위는 해시 맵 및 소스 코드에 항목을 작성하는 과정입니다. 시간 복잡성 O (1)
제거 요소 제거 :
최종 항목 <k, v> removeEntryforKey (개체 키) {if (size == 0) {return null; } // 키에 따라 해시 값을 계산하고 인덱스 int hash = (key == null)을 가져옵니다. 0 : 해시 (키); int i = indexfor (Hash, table.length); // 링크 된 목록을 삭제하고, 두 포인터를 정의하고, 사전은 선행 항목 <k, v> prev = table [i]를 나타냅니다. 입력 <k, v> e = 이전; // 충돌 체인을 트랜스 트레이닝하고 모든 키를 삭제합니다. 객체 k; // 발견 된 경우 (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) {modcount ++; 크기--; // 첫 번째 노드를 찾는 것은 (prev == e) 테이블 [i] = 다음에 삭제할 노드입니다. else prev.next = 다음; e.recordremoval (this); 반환 e; } prev = e; e = 다음; } 반환 e; }위는 해시 맵이 항목 및 소스 코드를 삭제하는 프로세스입니다. 시간 복잡성 O (1)
2. 해시 맵 해싱 원리 (해시 함수)
해시 맵에서 해시 함수의 구현은 해시 (객체 k) 및 indexfor (int h, int length)를 통해 수행됩니다. 아래 소스 코드를 살펴 보겠습니다.
최종 int 해시 (객체 k) {int h = 해시드; if (0! = h && k instanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h ^= k.hashcode (); //이 함수는 각 비트 위치에서 // 상수 배수에 의해서만 다른 해시 코드가 결합 된 // 충돌 횟수 (기본 부하 계수에서 약 8)를 갖도록합니다. // 충돌 가능성을 줄이기 위해 h ^ = (h >>> 20) ^ (h >>> 12); h ^ (h >>> 7) ^ (h >>> 4); }인덱스 인덱스 소스 코드 가져 오기 :
static int indexfor (int h, int length) {// assert integer.bitcount (길이) == 1 : "길이는 0이 아닌 2의 전력이어야합니다"; 반환 h & (길이 -1); }해시 맵은 키를 해시 함수를 통해 [0, table.length]의 간격 내에서 인덱스에 매핑합니다. 일반적으로 두 가지 종류의 인덱싱 방법이 있습니다.
해시 (키) % table.length, 여기서 길이는 소수 여야합니다. Hashtable 은이 구현을 JDK에서 사용합니다.
소수를 사용하는 특정 이유는 여기에 언급되지 않을 관련 알고리즘 데이터 증거를 찾을 수 있습니다.
해시 (키) & (테이블 - 길이 -1) 길이가 2 지수 전력에 있어야합니다. JDK의 Hashmap 은이 구현 방법을 사용합니다.
길이의 크기는 지수 시간이 2이기 때문에 해시 (키) & (표 - 길이 -1)는 항상 [0, 길이 -1] 사이입니다. 그러나이 작업만으로도 Java의 해시 코드 값이 32 비트이기 때문에 갈등에 큰 문제가 발생합니다. 예를 들어, 16, XOR 작동을 수행 할 때 16 일 때, HASHMAP의 용량이 작을 때, 높은 비트는 항상 폐기되지만 낮은 비트 조작 후에 충돌 확률이 증가합니다.
따라서 충돌 발생 가능성을 줄이기 위해 많은 비트 운영 및 독점 또는 작업이 코드에서 수행됩니다.
3. 해시 맵 메모리 할당 전략
회원 가변 용량 및로드 액터
필요한 용량 용량은 해시 맵에서 2의 지수 다중이며 기본 용량은 1 << 4 = 16입니다. 해시 맵에는 균형 계수 (loadfactor)도 있습니다. 과도하게 높은 요인은 저장 공간을 줄일 수 있지만 검색 시간 (해시 맵의 Put and Get Methods를 포함한 조회)이 증가합니다. LoadFactor의 기본값은 0.75이며, 이는 시간 복잡성 및 공간 복잡성을 측정하여 주어진 최적의 값입니다.
정적 최종 int default_initial_capacity = 1 << 4; // 일명 16 정적 최종 int maximum_capacity = 1 << 30; 정적 최종 플로트 default_load_factor = 0.75f;
해시 맵 생성기
해시 맵의 구성은 용량과 loadfactor의 초기 값을 설정하는 것입니다.
public hashmap (int initialcapacity, float loadfactor) {if (initialcapacity <0) 새로운 불법 불법 행위 ( "불법 초기 용량 :" + initialcapacity); if (InitialCapacity> maximum_capacity) 초기 커피 = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) 새로운 불법 불법 행위 ( "불법 하중 계수 :" + loadfactor); this.loadfactor = loadfactor; 임계 값 = 초기 용량; init (); } 해시 맵의 그 용량 앞에는 2의 지수 시간이어야하며 생성자에는 제한이 없다고 말했습니다. 그렇다면 용량 값이 기하 급수 시간 2의 기하 급수 시간을 보장하는 방법은 무엇입니까?
PUT 작업 중에 소스 코드는 현재 해시 테이블이 빈 테이블인지 여부를 결정합니다. 그렇다면 inflatetable (int tosize)을 호출하십시오.
private void inflatetable (int tosize) {// 2> = tosize int capacity = rounduptopowerof2 (tosize)의 전력 찾기; 임계 값 = (int) math.min (용량 * loadfactor, maximum_capacity + 1); 표 = 새로운 항목 [용량]; inithashseedasneded (용량); }Rounduptopowerof2는 주어진 매개 변수보다 더 큰 N 전력을 얻는 경우
개인 정적 int rounduptopowerof2 (int number) {// assert number> = 0 : "숫자는 무분별이어야합니다"; 반환 번호> = maximum_capacity? maximum_capacity : (번호> 1)? integer.highestonebit ((번호 -1) << 1) : 1; }integer.hightestonebit (int)은 주어진 매개 변수의 최고 비트를 유지하고 나머지 0을 변경하는 작업입니다.
숫자가 2 인 경우, 가장 높은 비트는 감소 1 후 원래 두 번째 높은 비트에 있고, 1 비트를 좌회전하여 여전히 가장 높은 비트 위치에 위치합니다. 숫자가 2의 N 전력이 아닌 경우, 가장 높은 비트는 1 비트가 1 비트를 남겨두기 위해 1 비트가 남은 후에도 여전히 가장 높은 비트입니다.
용량 확장 :
해시 맵은 풋 작동시 크기 조정 동작을 갖습니다. 특정 소스 코드는 다음과 같습니다.
void resize (int newCapacity) {entry [] oldtable = table; int oldcapacity = oldtable.length; // 해시 테이블이 최대 용량에 도달했습니다. 반품; } entry [] newtable = 새로운 항목 [newCapacity]; // OldTable의 항목을 NewTable로 옮깁니다. // inithashseedasneed의 반환 값은 해시 값 전송 (newtable, inithashseedasneeded (newcapacity))를 다시 계산할지 여부를 결정합니다. 테이블 = Newtable; // 임계 값 재 계산 임계 값 = (int) math.min (newCapacity * loadfactor, maximum_capacity + 1); } void arrantial (Entry [] NewTable, 부울 리해시) {int newCapacity = newtable.length; // transweep OldTable for (entry <k, v> e : table) {// transweep 충돌 체인 while (null! = e) {Entry <k, v> next = e.next; if (rashash) {// 해시 값을 다시 계산하십시오. e.hash = null == E.key? 0 : 해시 (e.key); } int i = indexfor (e.hash, newCapacity); // 요소를 헤드에 삽입, 헤더 삽입 방법 E.Next = newtable [i]; newtable [i] = e; e = 다음; }}}위는 해시 맵 메모리 할당의 전체 프로세스입니다. 요약하면, Hashmap이 항목을 입력하면 현재 용량과 임계 값 크기를 확인하여 용량을 확장할지 여부를 선택합니다. 각 확장의 크기는 2 * table.length입니다. 확장 기간 동안, 해시 값이 inithashseedasned에 따라 재 계산 해야하는지 여부를 결정합니다.
4. 해시 맵 반복자
Hashmap의 ValueIterator, Keyiterator, Enthreiterator 및 기타 반복자는 모두 해시 테이터를 기반으로합니다. 소스 코드를 살펴 보겠습니다.
개인 초록 클래스 해시 테이터 <e>는 반복자 <e> {Entry <k, v> 다음; // 다음 항목을 반환 할 int exclingModCount; // 빠른짜리 int 인덱스; // 현재 슬롯, 테이블 인덱스 항목 <k, v> current; // 현재 항목 hashiterator () {expostModCount = modCount; // 해시 테이블에서 첫 번째 항목을 찾으십시오. while (index <t.length && (다음 = t [index ++]) == null); }} public final boolean hasnext () {return next! = null; } 최종 항목 <k, v> nextEntry () {// 해시 맵은 비 스레드-안전이며, 가로 지르면 (modcount! = excliteModCount) 새로운 동의 mocurrentModificationException ()을 던지는 경우 테이블 구조의 수정이 있는지 여부를 여전히 결정합니다. 입력 <k, v> e = 다음; if (e == null) 새로운 nosuchelementException ()을 던지십시오. if ((다음 = e.next) == null) {// 다음 항목을 찾으십시오 [] t = table; while (index <t.length && (다음 = t [index ++]) == null); } current = e; 반환 e; } public void remove remove () {if (current == null) 던지기 새로운 불법 스테이트 exception (); if (modCount! = excliteModCount) 버리 새로운 동시에 mododificationException (); 객체 k = current.key; current = null; hashmap.this.removeentryforkey (k); 예상 modCount = modCount; }}키, 값 및 항목의 세 가지 반복자는 캡슐화되어 키 세트, 값 및 항목 세트의 세 가지 수집 관점이됩니다. 이 세 가지 수집 관점은 해시 맵의 제거, removeall 및 명확한 작업을 지원하며 Add 및 Addall 작업을 지원하지 않습니다.