해시 맵 개요
Hashmap은 해시 테이블을 기반으로 한 맵 인터페이스의 비동기 구현입니다. 이 구현은 모든 옵션 매핑 작업을 제공하며 NULL 값 및 NULL 키를 사용할 수 있습니다. 이 클래스는 매핑의 순서를 보장하지 않습니다. 특히 주문이 지속될 것이라고 보장하지는 않습니다.
해시 맵의 데이터 구조
Java 프로그래밍 언어에는 두 가지 기본 구조가 있으며, 하나는 배열이고 다른 하나는 시뮬레이션 된 포인터 (참조)입니다. 모든 데이터 구조는이 두 가지 기본 구조를 사용하여 구성 할 수 있으며 해시 맵도 예외는 아닙니다. Hashmap은 실제로 "링크 된 목록 해시"데이터 구조, 즉 배열 및 링크 된 목록의 구조이지만 JDK1.8입니다.
빨간색과 검은 색 트리의 구현이 추가됩니다. 링크 된 목록의 길이가 8보다 큰 경우 빨간색과 검은 색 트리의 구조로 변환됩니다.
위 그림에서 볼 수 있듯이 Hashmap은 Java의 체인 주소 방법을 사용합니다. 간단히 말하면 링크 주소 방법은 배열과 링크 된 목록의 조합입니다. 각 배열 요소에는 링크 된 목록 구조가 있습니다. 데이터가 해시되면 배열 첨자가 얻어지고 데이터는 해당 첨자 요소의 링크 된 목록에 배치됩니다.
*/ static 클래스 노드 <k, v> 구현 map.entry <k, v> {최종 int hash; // 배열 인덱스 최종 K 키의 위치를 찾는 데 사용됩니다. v 값; 노드 <k, v> next; // 링크 된 목록 노드의 다음 노드 (int hash, k key, v value, node <k, v> next) {this.hash = hash; this.key = 키; this.value = value; this.next = 다음; }노드는 내부 해시 맵 클래스로, 맵 (key-value 쌍) 인 맵. 엔트리 인터페이스를 구현합니다.
때로는 두 개의 키가 같은 위치에 위치하여 해시 충돌이 발생했음을 나타냅니다. 물론 해시 알고리즘의 계산 결과가 균일할수록 해시 충돌 가능성이 작고 맵의 액세스 효율이 높아집니다.
해시 맵 클래스에는 노드 [] 테이블, 즉 해시 버킷 어레이입니다. 분명히 노드 배열입니다.
해시 버킷 어레이가 크면 해시 알고리즘이 불량한 경우에도 더 흩어져 있습니다. 해시 버킷 어레이 어레이 어레이가 작 으면 좋은 해시 알고리즘조차 더 많은 충돌이 발생하므로 공간 비용과 시간 비용을 평가해야합니다. 실제로 실제 상황에 따라 해시 버킷 어레이의 크기를 결정하는 것이며,이를 바탕으로 설계된 해시 알고리즘은 해시 충돌을 줄입니다. 해시 충돌 가능성을 작게 만들기 위해 맵을 제어 할 수 있고 해시 버킷 어레이 (Node [] 테이블)가 공간을 덜 차지할 수 있습니까? 답은 좋은 해시 알고리즘과 용량 확장 메커니즘입니다.
해시 및 확장 프로세스를 이해하기 전에 해시 맵의 여러 필드를 이해해야합니다. Hashmap의 기본 생성자의 소스 코드에서 생성자가 다음 필드를 초기화하는 것을 알 수 있습니다. 소스 코드는 다음과 같습니다.
int 임계 값; // 수용 할 수있는 키 값은 궁극적 인 float loadfactor입니다. //로드 계수 int modcount; int 크기;
먼저, 노드 [] 테이블의 초기화 길이 (기본값은 16),로드 계수는로드 계수 (기본값은 0.75)이고 임계 값은 해시 맵이 수용 할 수있는 최대 데이터 양의 노드 수 (키-값 쌍)입니다. 임계 값 = 길이 * 하중 계수. 즉, 배열이 길이를 정의한 후에는 하중 계수가 클수록 수용 할 수있는 키 값 쌍이 더 많습니다.
하중 계수의 정의 공식에 기초하여, 임계 값은이 하중 계수 및 길이 (배열 길이)에 따라 허용되는 최대 요소 수임을 알 수 있습니다. 이 숫자가 이것을 초과하면 크기를 조정하십시오 (용량 확대). 확장 된 해시 맵 용량은 이전 용량의 두 배입니다. 기본 부하 계수 0.75는 공간 및 시간 효율을위한 균형 잡힌 선택입니다. 특수 시간과 공간의 경우 많은 메모리 공간과 높은 시간 효율 요구 사항이 있으면로드 계수로드 계수의 값을 줄일 수없는 경우에도 수정하지 않는 것이 좋습니다. 반대로, 메모리 공간이 빡빡하고 시간 효율 요구 사항이 높지 않으면로드 계수로드 변형의 값을 증가시킬 수 있으며 이는 1보다 클 수 있습니다.
크기 필드는 실제로 이해하기 쉽습니다. 실제로 해시 맵에 존재하는 키 값 쌍의 수입니다. 테이블의 길이와 최대 키 값 쌍을 수용하는 임계 값의 차이에 유의하십시오. ModCount 필드는 주로 해시 맵의 내부 구조의 변화 수를 기록하는 데 주로 사용되며 주로 반복의 빠른 고장에 주로 사용됩니다. 강조하기 위해, 내부 구조의 변화는 새로운 키 값 쌍을 넣는 것과 같은 구조의 변화를 말하지만 키에 해당하는 값은 덮어 쓰고 구조적 변화에 속하지 않습니다.
해시 맵에서 해시 버킷 어레이 테이블의 길이는 2의 n 전력 (복합 번호 여야 함)이어야합니다. 이것은 비 전통적인 디자인입니다. 기존의 디자인은 버킷의 크기를 소수로 설계하는 것입니다. 비교적 말하면, 소수로 인한 충돌 가능성은 복합 수의 것보다 작습니다. 특정 증거는 //www.vevb.com/article/100911.htm을 참조하십시오. 해시 가능은 버킷 크기를 11로 초기화합니다. 이는 소수로 설계된 버킷 크기의 적용입니다 (해시 가능은 확장 후 소수로 보장 할 수 없습니다). Hashmap은이 비 전통적인 디자인을 채택하여 주로 모듈로 및 확장 시점을 최적화합니다. 동시에, 충돌을 줄이기 위해 Hashmap은 해시 버킷 인덱스 위치를 찾을 때 컴퓨팅에 대한 고 비트 참여 프로세스를 추가합니다.
여기에 문제가 있습니다. 하중 계수와 해시 알고리즘이 합리적으로 설계 되더라도 지퍼가 너무 길어지는 상황이 필연적으로있을 것입니다. 지퍼가 너무 길면 해시 맵의 성능에 심각한 영향을 미칩니다. 따라서 JDK1.8 버전에서는 데이터 구조가 추가로 최적화되었고 빨간색과 검은 색 트리가 도입되었습니다. 링크 된 목록의 길이가 너무 길면 (기본값이 8 이상) 연결된 목록은 빨간색과 검은 색 트리로 변환됩니다. 빨간색 및 검은 색 트리의 특성, 삭제, 수정 및 검색의 특성은 해시 맵의 성능을 향상시키는 데 사용됩니다. 빨간색과 검은 나무의 삽입, 삭제 및 검색은 빨간색과 검은 색 나무와 같은 검색 알고리즘을 삽입, 삭제 및 검색하는 데 사용됩니다.
해시 버킷 어레이의 인덱스 위치를 결정하십시오
코드 구현 :
// 메소드 1 : 정적 최종 int 해시 (개체 키) {//jdk1.8 & jdk1.7 int h; // h = key.hashCode () 첫 번째 단계의 해시 코드 값을 가져옵니다. // h ^ (h >>> 16) 두 번째 단계 리턴의 작동에 참여합니다 (key == null)? 0 : (h = key.hashcode ()) ^ (h >>> 16);} // 메소드 2 : 정적 int indexfor (int h, int length) {//jdk1.7 소스 코드, JDK1.8은이 메소드가 없지만 구현 원리는 동일한 반환 h & (길이 -1)입니다. // 세 번째 단계는 모듈러스 작동을 취합니다}여기서 해시 알고리즘은 기본적으로 세 단계입니다. 키, 고 비트 작동 및 모듈러스 작동의 해시 코드 값을 취합니다.
주어진 객체의 경우 해시 코드 () 리턴 값이 동일하다면, 프로그램 호출 방법으로 계산 된 해시 코드는 항상 동일합니다. 우리가 가장 먼저 생각하는 것은 해시 값을 배열 길이로 모듈화하여 요소의 분포가 비교적 균일하다는 것입니다. 그러나 모듈러스 작업의 소비는 상대적으로 큽니다. 이것은 hashmap : call method 2에서 수행되어 테이블 배열에 저장 해야하는 객체를 색인화하는 것을 계산합니다.
이 방법은 매우 영리합니다. H & (표 -11)를 통해 객체의 저장된 비트를 얻습니다. 해시 맵의 기본 배열의 길이는 항상 2의 N 전력으로 이는 속도 측면에서 해시 맵의 최적화입니다. 길이가 항상 2의 N 전력에있을 때, H & (길이 -1) 조작은 모듈로 길이, 즉 H %길이와 동일하지만 %보다 효율이 높다.
JDK1.8을 구현할 때, 고 비트 작업에 대한 알고리즘은 최적화되고, 16 비트 XOR 하위 16 비트 구현은 주로 속도, 효율성 및 품질에서 고려되는 hashcode () : (h = k.hashcode ()) ^ (h >>> 16). 이렇게하면 배열 테이블의 길이가 비교적 작을 때, 비트가 높은 수준의 해시 계산에 관여 할 수 있으며 과도한 오버 헤드가 없을 수 있습니다.
다음은 N이 테이블의 길이입니다.
Hashmap Put 방법 구현
풋 기능의 일반적인 아이디어는 다음과 같습니다.
특정 코드는 다음과 같이 구현됩니다.
public v put (k key, v value) {return putval (해시 (키), 키, 값, 거짓, 참); } / ***해시 생성 방법* / 정적 최종 int 해시 (개체 키) {int h; return (key == null)? 0 : (h = key.hashcode ()) ^ (h >>> 16); } final v putval (int hash, k key, v value, boolean Onlyifabsent, boolean evict) {node <k, v> [] 탭; 노드 <k, v> p; int n, i; // 테이블이 비어 있는지, if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize ()). 길이; // 키 값 키에 따라 삽입 된 배열 인덱스 I에 해시 값을 계산합니다. 표 [i] == null이면 새 노드를 직접 생성하고 if ((p = tab [i = (n -1) & hash]) == null) 탭 [i] = newnode (hash, key, value, null); else {// 해당 노드에 노드 <k, v> e가있는 경우; K K; // 테이블 [i]의 첫 번째 요소가 키와 동일한 지 여부를 판단합니다. 동일 한 경우 값을 직접 덮어 씁니다 (p.hash == hash && ((k = p.key) == key || (key! = null && key.equals (k))) e = p; // 테이블 [i]가 트린 노드인지, 즉 테이블 [i]가 빨간색 나무인지 여부를 판단합니다. 빨간색 검은 트리 인 경우 트리에 키 값 쌍을 직접 삽입하십시오. else if (p instanceof treenode) e = ((treenode <k, v>) p) .puttreeval (this, 탭, 해시, 키, 값); //이 체인은 링크 된 목록입니다. {// 링크 된 목록의 길이가 treeify_threshold보다 큰지 여부를 결정하기 위해 테이블 [i]를 통과합니다 (기본값은 8). 8보다 큰 경우 링크 된 목록을 빨간색 블랙 트리로 변환하고 빨간색 블랙 트리에서 삽입 작업을 수행하십시오. 그렇지 않으면 링크 된 목록의 삽입 작업이 수행됩니다. 키가 이미 트래버스 프로세스 중에 직접 덮어 쓰기 값을 가지고 있음을 발견 한 경우; for (int bincount = 0;; ++ bincount) {if ((e = p.next) == null) {p.next = newNode (해시, 키, 값, null); if (bincount> = treeify_threshold -1) // -1 1st treeifybin (탭, 해시); 부서지다; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) break; p = e; }} // write if (e! = null) {// key v OldValue = e.Value에 대한 기존 매핑; if (! 만 피바 젠트 || OldValue == null) e.value = value; 오후에 반응 (E); OldValue를 반환하십시오. }} ++ modcount; // 삽입이 성공한 후에는 실제 값 쌍의 수가 최대 용량 임계 값을 초과하는지 여부를 결정하십시오. 용량을 초과하면 (++ size> threshold) resize (); OfferodeInsertion (evict); 널 리턴; }해시 맵 GET 메소드 구현
아이디어는 다음과 같습니다.
1. 버킷의 첫 번째 노드는 직접 쳤다.
2. 충돌이있는 경우 key.equals (k)를 사용하여 해당 항목을 찾으십시오.
나무 인 경우 key.equals (k), o (logn)을 통해 트리에서 검색합니다.
링크 된 목록 인 경우 링크 된 목록에서 key.equals (k)를 검색하십시오. O (n).
public v get (객체 키) {노드 <k, v> e; return (e = getNode (hash (key), key) == null? NULL : e.Value; } 최종 노드 <k, v> getNode (int hash, 객체 키) {node <k, v> [] 탭; 노드 <k, v> 먼저, e; int n; K K; if ((tab = table)! = null && (n = tab.length)> 0 && (First = Tab [(n -1) & hash])! = null) {// 직접 적중 if (first.hash == hash && // 첫 번째 노드를 확인할 때마다 ((k = first.key) == key || (ky.fequals (k))); // 누락 된 if ((e = first.next)! = null) {// get if (treenode의 첫 번째 인스턴스) return ((treenode <k, v>) .gettreenode (hash, key); // get do {if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) return e; } while ((e = e.next)! = null); }} return null; }용량 확장 메커니즘
크기 조정은 용량을 재 계산하고 해시 맵 객체에 요소를 지속적으로 추가하는 것을 의미합니다. 해시 맵 객체 내부의 배열에 더 많은 요소를로드 할 수없는 경우 더 많은 요소를로드 할 수 있도록 배열의 길이를 확장해야합니다. 물론 Java의 배열은 자동으로 확장 될 수 없습니다. 이 방법은 작은 양동이를 사용하여 물을 채우는 것처럼 작은 용량의 기존 배열 대신 새 배열을 사용하는 것입니다. 더 많은 물을 채우려면 큰 양동이로 교체해야합니다.
우리는 크기 조정의 소스 코드를 분석합니다. JDK1.8이 빨간색과 검은 나무를 통합한다는 점을 감안할 때 더 복잡합니다. 이해를 용이하게하기 위해 여전히 이해하기 쉬운 JDK1.7 코드를 사용합니다. 본질에는 거의 차이가 없습니다. 나중에 특정 차이점에 대해 이야기합시다.
void resize (int newCapacity) {// new 용량 항목을 일시 중지 [] oldtable = table; // 확장 전에 항목 배열을 참조하십시오 int OldCapacity = OldTable.length; if (OldCapacity == maximum_capacity) {// 확장 전 배열 크기가 최대 (2^30) 임계 값 = integer.max_value에 도달 한 경우; // 미래의 수익률에서 용량이 확장되지 않도록 int (2^31-1)의 최대 값으로 임계 값을 수정하십시오. } entry [] newtable = 새로운 항목 [newCapacity]; // 새 항목 배열 전송 (newtable)을 초기화합니다. //! ! 새 항목 배열 테이블 = newtable로 데이터를 전송합니다. // HASHMAP의 테이블 속성은 새 항목 배열 임계 값 = (int) (newCapacity * loadFactor)를 나타냅니다. // 임계 값 수정}여기서는 용량이 작은 기존 배열 대신 더 큰 용량의 배열을 사용합니다. Transfer () 메소드는 원래 항목 배열의 요소를 새 항목 배열에 복사합니다.
무효 전송 (entry [] newtable) {entry [] src = 테이블; // src는 이전 항목 배열을 말합니다 int newCapacity = newtable.length; for (int j = 0; j <src.length; // 이전 입력 배열의 각 요소를 가져옵니다. if (e! = null) {src [j] = null; // 기존 항목 배열의 객체 참조 (for 루프 후에는 이전 항목 배열이 더 이상 객체를 참조하지 않음) do {enth <k, v> next = e.next; int i = indexfor (e.hash, newcapacity); //! ! 배열에서 각 요소의 위치를 다시 계산합니다. e.next = newtable [i]; // 태그 [1] newtable [i] = e; // 배열에 요소를 넣습니다. e = 다음; // 다음 항목 체인에서 요소에 액세스하십시오} while (e! = null); }}}NewTable [I]에 대한 참조는 E.Next에 할당되며, 이는 단일 링크 된 목록의 헤더 삽입 방법이 사용됨을 의미합니다. 같은 위치에있는 새로운 요소는 항상 링크 된 목록의 헤드에 배치됩니다. 이런 식으로, 인덱스에 배치 된 요소는 결국 입력 체인의 끝에 배치됩니다 (해시 충돌이 발생하는 경우). 이것은 JDK1.8과 다르며, 아래에서 자세히 설명되어 있습니다. 기존 배열의 동일한 입력 체인의 요소는 인덱스 위치를 재 계산 한 후 새 배열의 다른 위치에 배치 될 수 있습니다.
다음은 용량 확장 프로세스를 설명하는 예입니다. 해시 알고리즘이 단순히 키 모드를 사용하여 테이블 크기 (즉, 배열의 길이)를 얻는다고 가정합니다. 해시 버킷 어레이 테이블의 크기 = 2, 키 = 3, 7, 5 및 풋 순서는 5, 7 및 3입니다. 모드 2 이후 충돌은 표 [1]에 있습니다. 여기서,로드 계수로드 변형기 = 1, 즉 키 값 쌍의 실제 크기가 테이블의 실제 크기보다 클 때 확장된다고 가정합니다. 다음 세 단계는 해시 버킷 어레이를 4로 크기를 조정 한 다음 모든 노드를 재 해당하는 과정입니다.
JDK1.8에서 어떤 최적화가 이루어 졌는지 설명해 봅시다. 관찰 후, 우리는 우리가 두 개의 확장의 힘을 사용하고 있음을 알 수 있습니다 (원본의 두 배 길이를 참조). 요소의 위치는 원래 위치에 있거나 원래 위치에서 2의 힘의 위치를 다시 움직입니다. 아래 그림을 살펴보면이 문장의 의미를 이해할 수 있습니다. n은 테이블의 길이입니다. 그림 (a)는 확장 전에 key1 및 key2의 인덱스 위치를 결정하는 두 키의 인덱스 위치의 예를 나타냅니다. 도 (b)는 확장 후 key1 및 key2의 인덱스 위치의 예를 나타낸다. 여기서 HASH1은 KEY1에 해당하는 해시 및 비 비트 작동 결과입니다.
요소가 해시를 재 계산 한 후, N이 2 배가되기 때문에, N-1의 마스크 범위는 하이 포인트에서 1 비트 (빨간색)이므로 새로운 인덱스가 다음과 같이 변경됩니다.
따라서 해시 맵을 확장 할 때 JDK1.7의 구현과 같이 해시를 다시 계산할 필요가 없습니다. 원래 해시 값에 추가 된 비트가 1 또는 0인지 확인하면됩니다. 0이면 인덱스가 변경되지 않았습니다. 1 인 경우 인덱스는 "원래 색인 + OldCap"이됩니다. 다음 그림을 16으로 32로 확장하여 크기 조정 다이어그램으로 볼 수 있습니다.
이 디자인은 실제로 매우 영리하며, 해시 값을 다시 계산할 시간을 절약 할뿐만 아니라 새로 추가 된 1 비트가 0 또는 1이므로 무작위로 간주 될 수 있으므로 크기 조정 프로세스는 이전 충돌 노드를 새 버킷에 균등하게 분배합니다. 이것은 JDK1.8에 의해 추가 된 새로운 최적화 지점입니다. 차이에 약간의 관심이 있습니다. JDK1.7의 재활 일 때, 오래된 연결된 목록이 새 링크 된 목록을 마이그레이션 할 때, 새 테이블의 배열 인덱스 위치가 동일하면 링크 된 목록 요소가 반전되지만 위 그림에서 볼 수 있듯이 JDK1.8은 반전되지 않습니다. 관심있는 학생들은 JDK1.8의 크기 조정 소스 코드를 연구 할 수 있습니다. 이는 다음과 같이 매우 좋습니다.
최종 노드 <k, v> [] resize () {node <k, v> [] oldtab = table; int OldCap = (OldTab == null)? 0 : OldTab.length; int oldthr = 임계 값; int newcap, newthr = 0; if (OldCap> 0) {// 최대 값이 초과되면 더 이상 확장되지 않으므로 (OldCap> = maximum_capacity) {threshold = integer.max_value; oldtab을 반환합니다. } // 최대 값이 초과되지 않으면 원래 if ((newCap = OldCap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newthr = Oldthr << 1; // double threshold} else if (oldthr> 0) // 초기 용량이 임계 값에 배치되었습니다. newCap = Oldthr; else {// Zero 초기 임계 값은 기본값을 사용하여 NewCap = default_initial_capacity를 사용합니다. newthr = (int) (default_load_factor * default_initial_capacity); } // 새 크기의 상한 계산 If (newthr == 0) {float ft = (float) newCap * loadfactor; newthr = (newCap <maximum_capacity && ft <(float) maximum_capacity? (int) ft : integer.max_value); } threshold = newthr; @suppresswarnings ({ "rawtypes", "unchecked"}) 노드 <k, v> [] newtab = (node <k, v> []) 새 노드 [newCap]; 테이블 = Newtab; if (OldTab! = null) {// 각 버킷을 새 버킷으로 이동하십시오 (int j = 0; j <OldCap; ++ j) {Node <k, v> e; if ((e = OldTab [j])! = null) {OldTab [j] = null; if (e.next == null) newtab [e.hash & (newcap -1)] = e; else if (e eforindof treenode) ((treenode <k, v>) e) .split (this, newtab, j, oldcap); else {// 순서 노드 보존 <k, v> lohead = null, lotail = null; 노드 <k, v> hihead = null, hitail = null; 노드 <k, v> 다음; {next = e.next; // 원본 색인 if ((E.Hash & OldCap) == 0) {if (lotail == null) lohead = e; else lotail.next = e; lotail = e; } // Original Index + OldCap else {if (hitail == null) hihead = e; else hitail.next = e; Hitail = e; }} while ((e = next)! = null); // 원래 색인을 버킷에 넣습니다. if (lotail! = null) {lotail.next = null; newtab [j] = lohead; } // 원래 색인 + OldCap을 버킷에 넣습니다. if (hitail! = null) {hitail.next = null; newtab [J + OldCap] = hihead; }}}}} return newtab;}요약
이제 해시 맵에 대한 이해를 심화시키기 위해 처음에 몇 가지 질문에 대답 할 수 있습니다.
1. 해시 맵은 언제 사용됩니까? 그의 특성은 무엇입니까?
맵 인터페이스의 구현을 기반으로합니다. 키 값 쌍을 저장할 때는 비동기식 인 널 키 값을받을 수 있습니다. Hashmap Stores Entry (해시, 키, 값, 다음) 객체.
2. 해시 맵이 어떻게 작동하는지 아십니까?
해시 방법을 통해 물체는 Put and Get을 통해 저장 및 얻어집니다. 객체를 저장할 때 k/v를 풋 방법으로 전달할 때 해시 코드를 호출하여 해시를 계산하여 버킷 위치를 가져 와서 더 저장합니다. HashMap은 현재 버킷 점유에 따라 용량을 자동으로 조정합니다 (하중 Facotr을 초과하는 경우 크기 조정은 원본의 두 배입니다). 객체를 얻을 때는 k를 통과시켜 해시 코드를 호출하여 해시를 계산하여 버킷 위치를 얻고 equals () 메소드를 호출하여 키 값 쌍을 결정합니다. 충돌이 발생하면 Hashmap은 연결된 목록을 통해 충돌 충돌을 생성하는 요소를 구성합니다. Java 8에서, 버킷에서 충돌하는 요소가 특정 한계를 초과하는 경우 (기본값은 8), 빨간색과 검은 색 트리는 링크 된 목록을 교체하여 속도를 높이는 데 사용됩니다.
3. Get and Put의 원칙을 알고 있습니까? equals () 및 hashcode ()의 함수는 무엇입니까?
키의 hashcode ()를 해싱하고 첨자 (n-1 & hash)를 계산하면 버킷의 위치가 얻어집니다. 충돌이 발생하면 key.equals () 메소드를 사용하여 링크 된 목록 또는 트리의 해당 노드를 검색하십시오.
4. HASH의 구현을 알고 있습니까? 왜 이것을해야합니까?
Java 1.8의 구현에서, 그것은 주로 속도, 효율 및 품질에서 고려되는 Hashcode ()의 높은 16 비트 x-또는 낮은 16 비트 16 비트를 통해 구현됩니다. 이를 통해 버킷의 N이 비교적 작을 때는 해시 계산에 높고 낮은 비트가 모두 해당 계산에 관여 할 수 있으며 과도한 오버 헤드가 없도록 할 수 있습니다.
5. 해시 맵의 크기가 하중 계수로 정의 된 용량을 초과하면 어떻게됩니까?
하중 계수가 초과되면 (기본 0.75) 원래 길이의 두 배인 해시 맵이 크기가 커지고 해시 방법이 다시 호출됩니다.
Java 컬렉션에 대한 치트 시트는 다음과 같이 설명됩니다.
Entry [] 배열로 구현 된 해시 버킷 어레이는 키의 해시 값을 사용하여 배열 첨자를 얻을 수 있습니다.
요소를 삽입 할 때, 두 키가 동일한 버킷에 빠지면 (예 : 해시 값 1과 17이 Modulo 16 인 후에는 모두 첫 번째 해시 버킷에 속한 경우) 항목은 다음 속성을 사용하여 일방 통행 링크 목록에서 여러 항목을 구현하고 버킷의 현재 항목 옆에 버킷 포인트를 입력하는 항목.
해시 값이 17 인 키를 찾을 때 먼저 첫 번째 해시 버킷을 찾은 다음 링크 된 목록과 버킷의 모든 요소를 반복하고 주요 값을 하나씩 비교하십시오.
항목 수가 버킷의 75%에 도달하면 (많은 기사에서 사용 된 버킷의 수가 75%에 도달한다고 말하지만 코드에 따르면 버킷 어레이는 기하 급수적으로 확장되고 모든 원래 항목이 재 할당되므로 여기에서 예상 값을 갖는 것이 가장 좋습니다.
비트 조작 (HASH & (Arraylength-1))가 더 빠르기 때문에 배열의 크기는 항상 N 전력 2입니다. 17과 같은 초기 값을 주면 32로 변환됩니다. 요소가 처음 배치 된 경우 기본 초기 값은 16입니다.
iterator ()는 해시 버킷 어레이를 따라 가로 지르며 순서대로 보입니다.
6. 두 객체의 해시 코드가 동일하면 어떻게됩니까?
해시 코드는 동일하기 때문에 버킷 위치는 동일하며 '충돌'이 발생합니다. Hashmap은 링크 된 목록을 사용하여 객체를 저장하기 때문에이 항목 (맵. 키 값 쌍이 포함 된 객체 객체)은 링크 된 목록에 저장됩니다.
7. 두 키의 해시 코드가 동일하다면 값 객체를 어떻게 얻습니까?
버킷 위치를 찾은 후 keys.equals () 메소드가 호출되어 링크 된 목록에서 올바른 노드를 찾아서 마지막으로 찾을 수있는 값 객체를 찾습니다. 따라서 주요 유형의 해시 맵을 설계 할 때, 불변의 객체가 최종으로 선언되고 적절한 equals () 및 hashcode () 메소드가 사용되면 충돌 발생이 줄어들고 효율이 향상됩니다. 불변성은 다른 키의 해시 코드를 캐시 할 수있어 전체 객체를 얻는 속도가 높아집니다. String 및 Interger와 같은 래퍼 클래스를 키로 사용하는 것이 매우 좋습니다.
8. 해시 맵의 크기가 하중 계수로 정의 된 용량을 초과하면 어떻게됩니까?
기본 부하 계수 크기는 0.75입니다. 즉, 맵이 다른 컬렉션 클래스 (예 : Arraylist 등)와 같이 75% 버킷을 채우면 원래 해시 맵의 두 배 크기 인 버킷 배열이 맵을 조정하고 원래 객체를 새 버킷 어레이에 넣을 수 있도록 만들어집니다. 이 과정은 새 버킷 위치를 찾기 위해 해시 방법을 호출하기 때문에 재 해싱이라고합니다.
9. 해시 맵 크기를 조정하는 데 무엇이 잘못되었는지 이해하십니까?
해시 맵 크기를 조정할 때는 실제로 조건부 경쟁이 있습니다. 두 스레드 모두 해시 맵이 크기를 조정해야한다는 것을 발견하면 동시에 크기를 조정하려고합니다. 크기 조정 프로세스 중에 링크 된 목록에 저장된 요소의 순서가 반전됩니다. 새 버킷 위치로 이동할 때 Hashmap은 링크 된 목록의 끝에 요소를 배치하지 않고 머리에 꼬리가 횡단을 피하기 때문에 요소를 배치하기 때문입니다. 조건부 경쟁이 발생하면 악순환이 있습니다. 따라서 동시 환경에서는 Currenthashmap을 사용하여 해시 맵을 대체합니다.
10. String 및 Interger와 같은 래퍼 클래스가 키로 적합한 이유는 무엇입니까?
문자열은 불변적이고 최종적이기 때문에 equals () 및 hashcode () 메소드가 다시 작성되었습니다. 다른 래퍼 클래스에는이 기능도 있습니다. hashcode ()를 계산하기 위해서는 키 값이 변경되는 것을 방지해야하기 때문에 불변성이 필요합니다. 키 값이 들어가거나 얻을 때 다른 해시 코드를 반환하면 해시 맵에서 원하는 객체를 찾을 수 없습니다. 불변성에는 실 안전과 같은 다른 장점이 있습니다. 필드를 최종으로 선언하여 해시 코드가 변경되지 않음을 보장 할 수 있다면 그렇게하십시오. 객체를 얻을 때 equals () 및 hashcode () 메소드가 사용 되므로이 두 메소드를 올바르게 다시 작성하는 것이 매우 중요합니다. 두 개의 불평등 한 개체가 다른 해시 코드를 반환하면 충돌 가능성이 더 작아서 해시 맵의 성능이 향상됩니다.
읽어 주셔서 감사합니다. 도움이되기를 바랍니다. 이 사이트를 지원 해주셔서 감사합니다!