Hashmap은 해시 테이블을 기반으로 한 맵 인터페이스 구현으로 모든 옵션 매핑 작업을 제공하고 널 값과 널 구성, 동기화 및 매핑 순서를 보장 할 수 없습니다. 해시 맵의 구현 원리를 기록해 봅시다.
해시 맵 내부 저장소
해시 맵에서 모든 키 값 쌍 관계는 순간 변수 테이블 (버킷이라고도 함)을 유지하여 저장됩니다. 버킷은 입구 객체 배열입니다. 버킷 크기는 필요에 따라 크기를 조정할 수 있으며 길이는 2의 전력이어야합니다. 다음 코드 :
/ *** 빈 입력 배열, 버킷의 기본값*/ 정적 최종 항목 <?,?> [] empty_table = {}; / *** 버킷, 필요에 따라 크기를 조정하지만 2*/ Transient Entry <k, v> [] table = (Entry <k, v> []) empty_table;초기 용량 및 하중 계수
Hashmap에는 성능, 초기 용량 및로드 계수에 영향을 미치는 두 가지 매개 변수가 있습니다. 용량은 해시 테이블의 버킷 수이고, 초기 용량은 해시 테이블이 생성 될 때 해시 테이블의 용량 일 뿐이며, 하중 계수는 용량이 자동으로 증가하기 전에 해시 테이블이 가득 찬 방법에 도달 할 수있는 스케일입니다. 해시 테이블의 항목 수가 하중 계수의 제품을 초과하고 현재 용량을 초과하면 해시 테이블을 다시 해쉬해야하며 (즉, 내부 데이터 구조를 재건), 재구성은 현재 용량의 두 배로 생성됩니다. 초기 용량 및 하중 계수는 생성자를 통해 설정할 수 있습니다. 기본 초기 용량은 16 개의 항목이고 최대 용량은 2^30 항목이며 기본 부하 계수는 0.75입니다.
양동이는 물을 저장하는 양동이와 같습니다. 기본 초기 저장 용량은 16 단위의 물입니다. 물이 16*0.75로 쏟아지면 다음에 데이터가 추가되면 용량이 먼저 32 단위로 확장됩니다. 0.75는 부하 계수이며 버킷을 만들 때 초기 용량 및 하중 계수를 설정할 수 있습니다. 버킷의 최대 용량은 2 단위의 물에서 30의 전력입니다. 초기 용량 설정의 수가 최대 용량보다 큰 경우 최대 용량이 우선합니다. 확장시 최대 용량보다 크거나 동일하면 직접 반환됩니다.
다음은 기본 초기 용량, 하중 계수 및 기타 상수를 정의하는 해시 맵의 소스 코드의 일부입니다.
/ ** * 기본 초기 용량은 2의 전력이어야합니다. */ 정적 최종 int default_initial_capacity = 1 << 4; // 일명 16/ *** 최대 용량, 초기 용량이 생성자 매개 변수를 통한 최대 용량보다 큰 경우, 용량은 초기 용량*이 2의 전력이어야하며 2*/ 정적 최종 int maximum_capacity = 1 << 30; / *** 기본 부하 계수는 생성자*/ 정적 최종 플로트 Default_load_factor = 0.75f에 의해 지정할 수 있습니다. / *** 버킷이 초기화되지 않은 경우 빈 배열 테이블*/ 정적 최종 항목 <?,?> [] empty_table = {}; / *** 버킷, 모든 키-값 쌍 항목을 저장하고 필요에 따라 크기를 조정할 수 있으며 길이는 2*/ transient entry <k, v> [] table = (enther <k, v> []) empty_table; /*** 맵의 키 값 쌍의 수는 추가되거나 삭제 될 때마다 크기가 +1 또는 -1 작업입니다. */ 과도 int 크기; /** * 크기를 조정 해야하는 부하 값의 임계 값은 다음과 같습니다. (용량 * 부하 계수). 각 크기 조정 후 새로운 용량은 새로운 용량을 사용하여 계산됩니다. * @serial */ // table == empty_table이면 팽창시 // 테이블이 생성되는 초기 용량입니다. int 임계 값; / ** * 부하 계수는 생성자에 지정되지 않으면 기본 부하 계수가 사용됩니다. * * @Serial */ Final Float Loadfactor; /** * 해시 맵 구조 수정 횟수, 해시 맵의 맵 수를 변경하거나 구조가 수정 될 때 내부 구조를 수정하십시오 (예 : * rehash 메소드, 내부 데이터 구조를 재건). 이 필드는 * 해시 맵 컬렉션 뷰에서 생성 된 반복자에 사용됩니다.초기 용량 및 하중 계수 성능 조정
일반적으로 기본 부하 계수 (0.75)는 시간 및 공간 비용의 타협을 추구합니다. 로드 계수가 너무 높지만 쿼리 비용도 증가합니다 (GET 및 PUT 작업을 포함하여 대부분의 해시 맵 작업에 반영됩니다). 초기 용량을 설정할 때 리해시 작업 수를 최소화하기 위해 맵에 필요한 항목 수와 하중 계수를 고려해야합니다. 초기 용량이 하중 계수로 나눈 최대 항목 수보다 큰 경우, 재사용 작업은 발생하지 않습니다.
많은 매핑 관계가 해시 맵 인스턴스에 저장되는 경우, 초기 용량이 충분히 큰 경우에이를 생성하면 테이블의 용량을 높이기 위해 주문형 자동 재활 작업을 수행하는 것보다 매핑 관계가 더 효율적으로 저장됩니다.
다음은 해시 맵 데이터 구조를 재건하는 코드입니다.
void resize (int newCapacity) {entry [] oldtable = table; int oldcapacity = oldtable.length; if (OldCapacity == maximum_capacity) {// 용량이 최대 한계에 도달 한 경우로드 값을 설정하고 임계 값 = integer.max_value로 직접 돌아갑니다. 반품; } // 데이터 입력을 저장할 새 테이블을 만듭니다 [] newTable = new entry [newCapacity]; // 이전 테이블에서 새 테이블로 데이터를 전송하면이 단계는 전송에 많은 시간이 걸립니다 (NewTable, inithashseedasneeded (newCapacity)); 테이블 = Newtable; // 마지막으로 다음 크기 조정 임계 값의로드 값을 설정합니다. (int) math.min (newCapacity * loadfactor, maximum_capacity + 1);}해시 맵 구조 방법
네 번째 구성 방법은 기존지도가있는 새 해시 맵을 만드는 것입니다. 나중에 그것에 대해 이야기합시다. 실제로, 처음 세 가지 시공 방법은 두 개의 매개 변수로 최종 세 번째 방법에서 호출됩니다. 매개 변수가 전달되지 않으면 기본값이 사용됩니다. 코드는 다음과 같습니다.
/** * 기본 초기 용량 * (16) 및 기본 부하 계수 (0.75)와 함께 빈 <TT> HASHMAP </tt>을 구성합니다. */ public hashmap () {this (default_initial_capacity, default_load_factor); } /** * 지정된 초기 * 용량 및 기본 부하 계수 (0.75)를 사용하여 빈 <tt> hashmap < /tt>를 구성합니다. * * * @param 초기 용량 초기 용량. * 초기 용량이 음수 인 경우 @throws 불법 행위 예고. */ public hashmap (int initialcapacity) {this (initialcapacity, default_load_factor); } /** * 지정된 초기 * 용량 및 하중 계수를 사용하여 빈 <tt> hashmap < /tt>를 구성합니다. * * @param 초기 범위 초기 용량 * @param loadfactor 부하 계수 * @throws 불법적 인 용량이 음수 인 경우 * 또는 부하 계수가 비 포지티브 */ public hashmap (int initialcapacity, float loadfactor) {if (초기 커피 <0) 던지기 초기 용량 : "불법 초기 용량 :"; if (InitialCapacity> maximum_capacity) 초기 커피 = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) 새로운 불법 불법 행위 ( "불법 하중 계수 :" +loadfactor); this.loadfactor = loadfactor; 임계 값 = 초기 용량; init (); }위에서 볼 수 있듯이 생성자에서 초기 용량이 최대 용량보다 큰 경우 최대 용량은 직접 교체됩니다.
방법을 넣으십시오
다음으로 해시 맵의 더 중요한 부분을 살펴 보겠습니다.
/***이 맵에서 지정된 값과 지정된 빌드가 연결되어 있습니다. 이전에 키의 매핑 관계가 포함 된 경우 이전 값이 대체됩니다.* @param* @param과 연관 될 값을 지정* @param 키와 관련된 이전 값을 지정합니다. 키와 관련된 기존 값을 지정합니다. 키에 매핑 관계가없는 경우 널을 반환합니다. 풍부한 (임계 값); } 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); 널 리턴; }1. 첫째, 풋 방법에서 먼저 버킷이 기본 비 초기 상태에 있는지 여부를 결정합니다. 초기화되지 않은 경우 풍선 용 메소드를 호출하여 초기화 한 다음 매개 변수 키가 NULL인지 확인하십시오. NULL 인 경우 PUTFORNULLKEY에 특별히 KEY를 NULL로 넣으십시오. Putfornullkey 메소드는 실제로 NULL이라는 KEY를 가진 데이터의 기본 저장 위치가 첫 번째, 즉 기본 첨자가 0이라는 점을 제외하고는 다음 3 단계와 동일합니다.
2. 키가 NULL이 아닌 경우 HASH () 메소드를 호출하여 키의 해시 값을 얻으십시오. 해시 값과 버킷의 길이에 따라 키를 버킷에 배치 할 수있는 위치를 계산할 수 있습니다.
3. 항목 객체에는 다음 해시 값을 가진 요소를 저장하기위한 일방 통행 링크 목록을 형성 할 수있는 속성이 있습니다. 따라서 키의 해시 값이 계산되면 저장 위치도 반복됩니다. 스토리지 위치의 요소와 요소의 다음 속성 목록이 주어진 키 및 키의 해시 값과 정확히 동일한 지 판단하십시오. 완전히 일관된 것이 있다면 이미 존재한다는 것을 의미합니다. 이전 값을 교체하고 이전 값을 반환 값으로 직접 반환합니다.
4. 구조 수정 수를 1 씩 증가시킵니다
5. Addentry 메소드를 호출하여 새 키 값 쌍을 해시 맵에 추가하십시오. Addentity 메소드는 먼저 현재 입력 데이터가 하중 값 (버킷 * 하중 계수의 용량)과 얼마나 크든 동일하고 버킷의 지정된 위치가 무효가되지 않는지 결정합니다. 이미보다 크고 지정된 위치가 NULL이 아닌 경우 조정 버킷의 용량은 전류 용량의 두 배입니다. 조정 버킷의 용량은 위의 초기 용량 및 하중 계수 성능 조정 디렉토리를 참조합니다. 해시 값을 다시 계산하고 저장 위치를 계산하십시오. CreateEntry 메서드를 호출하여 버킷에 저장하십시오
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 (해시, 키, 값, BucketIndex); } void createEntry (int hash, k key, v value, int buctIndex) {enther <k, v> e = 테이블 [buctIndex]; 표 [bucetIndex] = new Entry <> (해시, 키, 값, e); 크기 ++; } /*** 입력 생성자 메소드 새 항목을 생성합니다. */ Entry (int h, k k, v v, enter <k, v> n) {value = v; 다음 = n; 키 = k; 해시 = h; }6. CreateEntry 메소드에서 먼저 지정된 위치에서 항목을 가져온 다음 새 항목을 생성합니다. 항목을 생성 할 때 원래 항목을 새로 생성 된 항목의 다음 속성에 저장하고 (입력 구성 방법 참조) 지정된 위치의 항목을 새로 생성 된 위치로 교체하십시오.
새 항목을 추가 할 때 해시 값을 계산해야하고 길이가 충분하지 않으면 길이를 조정해야합니다. 계산 된 저장소 위치에 요소가 있으면 연결된 목록을 저장해야하므로 해시 맵을 사용하여 새 작업을 추가하는 효율이 너무 높지 않습니다.
방법을 얻으십시오
먼저 Get 메소드의 소스 코드를 살펴 보겠습니다.
/*** 지정된 키로 매핑 된 값을 반환합니다. 이 맵 이이 키에 대한 매핑 관계가 포함되어 있지 않으면 NULL을 반환하면 NULL 값을 반환하면 맵에 키의 매핑이 포함되어 있지 않으며 매핑을 NULL로 변경할 수도 있습니다. 이 두 가지 상황을 구별하기 위해 포함 된 키 작업을 사용하여 * @see #put (Object, Object) */ public v get (개체 키) {if (key == null) return getFornUllKey (); Entry <k, v> entry = getentry (키); return null == Entry? NULL : Entry.GetValue (); } 최종 항목 <k, v> getEntry (개체 키) {if (size == 0) {return null; } 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;}Get 메소드는 구현하기가 간단하고 다음은 몇 단계입니다.
Get의 소스 코드를 살펴보면 Get 메소드가 키의 해시 값과 버킷의 길이를 통해 스토리지 위치를 계산한다는 것을 알 수 있습니다. 기본적으로 원하는 요소를 찾을 수 있습니다. 반복 된 해시 값으로 몇 개의 키를 가로 지르더라도 매우 빠릅니다. 해시 값은 비교적 고유하기 때문에 해시 맵은 검색에 매우 빠릅니다.
해시 맵의 키로 사용자 정의 객체
클래스 사용자 {// id 번호 보호 int idnumber; 공개 사용자 (int id) {idnumber = id; }} public class testuser {public static void main (String [] args) {map <User, String> map = new Hashmap <User, String> (); for (int i = 0; i <5; i ++) {map.put (새 사용자 (i), "이름 :"+i); } system.out.println ( "user3의 이름 :" + map.get (새 사용자 (3)); }} 출력 : user3 이름 : null위에서 언급 한 바와 같이, 사용자 정의 사용자 클래스 인스턴스를 해시 맵 객체로 사용할 때는 사용자 클래스가 기본 클래스 객체를 자동으로 상속하기 때문에 인쇄 할 때 사용자 3의 이름을 찾을 수 없으므로 해시 코드 메소드는 자동으로 해시 값을 생성하는 데 사용되며 객체의 주소를 사용하여 기본적으로 해당 값을 계산합니다. 따라서 새 사용자 (3)에 의해 생성 된 첫 번째 인스턴스의 해시 값은 생성 된 두 번째 인스턴스의 해시 값과 다릅니다. 그러나 해시 코드 메소드를 간단히 무시하면되면 동시에 Equals 메소드를 재정의하지 않는 한 제대로 작동하지 않으면 객체의 일부이기도합니다. Hashmap은 equals ()를 사용하여 현재 키가 테이블에있는 키와 동일한 지 여부를 결정합니다. 위의 get 또는 put 방법을 참조 할 수 있습니다.
올바른 평등 () 메소드는 다음 5 가지 조건을 충족해야합니다. --- "Java 프로그래밍 생각" -489 페이지 참조
다시 : 기본 OBJECT.Equals ()는 비교 객체의 주소 일 뿐이므로 하나의 새 사용자 (3)은 다른 새 사용자 (3)와 같지 않습니다. 따라서 자신의 클래스를 해시 맵의 키로 사용하려면 hashcode ()와 equals ()를 모두 과부하해야합니다.
다음 코드는 정상적으로 작동합니다.
클래스 사용자 {// id 번호 보호 int idnumber; 공개 사용자 (int id) {idnumber = id; } @override public int ashcode () {return idnumber; } @override public boolean equals (object obj) {return obj instance user && (idnumber == ((사용자) obj) .idnumber); }} public class testuser {public static void main (String [] args) {map <User, String> map = new Hashmap <User, String> (); for (int i = 0; i <5; i ++) {map.put (새 사용자 (i), "이름 :"+i); } system.out.println ( "user3의 이름 :" + map.get (새 사용자 (3)); }} 출력 : user3의 이름 : 이름 : 3위의 내용은 단순히 Idnumber를 해시 코드의 유일한 차별으로 반환하며 사용자는 자신의 사업에 따라 자체 방법을 구현할 수 있습니다. Equals 메소드에서 인스턴스는 객체가 무효인지 조용히 확인합니다. 인스턴스의 왼쪽에있는 매개 변수가 null이면 false가 반환됩니다. equals ()의 매개 변수가 null이 아니고 유형이 올바른 경우 비교는 각 객체의 실제 idnumber를 기반으로합니다. 출력에서 볼 수 있듯이 현재 방법이 정확합니다.
참조 :
"자바 프로그래밍 생각"
JDK 1.6 중국어 도움말 매뉴얼
위는이 기사의 모든 내용입니다. 이 기사의 내용이 모든 사람의 연구 나 업무에 도움이되기를 바랍니다. 또한 wulin.com을 더 지원하기를 바랍니다!