우리는 두 개의 Arraylist와 LinkedList 세트를 분석했습니다. ArrayList는 배열에 따라 구현되며 LinkedList는 링크 된 목록을 기반으로 구현됩니다. 각각 자체의 장점과 단점이 있습니다. 예를 들어, 요소를 포지셔닝하고 찾을 때 ArrayList가 LinkedList보다 우수하지만 LinkedList는 요소를 추가하고 제거 할 때 ArrayList보다 좋습니다. 이 기사에 소개 된 해시 맵은 두 가지의 장점을 결합합니다. 기본 레이어는 해시 테이블을 기반으로 구현됩니다. 해시 충돌이 고려되지 않으면 해시 맵의 시간 복잡성, 삭제, 수정 및 검색 작업이 놀라운 O (1)에 도달 할 수 있습니다. 먼저 해시 테이블의 구조를 기반으로하는 해시 테이블을 살펴 보겠습니다.
위 그림에서 볼 수 있듯이 해시 테이블은 배열과 링크 된 목록으로 구성된 구조입니다. 물론 위의 그림은 나쁜 예입니다. 좋은 해시 함수는 배열에서 요소 분포를 평균화하고 해시 충돌을 줄이며 링크 된 목록의 길이를 줄이려고 노력해야합니다. 링크 된 목록의 길이가 길수록 검색 중에 더 많은 노드를 통과해야할수록 해시 테이블의 성능이 악화됨을 의미합니다. 다음으로 해시 맵의 일부 멤버 변수를 살펴 보겠습니다.
// 기본 초기 용량 정적 최종 최종 최종 최종 int default_initial_capacity = 1 << 4; // 기본 최대 용량 정적 최종 최종 int maximum_capacity = 1 << 30; // 기본로드 팩터는 해시 테이블이 정적 최종 플로트에 도달 할 수있는 방법을 나타냅니다. default_load_factor = 0.75f; // empty hash 테이블 입력 <? [] emply__tody =}; 과도 항목 <k, v> [] table = (Entry <k, v> []) empty_table; // 해시 맵 크기, 즉 해시 맵 과도 int 크기에 저장된 키-값 쌍의 수 FAIL-FAST 메커니즘 과도 int modCount; // 대체 해시의 기본 임계 값을 사용하여 해시 정적 최종 int anternative_hashing_threshold_default = integer.max_value; // 랜덤 해시 시드는 해시 충돌 수를 줄이는 데 도움이됩니다.
멤버 변수에서 알 수 있듯이 해시 맵의 기본 초기 용량은 16이고 기본 부하 계수는 0.75입니다. 임계 값은 세트에 저장할 수있는 키 값 쌍의 임계 값입니다. 기본값은 초기 용량*로딩 계수, 즉 16*0.75 = 12입니다. 키 값 쌍이 임계 값을 초과 해야하는 경우 해시 테이블이 이미 포화되어 있음을 의미합니다. 요소가 계속 추가되면 해시 충돌이 추가되어 해시 맵의 성능이 저하됩니다. 현재 해시 맵의 성능을 보장하기 위해 자동 용량 확장 메커니즘이 트리거됩니다. 또한 해시 테이블이 실제로 입력 배열임을 알 수 있으며 배열에 저장된 각 항목은 일방 통행 링크 목록의 헤더 노드입니다. 이 항목은 해시 맵의 정적 내부 클래스입니다. 입력의 멤버 변수를 살펴 보겠습니다.
정적 클래스 항목 <k, v>는 map.entry <k, v> {최종 K 키; // 키 V 값; // 값 항목 <k, v> 다음; // 다음 항목에 대한 참조 INT HASH; // histocode ... // 다음 코드를 생략}}입력 인스턴스는 키와 값을 포함하는 키 값 쌍입니다. 각 항목 인스턴스에는 다음 항목 인스턴스에 대한 참조가 있습니다. 반복 계산을 피하기 위해 각 입력 인스턴스는 해당 해시 코드도 저장합니다. 입력 배열은 해시 맵의 핵심 이며이 배열에 대해 모든 작업이 수행됩니다. 해시 맵 소스 코드는 상대적으로 길기 때문에 모든 방법을 포괄적 인 방식으로 도입하는 것은 불가능하므로 소개하는 핵심 포인트에만 집중합니다. 다음으로, 우리는 문제 지향적이며 다음 문제에 대해 해시 맵의 내부 메커니즘을 탐색 할 것입니다.
1. 건설 중에 Hashmap은 어떤 작업을 수행합니까?
// 생성자, 초기화 용량 및 하중 계수 공개 해시 맵 (int initialcapacity, float loadfactor) {if (InitialCapacity <0) {throw new New OregalArgumentException ( "불법 초기 용량 :" + 초기 범위); } // 초기화 용량이 최대 용량보다 큰 경우 (InitialCapacity> maximum_capacity) {initialcapacity = maximum_capacity; } // 하중 계수가 0 미만이거나 부하 계수가 플로팅 포인트 번호가 아닌 경우 (loadfactor <= 0 || float.isnan (loadfactor)) {New New ImperalArgumentException ( "불법 부하 계수 :" + loadfactor); } // 하중 계수를 설정 this.loadFactor = loadFactor; // 임계 값은 초기화 용량 임계 값 = 초기 범위입니다. init ();} void init () {}모든 생성자는이 생성자를 호출합니다. 이 생성자에서는 매개 변수를 약간 검증하는 것 외에도로드 계수를 들어오는 하중 계수로 설정하고 임계 값을 들어오는 초기화 크기로 설정합니다. Init 메소드는 비어 있고 아무것도하지 않습니다. 현재 초기화 크기에 따라 새로운 입력 배열이 생성되지 않습니다. 그렇다면 언제 새 배열을 만들 것인가? 계속 읽으십시오.
2. Hashmap이 키 값 쌍을 추가 할 때 어떤 작업이 수행됩니까?
// 키-값 쌍을 해시 맵 공개 v put (k key, v value)에 넣습니다. {// if (table == empty_table) {// 해시 테이블 inflatetable (threshold) 초기화; } if (key == null) {return putfornullkey (value); } // 키 int hash = hash (key)의 해시 코드를 계산합니다. // 해시 코드에 따른 해시 테이블의 위치를 int i = indexfor (Hash, table.length); for (Entry <k, v> e = 테이블 [i]; e! = null; e = e.next) {object k; // 해당 키가 이미 존재하는 경우 값 값을 바꾸고 원래 값을 반환합니다. e.Value = 값; e.recordaccess (this); OldValue를 반환하십시오. }} modcount ++; // 해당 키가 없으면 Hashmap Addentry에 항목을 추가하십시오 (해시, 키, 값, i); // return null return null;}키 값 쌍을 추가 할 때 먼저 해시 테이블이 빈 테이블인지 확인하고 빈 테이블이면 초기화됩니다. 그런 다음 후속 작업을 수행하고 해시 함수를 호출하여 전달 된 키의 해시 코드를 계산하십시오. 해시 코드에 따라 입력 배열의 지정된 슬롯을 배치 한 다음 슬롯의 일방 통행 링크 목록을 통과하십시오. 통과 된 사람이 이미 존재하는 경우 교체 작업을 수행하면 새 항목이 생성되어 해시 테이블에 추가됩니다.
3. 해시 테이블은 어떻게 초기화됩니까?
// 해시 테이블을 초기화하면 해시 테이블 용량이 확장됩니다. 들어오는 용량은 2 개인 무효화가 풍부한 2 개의 전력이 아닐 가능성이 있기 때문입니다. // 임계 값을 설정하십시오. 여기에 일반적으로 용량이 있습니다 * loadfactor threshold = (int) math.min (용량 * loadfactor, maximum_capacity + 1); // 지정된 용량으로 새 해시 테이블을 만듭니다. 테이블 = 새 항목 [용량]; // 해시 씨앗을 초기화 inithashseedasned (용량);}
위에서 알 수 있듯이 해시 맵을 구성 할 때 새 항목 배열을 생성하지는 않지만 현재 해시 테이블이 풋 작업 중에 빈 테이블인지 확인하십시오. 빈 테이블 인 경우 초기화를 위해 팽창 식 방법을 호출하십시오. 이 방법의 코드는 위에 게시됩니다. 해시 맵을 구성 할 때 전달 된 초기화 크기가 2의 전력이 아닐 수 있으므로 입력 배열의 용량이 메소드 내부에서 재 계산 될 수 있으므로이 숫자가 2의 전력으로 변환 한 다음 새 용량을 기반으로 새 항목 배열을 만들어야합니다. 해시 테이블을 초기화 할 때 임계 값을 다시 재설정하면 임계 값은 일반적으로 용량*loadfactor입니다. 또한 해시 테이블을 초기화 할 때 해시 시드 (해시드)가 초기화됩니다. 이 해시드는 해시 함수를 최적화하는 데 사용됩니다. 기본값은 0이고 대체 해시 알고리즘이 사용되지는 않지만 최적화 효과를 달성하기 위해 해시 값을 직접 설정할 수도 있습니다. 이것은 아래에서 자세히 설명합니다.
4. Hashmap은 언제 용량을 확장 해야하는지 여부와 용량을 확장하는 방법을 언제 결정합니까?
// 입력 메소드를 추가하고 먼저 용량 void Addentry (int Hash, k key, v value, int bucketIndex)를 확장할지 여부를 결정하십시오. {// 해시 맵의 크기가 임계 값보다 크고 해시 테이블의 해당 슬롯의 값이 비어 있지 않으면 (size> = theshold) && (null! = table))) {// 임계 값은 해시 충돌이 발생할 것이라는 것을 나타냅니다. 따라서 용량 크기 조정 (2 * table.length)을 확장하십시오. hash = (null! = 키)? 해시 (키) : 0; BucketIndex = indexfor (Hash, table.length); } // 여기에 해시 맵의 크기가 임계 값을 초과하지 않으므로 용량을 확장 할 필요가 없습니다. int oldcapacity = oldtable.length; // 현재 최대 용량이 이미 사용중인 경우 (OldCapacity == maximum_capacity) {threshold = integer.max_value; 반품; } // 그렇지 않으면 용량 항목을 확장합니다 [] newTable = new entry [newCapacity]; // 해시 테이블 전송을 마이그레이션하는 메소드 (NewTable, inithashseedasneded (newCapacity)); // 현재 해시 테이블을 새 해시 테이블 테이블 = newtable로 설정합니다. // 해시 테이블 임계 값을 업데이트 = (int) math.min (newCapacity * loadfactor, maximum_capacity + 1);}풋 메소드를 호출하여 키 값 쌍을 추가 할 때 컬렉션에 키가 없으면 Addentry 메소드를 호출하고 새 항목을 작성하십시오. 위에 게시 된 Addentry 코드가 표시되면 새 항목을 작성하기 전에 먼저 현재 수집 요소의 크기가 임계 값을 초과하는지 여부를 결정합니다. 임계 값이 임계 값을 초과하면 resize resize를 초과하면 확장을 위해 호출하십시오. 통과 된 새로운 용량은 원래 해시 테이블의 두 배입니다. 크기 조정 메소드에서는 원래 해시 테이블의 두 배의 용량을 갖는 새로운 입력 배열이 생성됩니다. 그런 다음 오래된 해시 테이블의 모든 요소가 새로운 해시 테이블로 마이그레이션되어 재사용이 수행 될 수 있으며, 재 해시를 수행할지 여부는 inithashseedasneded 방법에 의해 계산 된 값에 따라 수행됩니다. 해시 테이블 마이그레이션이 완료된 후, 현재 해시 테이블이 새 테이블로 대체되며 마지막으로 해시 맵의 임계 값은 새 해시 테이블 용량에 따라 다시 계산됩니다.
5. 입력 배열의 크기가 왜 2의 전력이어야합니까?
// 해시 코드 STATIC Int Indexfor (int h, int length)에 해당하는 배열 인덱스를 반환합니다. {return h & (longth-1); }인덱스 용 메소드는 해시 코드를 기반으로 배열의 해당 첨자를 계산합니다. 우리는 (&) 연산자 가이 방법에서 사용된다는 것을 알 수 있습니다. 작업은 두 개의 피연산자에서 비트 작업을 수행하는 것입니다. 해당 두 비트가 1 인 경우 결과는 1입니다. 그렇지 않으면 01011010 & 00001111 = 00001010과 같은 오 피연드 값을 제거하는 데 사용됩니다. 코드로 돌아가서 H & (1-1)의 역할을 보자.
통과 된 길이는 입력 배열의 길이 인 것으로 알려져 있습니다. 배열 첨자는 0에서 계산되므로 배열의 최대 첨자는 길이 1입니다. 길이가 2 인 경우, 길이 -1의 이진 비트에 이어 1이 뒤 따릅니다.이 시점에서 H & (길이 -1)의 함수는 H의 높은 비트 값을 제거하고 H의 낮은 비트 값 만 배열의 첨자로 남겨 두는 것입니다. 이것으로부터 우리는 항목 배열의 크기 가이 알고리즘을 사용하여 배열의 첨자를 결정하기 위해 2의 전력으로 정의된다는 것을 알 수 있습니다.
6. 해시 함수는 해시 코드를 어떻게 계산합니까?
// 해시 코드를 생성하는 함수 최종 int Hash (Object K) {int h = Hashseed; // 키가 문자열 유형 인 경우 다른 해시 알고리즘을 사용하십시오. } h ^= k.hashcode (); // 섭동 함수 h ^ = (h >>> 20) ^ (h >>> 12); h ^ (h >>> 7) ^ (h >>> 4);} 반환해시 방법의 마지막 두 줄은 해시 값을 진정으로 계산하는 알고리즘입니다. 해시 코드를 계산하는 알고리즘을 섭동 함수라고합니다. 소위 섭동 기능은 모든 것을 함께 혼합하는 것입니다. 여기에는 4 개의 오른쪽 시프트 작업이 사용됨을 알 수 있습니다. 목적은 H의 높은 값과 낮은 값을 혼합하여 낮은 값의 임의성을 증가시키는 것입니다. 위와 같이, 우리는 포지셔닝 어레이의 첨자가 해시 코드의 낮은 비트 값에 따라 결정된다는 것을 알고 있습니다. 키의 해시 코드는 해시 코드 메소드에 의해 생성되며 잘못된 해시 코드 메소드에 의해 생성 된 해시 코드의 낮은 값은 많은 반복을 가질 수 있습니다. 해시 코드를 배열에서 비교적 균일하게 매핑하기 위해, 섭동 함수는 유용하며, 비 비트 값의 특성을 낮은 비트 값으로 결합하여 낮은 비트 값의 무작위성을 증가시켜 해시 분포를 더 느슨하게하여 성능을 향상시킵니다. 다음 그림은 이해하는 데 도움이되는 예를 제공합니다.
7. 교체 Hash는 무슨 일이 일어나고 있습니까?
해시 방법에서 해시드는 먼저 h에 할당 될 것임을 알 수 있습니다. 이 해시드는 해시 씨앗으로 임의의 값이며 해시 함수를 최적화하는 데 사용됩니다. 기본 해시 시드는 0이므로 대체 해시 알고리즘은 기본적으로 사용되지 않습니다. 그렇다면 언제 hashseed를 사용합니까? 먼저, 대체 해시를 설정하고 시스템 속성에서 jdk.map.althashing.threshold의 값을 설정해야합니다. 이 값은 시스템 속성에서 기본적으로 -1입니다. -1 인 경우 대체 해시를 사용하는 임계 값은 integer.max_value입니다. 이것은 또한 교체 해시를 사용할 수 없음을 의미합니다. 물론 세트 요소가 임계 값에 도달하면 임의의 해시드가 생성되도록이 임계 값을 조금 더 작게 설정할 수 있습니다. 이것은 해시 함수의 무작위성을 증가시킵니다. 대체 해시를 사용하는 이유는 무엇입니까? 설정 요소가 설정 한 임계 값에 도달하면 해시 테이블이 상대적으로 포화되어 있고 해시 충돌 가능성이 크게 증가 함을 의미합니다. 이 시점에서, 추가 된 요소에 더 임의의 해시 함수를 사용하면 추가 요소가 해시 테이블에 무작위로 분산 될 수 있습니다.
참고 : 위의 모든 분석은 JDK1.7을 기반으로하며 다른 버전간에 큰 변화가있을 것이므로 독자는주의를 기울여야합니다.