- 하쉬 맵 -
장점 : O (1) 시간 복잡성에 도달 할 수있는 매우 빠른 쿼리 속도 및 데이터 구조는 해시 맵입니다. 동적 변수 길이 저장 데이터 (어레이에 비해).
단점 : 해시 값은 추가로 계산되어야하며, 제대로 처리되지 않으면 추가 공간이 필요합니다.
- 해시 맵을 사용하는 방법 -
일반적으로 우리는 다음과 같이 해시 맵을 사용합니다
Map <Integer, String> Maps = New Hashmap <Integer, String> (); maps.put (1, "a"); maps.put (2, "b");
위의 코드는 새 해시 맵을 생성하고 두 개의 데이터를 삽입합니다. 기본 데이터 유형은 여기서 K 및 V를 수행하기 위해 여기에서 허용되지 않습니다.
이 글을 쓰면 문제가 있습니다.
Map <int, double> maps = new Hashmap <int, double> ();
우리는 왜 이런 식으로 사용합니까? 소스 코드를 참조하십시오 :
공개 클래스 해시 맵 <k, v> 확장 actractmap <k, v> 구현 <k, v>, 클로닝 가능, 직렬화 가능
이것이 해시 맵 구현 클래스의 정의입니다.
-하쉬 맵은 동적으로 가변 길이의 데이터 구조입니다.
Hashmap을 사용하는 경우 실행 효율성을 향상시키기 위해 종종 해시 맵 초기화 용량을 설정합니다.
Map <String, String> rm = new Hashmap <String, String> (2)
또는 Guava의 도구 클래스 맵을 사용하여 수집을 쉽게 만들고 적절한 크기로 값을 초기화하십시오.
map <string, object> map = maps.newhashmapwithexpectedSize (7);
그렇다면 왜 이렇게 사용합니까? 소스 생성자를 살펴 보겠습니다.
매개 변수가없는 생성자 :
public hashmap () {this.loadfactor = default_load_factor; 임계 값 = (int) (default_initial_capacity * default_load_factor); 테이블 = 새 항목 [default_initial_capacity]; init (); } public hashmap () {
this.loadfactor = default_load_factor;
임계 값 = (int) (default_initial_capacity * default_load_factor);
테이블 = 새 항목 [default_initial_capacity];
init ();
}
/** * 지정된 초기 * 용량 및 기본 부하 계수 (0.75)를 사용하여 빈 <TT> HASHMAP </tt>을 구성합니다. * * * @param 초기 용량 초기 용량. * 초기 용량이 음수 인 경우 @throws 불법 행위 예고. */ public hashmap (int initialcapacity) {this (initialcapacity, default_load_factor); }명사에 대한 설명 :
default_load_fackor // 기본로드 계수, 지정되지 않은 경우 0.75. default_initial_capacity // 기본 초기화 용량, 기본값은 16 임계 값입니다. // 임계 값 (YU) 값은로드 계수 및 초기화 용량에 따라 계산됩니다. <span style = "color : rgb (54, 46, 43); Font-Family :"Microsoft Yahei ";"> 임계 값은 해시 맵의 크기가 임계 값보다 클 때 크기 조정 작업이 수행됨을 의미합니다.
따라서 우리는 매개 변수가없는 생성자를 호출하면 16 용량의 배열을 얻을 것임을 알고 있습니다.
따라서 문제는 다음과 같습니다. 초기 용량이 충분하지 않으면 어떻게됩니까?
어레이는 고정 길이이며, 고정 길이 데이터를 사용하여 불확실한 길이 데이터를 나타내는 방법은 무엇입니까? 대답은 더 긴 것을 찾는 것이지만 크기가 크면 효율성이 줄어 듭니다. 따라서 초기화 할 때 해시 맵에 신뢰할 수있는 용량을 제공하는 것이 좋습니다.
- hashmap put 방법 -
public v put (k key, v value) {if (key == null) // 키가 비어 있으면 해시 맵과 해시 가능 반환 풋 푸른 룰키 (value)의 차이; int hash = hash (key.hashcode ()); // 키 int i = indexfor (hash, table.length)의 해시 코드를 기반으로 해시 값을 프레임합니다. // (Entry <k, v> e = 테이블 [i]; e! = null; e = e.next)에 대한 해시 값을 기준으로 배열 위트 스크립트를 프레임으로 프레임하십시오. {// 루프의 전체가 k가 존재하는 경우 v object k를 교체합니다. if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v OldValue = e.Value; e.Value = 값; e.recordaccess (this); OldValue를 반환하십시오. }} modcount ++; // Counter Addentry (해시, 키, 값, i); // 배열 return null에 추가; }삽입 된 데이터가 기존 용량을 초과하면 실행됩니다.
Addentry (해시, 키, 값, i);
void addentry (int Hash, K Key, V value, int buctIndex) {Entry <k, v> e = 테이블 [buctIndex]; 표 [BuctIndex] = 새 항목 <k, v> (해시, 키, 값, e); if (size ++> = threshold) <span style = "color :#ff0000;"> <strong> resize (2 * table.length);}여기에서 현재 크기 ++> 임계 값이 표시되면 현재 크기가 두 번 확장되고 크기 조정 (2*table.length)이 실행됩니다. 그래서 그들은 어떻게 확장합니까?
void resize (int newCapacity) {entry [] oldtable = table; int oldcapacity = oldtable.length; if (OldCapacity == maximum_capacity) {threshold = integer.max_value; 반품; } entry [] newtable = 새로운 항목 [newCapacity]; <span style = "color : rgb (51, 51, 51); font-family : arial;"> 새로운 배열, </span> <strong> <span style = "color :#ff0000;"> 송금 (newtable); </span> </span> // 배열을 새 배열 테이블로 전송합니다. 임계 값 = (int) (newCapacity * loadFactor); // 용량 재 계산}전송 배열 전송은 어떻게 전송됩니까?
무효 전송 (entry [] newtable) {entry [] src = 테이블; int newcapacity = newtable.length; for (int j = 0; if (e! = null) {src [j] = null; do {Entry <k, v> next = e.next; int i = <strong> <span style = "color :#ff0000;"> indexfor (e.hash, newCapacity); // 해시 용량에 따라 인덱스를 다시 계산합니다. </span> </strong> e.next = newtable [i]; newtable [i] = e; e = 다음; } while (e! = null); }}}- 해시 맵 확장의 추가 실행 수
따라서 1000 요소의 해시 맵을 추가하려면 기본값을 사용하는 경우 몇 개의 추가 계산이 계산해야합니까?
16*0.75 = 12보다 큰 경우 12 번 재 계산해야합니다.
16*2*0.75 = 24보다 큰 경우 추가 24 개의 계산이 필요합니다.
...
16*n*0.75 = 768보다 큰 경우 추가 768 계산이 필요합니다.
따라서 확장 프로세스에서 12+24+48+…+768 배를 계산했습니다
따라서 프로젝트의 범위를 다음과 같이 알고 있다면 초기 크기를 수동으로 지정해야합니다.
Map <Integer, String> Maps = New Hashmap <Integer, String> (1000);
요약 : 사용 중 초기 용량을 초과하면 해시 맵의 실행 효율이 심각하게 감소하는 이유입니다.
위의 것은 Java 소스 코드 분석에 관한이 기사에서 해시 맵의 사용에 관한 것입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!