그것을 표시하고 동시에 Hashcode () 및 Equals () 메소드를 잘 결합하여 Equals의 두 객체가 동일한 해시 코드를 갖도록하는 것이 가장 좋습니다. hashcode ()는 동일하지 않으며, hashcode ()를 추론 할 수 있어야합니다.
Hashmap이 얻을 때 먼저 해시 코드를 비교 한 다음 equals, hashcode == && equals를 비교하기 때문에 둘 다 사실이므로 동일한 키로 간주됩니다.
1. 해시 맵 개요 :
Hashmap은 해시 테이블을 기반으로 한 맵 인터페이스의 비동기 구현입니다. 이 구현은 모든 옵션 매핑 작업을 제공하며 NULL 값 및 NULL 키를 사용할 수 있습니다. 이 클래스는 매핑의 순서를 보장하지 않습니다. 특히 주문이 지속될 것이라고 보장하지는 않습니다.
2. Hashmap의 데이터 구조 :
Java 프로그래밍 언어에는 두 가지 기본 구조가 있으며, 하나는 배열이고 다른 하나는 시뮬레이션 된 포인터 (참조)입니다. Hashmap은 실제로 "링크 된 목록 해시"데이터 구조, 즉 배열과 링크 된 목록의 조합입니다.
위 그림에서 볼 수 있듯이 해시 맵의 기본 레이어는 배열 구조이며 배열의 각 항목은 또 다른 링크 된 목록입니다. 새 해시 맵이 만들어지면 배열이 초기화됩니다.
소스 코드는 다음과 같습니다.
/ ** * 테이블은 항상 2의 전력이어야합니다. v 값;
항목은 배열의 요소라는 것을 알 수 있습니다.
3. 해시 맵 액세스 구현 :
1) 저장 :
public v put (k key, v value) {// hashmap은 널 키와 널 값을 허용합니다. // 키가 null이면 putfornullkey 메소드를 호출하고 값을 배열의 첫 번째 위치에 놓습니다. if (key == null) return putfornullkey (value); int hash = hash (key.hashcode ()); int i = indexfor (Hash, table.length); // I Index의 항목이 NULL이 아닌 경우 루프를 통해 E 요소의 다음 요소를 계속 통과하십시오. for (Entry <k, v> e = 테이블 [i]; e! = null; e = e.next) {객체 k; || key. 이것은 아직 출품작이 없다는 것입니다. modcount ++ // i index에 키와 값을 추가합니다. addentry (해시, 값, i); 위의 소스 코드에서, 우리는 요소를 해시 맵에 넣을 때, 먼저 키의 해시 코드에 따라 해시 값을 다시 계산하고 해시 값에 따라 배열 의이 요소의 위치 (예 : 첨자 첨자. ), 배열이있는 경우 위치에 이미 저장된 다른 요소가 있으므로이 위치의 요소는 링크 된 목록의 형태로 저장되며 새로 추가 된 목록은 체인의 헤드에 배치되고 첫 번째 추가 된 목록이 있습니다. 하나는 체인 끝에 배치됩니다. 배열 에이 위치에 요소가 없으면 배열 의이 위치에 요소를 직접 넣으십시오.
Addentry (해시, 키, 값, i) 메소드는 계산 된 해시 값을 기반으로 배열 테이블의 I 인덱스에 키 값 쌍을 배치합니다. Addentry는 Hashmap에서 제공하는 패키지 액세스 권한 방법입니다. 코드는 다음과 같습니다.
void addentry (int Hash, k key, v value, int buctIndex) {// 지정된 BucketIndex 인덱스 항목 <k, v> e = table [bucetIndex]; 원래 입력 테이블에 새로운 진입 지점을 지정하고 새로운 입력 <k, v> (hash, key, value, e); (size ++> = 임계 값) // 테이블 객체의 길이를 원본의 두 배로 늘립니다. 크기 (2 * 테이블); 시스템이 키 값 쌍을 해시 맵에 저장하기로 결정하면 항목의 값이 전혀 고려되지 않으며 단순히 키를 기반으로 각 항목의 저장 위치를 계산하고 결정합니다. 맵 컬렉션의 값을 키에 대한 첨부 파일로 완전히 처리 할 수 있습니다.
해시 (int h) 메소드는 키의 해시 코드에 따라 해시를 다시 계산합니다. 이 알고리즘은 높은 비트 계산을 추가하여 낮은 비트가 변경되지 않은 상태에서 발생하고 비트가 변경 될 때 해시 충돌이 발생합니다.
정적 int 해시 (int h) {h ^ = (h >>> 20) ^ (h >>> 12); 해시 맵에서 요소를 찾으려면 키의 해시 값을 기반으로 배열에서 해당 위치를 찾아야한다는 것을 알 수 있습니다. 이 위치를 계산하는 방법은 해시 알고리즘입니다. 앞에서 언급했듯이 해시 맵의 데이터 구조는 배열과 링크 된 목록의 조합 이므로이 해시 맵의 요소 위치가 가능한 한 고르게 분산되어 각 위치의 요소 수만 그런 다음 해시 알고리즘을 사용 하여이 위치를 사용할 때 찾을 때 해당 위치의 요소가 우리가 원하는 것임을 즉시 알 수 있으며 더 이상 링크 된 목록을 가로 질러옵니다. 쿼리의 효율성.
주어진 객체의 경우 해시 코드 () 리턴 값이 동일하다면, 해시 (int h) 메소드를 호출하는 프로그램에 의해 계산 된 해시 코드 값은 항상 동일합니다. 우리가 가장 먼저 생각하는 것은 해시 값을 배열 길이로 모듈화하여 요소의 분포가 비교적 균일하다는 것입니다. 그러나 "Modulo"작업은 많은 소비를 소비하며 이는 Hashmap에서 수행됩니다. indexfor (int h, int length) 메서드를 호출하여 테이블 배열에 저장 해야하는 인덱스를 계산하십시오.
indexfor (int h, int length) 메소드의 코드는 다음과 같습니다.
static int indexfor (int h, int length) {return h & (longth-1);이 방법은 매우 영리합니다. H & (테이블 -1)를 통해 객체의 저장된 비트를 얻습니다. 속도 조건. 해시 맵 생성자에는 다음과 같은 코드가 있습니다.
int 용량 = 1; while (용량 <초기 범위) 용량 << = 1;
이 코드는 해시 맵의 용량이 항상 초기화 중, 즉 기본 배열의 길이가 항상 2의 N 전력에임을 보장합니다.
길이가 항상 2의 N 전력에있을 때, H & (길이 -1) 조작은 모듈로 길이, 즉 H %길이와 동일하지만 %보다 효율이 높다.
이것은 매우 간단 해 보이지만 실제로는 매우 신비 롭습니다.
배열 길이가 15 및 16이고 최적화 된 해시 코드가 각각 8 및 9라고 가정하면, 그리고 작업 후 결과는 다음과 같습니다.
H & (테이블 -Length-1) 해시 테이블 .length-1
8 & (15-1) : 0100 & 1110 = 0100
9 & (15-1) : 0101 & 1110 = 0100
--------------------------------------------------------- --------------------------------------------------------- --------------------------------------------------- --------------------------------------------------------- --------------------------------------------------------- ------------------------------------------------- --------------------------------------------------------- --------------------------------------------------------- --------------------------------------------------------- --------------------------------------------------------- ------------
8 & (16-1) : 0100 & 1111 = 0100
9 & (16-1) : 0101 & 1111 = 0101
위의 예에서 볼 수 있듯이 : 15-1 (1110)로 "AS"에있을 때 동일한 결과가 생성됩니다. 즉, 배열의 동일한 위치에 위치하여 충돌, 8 그리고 9는 링크 된 목록을 형성하기 위해 배열에서 동일한 위치에 배치되며 링크 된 목록을 8 또는 9를 얻으려면 쿼리의 효율성이 줄어 듭니다. 동시에 배열 길이가 15 일 때 해시 값은 15-1 (1110)로 "AS"가되면 마지막 비트는 항상 0, 0001, 0011, 0101, 1001이라는 것을 알 수 있습니다. , 1011, 0111, 0111, 1101은 절대 요소를 저장할 수 없으며 공간이 많이 낭비됩니다.이 경우 배열이 사용할 수있는 위치는 배열의 길이보다 훨씬 작습니다. 충돌 가능성이 더 높아지고 쿼리 효율이 느립니다! 배열 길이가 16 인 경우, 즉, 2의 N 전력에있을 때, 2N-1에 의해 얻은 이진수의 각 비트의 값은 1이므로 원래 해시의 합의 낮은 비트를 만듭니다. 획득 된 합계의 낮은 비트가 동일하고 해시 (int h) 메소드와 결합하여 키의 해시 코드를 추가로 최적화하고 높은 비트 계산을 추가하여 두 값 만 추가합니다. 동일한 해시 값의 값은 링크 된 목록을 형성하기 위해 배열에서 동일한 위치에 배치됩니다.
따라서 배열 길이가 N 전력 2 인 경우, 다른 키가 동일한 인덱스를 계산할 수있는 확률이 더 작아서 데이터가 배열에 고르게 분포되므로 충돌 확률이 작고 상대적으로 쿼리됩니다. 이번에는 링크 된 목록을 특정 위치에서 통과 할 필요가 없으므로 쿼리 효율이 높아집니다.
위의 푸트 방법의 소스 코드에 따르면, 프로그램이 키 값 쌍을 해시 맵에 넣으려고 할 때, 프로그램은 먼저 키의 해시 코드 () 반환 값을 기반으로 항목의 저장 위치를 결정합니다. 두 항목의 키 hashcode () 리턴 값은 동일하며 스토리지 위치는 동일합니다. 이 두 항목의 키가 Equals 비교를 통해 true를 반환하면 새로 추가 된 항목의 값은 컬렉션의 원래 항목의 값을 무시하지만 키는 무시되지 않습니다. 이 두 입력의 키가 Equals 비교를 통해 False가 거짓으로 반환되면, 새로 추가 된 항목은 컬렉션의 원래 항목이있는 항목 체인을 형성하고 새로 추가 된 항목은 항목 체인의 헤드에 있습니다. 세부 사항은 계속 보입니다. addentry () 메소드의 설명.
2) 읽기 :
public v get (object key) {if (key == null) reture hash = hash (key.hashcode (); 길이)] e! = e.next) {객체 k; return e.value} return null}. 해시 알고리즘이 위의 기본으로 저장되면이 코드를 쉽게 이해할 수 있습니다. 위의 소스 코드에서 Hashmap에서 요소를 얻을 때 먼저 키의 해시 코드를 계산하고 배열의 해당 위치에서 요소를 찾은 다음 해당 위치의 연결된 목록에서 필요한 요소를 찾을 수 있습니다. 키의 동등한 방법을 통해.
3) 요약하자면, 해시 맵은 하단에서 키 값을 전체적으로 처리 하며이 전체는 입구 객체입니다. 기본 해시 맵은 Entry [] 배열을 사용하여 모든 키 값 쌍을 저장해야 할 때 해시 알고리즘을 기반으로 배열의 저장 위치를 결정하고 배열의 위치를 결정합니다. 동등한 방법. 항목을 검색해야 할 때 해시 알고리즘에 따라 배열에서 저장 위치를 찾은 다음 해당 위치에서 링크 된 목록에서 항목을 추출합니다.
4. Hashmap 's resize (rashash) :
해시 맵에는 점점 더 많은 요소가 있기 때문에 배열의 길이가 고정되어 있기 때문에 해시 충돌 가능성이 높아지고 있습니다. 따라서 쿼리의 효율성을 향상시키기 위해 해시 크기의 배열은 ArrayList에서도 확장됩니다. 나타납니다 : 원래 배열의 데이터는 다시 계산하고 새로운 배열에 배치해야합니다.
그렇다면 해시 맵은 언제 확장됩니까? 해시 맵의 요소 수가 배열 크기 *loadfactor를 초과하면 배열의 기본값이 0.75이며 이는 타협 값입니다. 즉, 기본적으로 배열 크기는 16입니다. 그런 다음 해시 맵의 요소 수가 16*0.75 = 12를 초과하면 배열의 크기는 2*16 = 32, 즉 두 배의 크기로 확장됩니다. 그런 다음 배열에서 각 요소의 위치를 재 계산합니다. 이는 매우 성능 저렴한 작업이므로 해시 맵의 요소 수를 예측 한 경우 사전 설정 요소의 수는 해시 맵의 성능을 효과적으로 향상시킬 수 있습니다. .
5. 해시 맵 성능 매개 변수 :
Hashmap에는 다음 생성자가 포함됩니다.
Hashmap () : 초기 용량이 16이고 부하 계수가 0.75 인 해시 맵을 구축하십시오.
Hashmap (Int InitialCapacity) : 초기 용량과 0.75의 하중 계수를 가진 해시 맵을 구축하십시오.
HASHMAP (int initialcapacity, float loadfactor) : 지정된 초기 용량 및 지정된 하중 계수로 해시 맵을 만듭니다.
Hashmap의 기본 생성자 인 Hashmap (Int InitialCapacity, Float Loadfactor)에는 두 개의 매개 변수가 있으며 초기 용량 초기 범위 및로드 계수로드 변형기입니다.
초기 용량 : 해시 맵의 최대 용량, 즉 기본 배열의 길이.
LoadFactor :로드 계수로드 변수는 해시 테이블 (N)의 실제 요소 수/해시 테이블 (M)의 용량으로 정의됩니다.
하중 계수는 해시 테이블 공간의 사용 정도를 측정합니다. 링크 된 목록 방법을 사용하는 해시 테이블의 경우, 요소를 찾는 평균 시간은 O (1+A)이므로 공간이 더 많이 사용되지만 결과는 검색 효율이 감소합니다 하중 계수가 너무 작아지면 해시 테이블의 데이터가 너무 드물어 공간 낭비가 심각하게 발생합니다.
해시 맵의 구현에서 해시 맵의 최대 용량은 임계 값 필드에 의해 결정됩니다.
코드 사본은 다음과 같습니다.
임계 값 = (int) (용량 * loadfactor);
하중 계수의 정의 공식에 따라, 임계 값은로드 변형기에 따라 허용되는 최대 요소 수라는 것을 알 수 있습니다. 기본 부하 계수 0.75는 공간 및 시간 효율을위한 균형 잡힌 선택입니다. 용량 이이 최대 용량을 초과하면 크기가 크기가 높은 해시 맵 용량은 용량의 두 배입니다.
if (size ++> = 임계 값) resize (2 * table.length);
6. 빠른 메커니즘 :
우리는 java.util.hashmap이 스레드-안전하지 않다는 것을 알고 있으므로, 반복기를 사용하는 과정에서 다른 스레드가 맵을 수정하면 동시 모형화 외환이 발생합니다. 이는 소위 실패 전략입니다.
이 전략은 ModCount를 통해 소스 코드에서 구현됩니다. 반복자의 예상 모드 카운트.
hashiterator () {explicemodcount = modcount; }} 반복 프로세스 중에 ModCount 및 ExpectModCount가 동일하지 않으면 다른 스레드가 맵을 수정했음을 의미합니다.
ModCount는 휘발성으로 선언되어 스레드 간의 수정의 가시성을 보장합니다.
최종 항목 <k, v> nextEntry () {if (modCount! = excliteModCount) 새 ConcurrentModificationException () 버리기; Hashmap의 API에서는 다음과 같습니다.
모든 해시 맵 클래스의 "컬렉션 뷰 메소드"에 의해 반환 된 반복자는 빠르게 실패합니다. 반복자의 자체 제거 방법을 통과하지 않는 한, 반복자가 구조에서 수정되면 반복자는 다른 방법으로 반복됩니다 수정이 이루어지면 동시 변형을 던지십시오. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한시기에 임의의 불확실한 행동을 위험에 빠뜨리지 않고 곧 완전히 실패 할 것입니다.
반복자의 빠른 고장 거동은 일반적으로 비동기 동시 수정이있을 때는 확고한 보장을 할 수 없습니다. 빠른 실패 반복자는 가장 잘 작동하면 동시 모형화 소집을 던집니다. 따라서이 예외에 의존하는 프로그램을 작성하는 것은 잘못이며, 올바른 방법은 반복자의 빠른 고장 동작을 사용하여 프로그램 오류를 감지해야합니다.