대부분의 Java 개발자는 맵, 특히 해시 맵을 사용합니다. Hashmap은 간단하지만 강력한 저장 및 데이터를 얻는 방법입니다. 그러나 Hashmap이 내부적으로 어떻게 작동하는지 알고 있습니까? 며칠 전, 나는이 기본 데이터 구조에 대한 깊은 이해를 얻기 위해 java.util.hashmap (Java 7 및 Java 8 포함)의 많은 소스 코드를 읽었습니다. 이 게시물에서는 java.util.hashmap의 구현을 설명하고 Java 8 구현에 추가 된 새로운 기능을 설명하고 Hashmap을 사용할 때 성능, 메모리 및 알려진 문제에 대해 논의 할 것입니다.
내부 저장소
Java Hashmap 클래스는 맵 <k, v> 인터페이스를 구현합니다. 이 인터페이스의 주요 방법은 다음과 같습니다.
v put (k key, v value) v get (객체 키) v 제거 (객체 키) 부울 continainskey (객체 키)
Hashmap은 내부 클래스 항목 <k, v>를 사용하여 데이터를 저장합니다. 이 내부 클래스는 두 개의 추가 데이터가있는 간단한 키 값 쌍입니다.
해시 맵이 링크 목록과 같은 개체를 저장할 수 있도록 다른 항목에 대한 참조.
키를 나타내는 데 사용되는 해시 값. 이 값을 저장하면 해시 맵이 필요할 때마다 키에 해당하는 해시 값을 재생하는 것을 방지 할 수 있습니다.
다음은 Java 7에 따라 Entry <K, V> 코드의 일부입니다.
정적 클래스 항목 <k, v>는 map.entry <k, v> {최종 k 키; v value; enther <k, v> next; int 해시;…}를 구현합니다.해시 맵은 데이터를 여러 단방차 목록 (때로는 버킷 또는 컨테이너 오빈이라고 함)에 저장합니다. 모든 목록은 항목 배열 (Entry <k, v> [] array)에 등록 되며이 내부 배열의 기본 길이는 16입니다.
다음 그림은 해시 맵 인스턴스의 내부 저장에 대해 설명합니다. 해시 맵 인스턴스의 내부 저장소는 널리 사용 가능한 객체 배열이 포함되어 있습니다. 각 객체는 다른 객체에 연결되어 연결된 목록을 형성합니다.
해시 값이 동일한 모든 키는 동일한 링크 된 목록 (버킷)에 배치됩니다. 해시가 다른 키는 같은 양동이로 끝날 수 있습니다.
사용자가 put (k key, v value) 또는 get (객체 키)을 호출하면 프로그램은 객체가있는 버킷의 색인을 계산합니다. 그런 다음 프로그램은 해당 목록을 반복하여 동일한 키로 입력 오브젝트를 찾습니다 (키의 equals () 메서드 사용).
호출 get ()의 경우, 프로그램은 값에 해당하는 항목 개체를 반환합니다 (항목 개체가 존재하는 경우).
put (k key, v value)을 호출하려면 항목 객체가 이미 존재하는 경우 프로그램은 값을 새 값으로 바꾸게됩니다. 그렇지 않으면 프로그램이 일방 통행 링크 된 목록의 헤더에서 새 항목 (매개 변수의 키 및 값)이 생성됩니다.
버킷의 색인 (링크 된 목록)은 맵의 3 단계를 통해 생성됩니다.
먼저 키의 해시 코드를 얻으십시오.
이 프로그램은 해시 코드를 반복하여 키에 대한 잘못된 해시 함수를 차단합니다. 이는 모든 데이터를 내부 배열의 동일한 인덱스 (버킷)에 넣을 가능성이 있기 때문입니다.
이 프로그램은 중복 해시 코드를 가져 와서 배열 길이 (최소 1)의 비트 마스크를 사용합니다. 이 작업은 인덱스가 배열의 크기보다 크지 않도록합니다. 계산 된 최적화 된 모듈러스 기능으로 생각할 수 있습니다.
인덱스 생성을위한 소스 코드는 다음과 같습니다.
// Keystatic int Hash (int h)의 해시 코드를 취하는 Java 7의 "reshash"기능은 {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);} // Keystatic final inth (giet h key) (int h key) (int) (int) (int) (int) (int) (int) ( 0 : (h = key.hashcode ()) ^ (h >>> 16);} // 다시 해시 된 해시 적 int Indexfor (int h, int length)에서 인덱스를 반환하는 함수 {return h & (longth-1);}보다 효율적으로 작동하려면 내부 배열의 크기는 2의 전력이어야합니다. 이유를 보자.
배열의 길이가 17이라고 가정하면 마스크의 값은 16 (배열 길이 -1)입니다. 16의 바이너리 표현은 0… 010000이므로 임의의 값에 대해 "H & 16"의 결과는 16 또는 0입니다. 이는 길이 17의 배열이 두 개의 버킷에만 적용될 수 있음을 의미합니다. 하나는 0이고 다른 하나는 16이므로 그다지 효율적이지 않습니다. 그러나 배열의 길이를 2, 예를 들어 16의 전력으로 설정하면 Bitwise 인덱싱은 "H & 15"로 작동합니다. 15의 이진 표현은 0… 001111이며, 인덱스 공식에 의한 값 출력은 0에서 15 사이의 범위가 될 수 있으므로 길이 16의 배열을 완전히 사용할 수 있습니다. 예를 들어:
H = 952 인 경우 이진 표현은 0..01110111000이고 해당 색인은 0… 01000 = 8입니다.
H = 1576 인 경우 이진 표현은 0..011000101000이고 해당 색인은 0… 01000 = 8입니다.
H = 12356146 인 경우 바이너리 표현은 0..0101111001000101010010이면 해당 인덱스는 0… 00010 = 2입니다.
H = 59843 인 경우 이진 표현은 0..011101001110010011이면 해당 인덱스가 0… 00011 = 3입니다.
이 메커니즘은 개발자에게 투명합니다. 길이 37의 해시 맵을 선택하면 맵은 내부 배열의 길이로 37 (64)보다 큰 다음 전력 값을 자동으로 선택합니다.
자동으로 크기를 조정하십시오
인덱스를 얻은 후 get (), put () 또는 remove () 메소드는 해당 링크 된 목록에 액세스하여 지정된 키의 항목 객체가 이미 존재하는지 확인합니다. 수정이 없으면이 메커니즘은 성능 문제를 일으킬 수 있습니다.이 방법은 입력 객체가 존재하는지 확인하기 위해 전체 목록을 반복해야하므로 성능 문제를 일으킬 수 있습니다. 내부 배열의 길이가 기본값 16을 가져오고 2,000,000 레코드를 저장해야한다고 가정합니다. 최선의 경우 링크 된 목록 당 125,000 개의 항목 객체가 있습니다 (2,000,000/16). get (), remove () 및 put () 메소드에는 실행할 때마다 125,000 개의 반복이 필요합니다. 이를 피하기 위해 해시 맵은 내부 배열의 길이를 증가시켜 링크 된 목록에 몇 개의 항목 객체 만 유지되도록합니다.
해시 맵을 만들 때 다음 생성자를 통해 초기 길이와로드 변형기를 지정할 수 있습니다.
</pre> public hashmap (int initialcapacity, float loadfactor) <pre>
매개 변수를 지정하지 않으면 기본 초기 범위 값은 16이고 기본 부하 변형 값은 0.75입니다. 초기 범위는 내부 배열의 링크 된 목록의 길이를 나타냅니다.
PUT (…) 메소드를 사용하여 맵에 새 키 값 쌍을 추가하면 메소드가 내부 배열의 길이를 증가시켜야하는지 확인합니다. 이를 달성하기 위해 MAP는 2 데이터를 저장합니다.
맵 크기 : 해시 맵의 레코드 수를 나타냅니다. 해시 맵에 삽입하거나 삭제할 때 값을 업데이트합니다.
임계 값 : 내부 배열*loadfactor의 길이와 같 으며이 임계 값은 내부 배열의 길이를 조정할 때마다 동시에 업데이트됩니다.
새 항목 객체를 추가하기 전에 Put (…) 메소드는 현재 맵의 크기가 임계 값보다 얼마나 큰지 확인합니다. 임계 값보다 크면 현재 내부 배열의 길이의 두 배로 새 배열을 만듭니다. 새 배열의 크기가 변경되었으므로 인덱스 함수 (즉, 비트 조작 결과 "키의 해시 값 (Array Length -1)")도 변경됩니다. 어레이를 조정하면 두 개의 새 버킷 (링크 된 목록)이 생성되고 기존의 모든 항목 객체를 버킷에 재 할 수 있습니다. 배열 크기를 조정하는 목표는 링크 된 목록의 크기를 줄여서 put (), remove () 및 get () 메소드의 실행 시간을 줄이는 것입니다. 해시 값이 동일한 키에 해당하는 모든 항목 객체의 경우 크기 조정 후 동일한 버킷에 할당됩니다. 그러나 두 입력 객체의 해시 값이 다르지만 이전에 동일한 버킷에있는 경우 조정 후에도 여전히 같은 버킷에 있다는 보장은 없습니다.
이 이미지는 조정 전 및 조정 후 내부 배열의 상황을 설명합니다. 항목 객체 E를 얻기 위해 배열 길이를 조정하기 전에 맵은 5 개의 요소가 포함 된 링크 된 목록을 반복해야합니다. 배열 길이를 조정 한 후, 동일한 get () 메소드는 2 개의 요소를 포함하는 링크 된 목록만을 가로 질러야하므로 배열 길이를 조정 한 후 get () 메소드의 실행 속도가 2 배 증가합니다.
실 안전
당신이 이미 해시 맵에 매우 익숙하다면, 당신은 그것이 스레드 안전하지 않다는 것을 확실히 알고 있지만, 왜 그런가? 예를 들어, 기존 데이터를 맵에 삽입하는 Writer 스레드, 맵에서 데이터를 읽을 독자 스레드 만 있다고 가정 해 봅시다. 왜 작동하지 않습니까?
자동 크기 조정 메커니즘에서 스레드가 객체를 추가하거나 얻으려고 할 경우 맵은 이전 인덱스 값을 사용할 수 있으므로 입력 객체가있는 새 버킷을 찾을 수 없습니다.
최악의 경우 2 개의 스레드가 동시에 데이터를 삽입하면 2 put () 호출이 동시에 시작되고 배열이 자동으로 크기 조정됩니다. 두 스레드가 링크 된 목록을 동시에 수정하므로 맵이 링크 된 목록의 내부 루프에서 종료 될 수 있습니다. 내부 루프가있는 목록에서 데이터를 얻으려고하면 get () 메소드가 끝나지 않습니다.
Hashtable은 위의 발생을 방지하는 스레드 안전 구현을 제공합니다. 그러나 모든 동기 CRUD 작업은 매우 느리기 때문입니다. 예를 들어, 스레드 1 호출이 (key1)을 얻으면 스레드 2 호출이 (key2)되고 스레드 2 호출이 get (key3)을 얻으면 지정된 시간에 1 개의 스레드 만 값을 얻을 수 있지만 3 개의 스레드는 모두 동시에 이러한 데이터에 액세스 할 수 있습니다.
Java 5 이후, 우리는 더 나은 스레드 안전 해시 맵 구현을 가지고 있습니다 : consurenthashmap. ConcurrentMap의 경우 버킷 만 동기화되므로 여러 스레드가 동일한 버킷을 사용하지 않거나 내부 배열 크기를 조정하면 get (), remove () 메소드를 동시에 호출 할 수 있습니다. 멀티 스레드 응용 프로그램 에서이 접근법은 더 나은 선택입니다.
채권의 불변
문자열과 정수를 해시 맵의 키로 사용하는 것이 좋은 구현입니까? 주로 그들은 불변이기 때문에! 클래스를 열쇠로 직접 만들기로 선택했지만 클래스가 불변이라고 보장 할 수는 없다면 해시 맵 내에서 데이터를 잃을 수 있습니다.
다음 사용 사례를 살펴 보겠습니다.
내부 값이 "1"인 키가 있습니다.
객체를 해시 맵에 삽입하면 키는 "1"입니다.
해시 맵은 키의 해시 코드에서 해시 값을 생성합니다 (즉, "1").
맵은 새로 생성 된 레코드 에이 해시 값을 저장합니다.
키의 내부 값을 변경하고 "2"로 변경합니다.
키의 해시 값은 변경되었지만 해시 맵은 이것을 알지 못합니다 (이전 해시 값이 저장되어 있기 때문에).
수정 된 키로 해당 객체를 얻으려고합니다.
맵은 새 키 (즉, "2")의 해시 값을 계산하여 입력 객체가있는 링크 된 목록 (버킷)을 찾습니다.
사례 1 : 키를 수정 했으므로 MAP는 잘못된 버킷에서 항목 객체를 찾으려고하지만 찾을 수 없습니다.
사례 2 : 수정 된 키에 의해 생성 된 버킷과 이전 키에 의해 생성 된 버킷이 동일하다는 것이 운이 좋다. 그런 다음 맵은 링크 된 목록을 가로 지르고 동일한 키가있는 항목 객체가 발견되었습니다. 그러나 키를 찾으려면 맵은 equals () 메소드를 호출하여 키의 해시 값을 먼저 비교합니다. 수정 된 키가 다른 해시 값을 생성하기 때문에 (이전 해시 값은 레코드에 저장됨) MAP는 링크 된 목록에서 해당 항목 객체를 찾을 방법이 없습니다.
다음은 두 개의 키 값 쌍을 맵에 삽입 한 다음 첫 번째 키를 수정하고 두 객체를 얻으려고하는 Java 예제입니다. 맵에서 반환 된 두 번째 객체 만 해시 맵에서 "손실"되었습니다.
public class mutablekeytest {public static void main (string [] args) {class mykey {integer i; public void seti (integer i) {this.i = i;} public mykey (integer i) {this.i = i;}@overidepublic int hashcode () {return i; mykey) {return i.equals (((Mykey) obj) .i); key1key1.seti (3); String test1 = myMap.get (key1); String test2 = myMap.get (key2); System.out.println ( "test1 =" + test1 + "test2 =" + test2);}}위의 코드의 출력은 "test1 = null test2 = test 2"입니다. 예상대로 MAP에는 수정 된 키 1에 해당하는 문자열 1을 얻는 기능이 없습니다.
Java 8의 개선
Java 8에서는 Hashmap의 내부 구현이 많이 수정되었습니다. 실제로 Java 7은 1000 줄의 코드를 사용하여 구현하는 반면 Java 8은 2000 줄의 코드를 사용합니다. 이전에 설명한 대부분의 것은 Entry Object를 저장하기 위해 링크 된 목록을 사용하는 것을 제외하고는 Java 8에서 여전히 정확합니다. Java 8에서는 여전히 배열을 사용하지만 이전 항목 객체와 동일한 정보를 포함하고 링크 된 목록을 사용하는 노드에 저장됩니다.
다음은 Java 8의 노드를 구현하는 코드의 일부입니다.
정적 클래스 노드 <k, v>는 map.entry <k, v> {최종 int 해시; 최종 k 키; v 값; node <k, v> next;그렇다면 Java 7에 비해 큰 차이점은 무엇입니까? 글쎄, 노드는 Treenode로 확장 될 수 있습니다. Treenode는 더 많은 정보를 저장할 수있는 빨간색과 검은 색 트리의 데이터 구조이므로 O (log (n))의 복잡성에 따라 요소를 추가, 삭제 또는 얻을 수 있습니다. 다음 예제는 Treenode에서 저장된 모든 정보를 설명합니다.
정적 최종 클래스 Treenode <k, v>는 linkedhashmap.entry <k, v> {Final int Hash; // 노드에서 상속 <k, v> final k 키; // 노드에서 상속 <k, v> v 값; // 노드에서 상속 <k, v> 노드 <k, v> 다음; // 노드에서 상속 <k, v> entry <k, v> 이전; // intrindhashmap.entry <k, v> parent; treenode <k, v> 왼쪽; treenode <k, v> 오른쪽; treenode <k, v> prev; 부울 빨간;빨간색과 검은 나무는 자체 균형 이진 검색 검색 트리입니다. 내부 메커니즘은 노드를 추가하거나 삭제하든 길이가 항상 로그 (n)임을 보장합니다. 이 유형의 트리를 사용하면 가장 중요한 이점은 내부 테이블의 많은 데이터가 동일한 인덱스 (버킷)를 갖는 경우입니다. 현재 트리 검색의 복잡성은 O (log (n))이며 링크 된 목록의 경우 동일한 작업을 수행하기위한 복잡성이 O (N)입니다.
보시다시피, 우리는 링크 된 목록보다 트리에 더 많은 데이터를 저장합니다. 상속 원칙에 따르면 내부 테이블에는 노드 (링크 된 목록) 또는 Treenode (빨간색 및 검은 색 트리)가 포함될 수 있습니다. Oracle은 다음 규칙에 따라이 두 가지 데이터 구조를 사용하기로 결정합니다.
- 내부 테이블의 지정된 인덱스 (버킷)의 경우 노드 수가 8보다 큰 경우 링크 된 목록은 빨간색과 검은 색 트리로 변환됩니다.
- 내부 테이블의 지정된 인덱스 (버킷)의 경우 노드 수가 6 미만인 경우 빨간색과 검은 색 트리가 링크 된 목록으로 변환됩니다.
이 이미지는 Java 8 해시 맵의 내부 배열을 설명하며, 여기에는 트리 (버킷 0)와 링크 된 목록 (버킷 1, 2 및 3)이 포함되어 있습니다. 버킷 0은 8 개 이상의 노드를 포함하기 때문에 트리 구조입니다.
메모리 오버 헤드
Java 7
해시 맵을 사용하면 메모리가 소비됩니다. Java 7에서 Hashmap은 키 값 쌍을 입력 객체로 캡슐화하고 항목 객체에는 다음 정보가 포함되어 있습니다.
다음 레코드에 대한 참조 사전 계산 된 해시 값 (정수)
키에 대한 참조 및 값에 대한 참조
또한 Java 7의 Hashmap은 내부 엔트리 객체를 사용합니다. Java 7 해시 맵에 n 요소가 포함되어 있고 내부 배열이 용량을 가지고 있다고 가정하면 추가 메모리 소비가 다음과 같습니다.
크기 (정수)* n + sizeof (참조)* (3* n + c)
안에:
정수의 크기는 4 바이트입니다
참조 크기는 JVM, 운영 체제 및 프로세서에 따라 다르지만 일반적으로 4 바이트입니다.
이는 총 메모리 오버 헤드가 일반적으로 16 * n + 4 * 용량 바이트임을 의미합니다.
참고 : 맵이 자동으로 크기가 조정 된 후 용량 값은 N보다 큰 다음으로 가장 작은 전력입니다.
참고 : Java 7에서 시작하여 Hashmap은 게으른 하중 메커니즘을 채택합니다. 즉, 해시 맵의 크기를 지정하더라도, 먼저 put () 메소드를 사용하기 전에 메모리에 할당되지 않은 내부 배열 (4*용량 바이트 소비)을 지정합니다.
Java 8
Java 8 구현에서는 노드가 항목과 동일한 데이터를 저장하거나 6 개의 참조 및 부울 속성 (트리 노드 여부를 지정)을 추가 할 수 있기 때문에 메모리 사용량 컴퓨팅이 더욱 복잡해집니다.
모든 노드가 노드 인 경우 Java 8 Hashmap이 소비 한 메모리는 Java 7 Hashmap에서 소비 한 것과 동일합니다.
모든 노드가 Treenode 인 경우 Java 8 Hashmap이 소비하는 메모리가 다음과 같습니다.
n * sizeof (정수) + n * sizeof (boolean) + sizeof (참조) * (9 * n + 용량)
대부분의 표준 JVM에서 위의 공식의 결과는 44 * n + 4 * 용량 바이트입니다.
성능 문제
비대칭 해시 맵 대 균형 해시 맵
최선의 경우 get () 및 put () 메소드 모두 O (1) 복잡성 만 있습니다. 그러나 키의 해시 함수에 신경 쓰지 않으면 put () 및 get () 메소드가 매우 느리게 실행될 수 있습니다. put () 및 get () 메소드의 효율적인 실행은 내부 배열 (버킷)의 다른 인덱스에 할당되는 데이터에 따라 다릅니다. 키의 해시 함수가 제대로 설계되지 않은 경우 내부 데이터의 크기에 관계없이 비대칭 파티션이 나타납니다. 모든 put () 및 get () 메소드는 가장 큰 링크 된 목록을 사용하며 링크 된 목록의 모든 레코드를 반복해야하므로 실행이 느리게됩니다. 최악의 경우 (대부분의 데이터가 동일한 버킷에있는 경우) 시간 복잡성은 O (n)이됩니다.
다음은 시각적 예입니다. 첫 번째 그래프는 비대칭 해시 맵을 설명하고 두 번째 그래프는 평형화 된 해시 맵을 설명합니다.
SKEWEDHASHMAP
이 비대칭 해시 맵에서는 버킷 0에서 get () 및 put () 메소드를 실행하는 데 시간이 걸립니다. 레코드 k를 얻는 데 6 개의 반복이 필요합니다.
이 균형 잡힌 해시 맵에서는 레코드 K를 얻기 위해 3 개의 반복 만 필요합니다.이 두 해시 맵은 동일한 양의 데이터를 저장하고 내부 배열은 동일한 크기입니다. 유일한 차이점은 키의 해시 함수로, 다른 버킷에 레코드를 분배하는 데 사용됩니다.
다음은 Java로 작성된 극단적 인 예입니다. 여기서 해시 함수를 사용하여 모든 데이터를 동일한 링크 된 목록 (버킷)에 넣은 다음 2,000,000 개의 데이터를 추가했습니다.
public class test {public static void main (String [] args) {class mykey {integer i; public mykey (Integer i) {this.i = i;}@atederidepublic int hashcode () {return 1;}@atedridepublic boolean equals (object obj) {…}} 날짜 = new Date (); mykey, string, string, string, string. hashmap <> (2_500_000,1); for (int i = 0; i <2_000_000; i ++) {mymap.put (new Mykey (i), "test"+i);} date end = new date (); system.out.println ( "duration (ms)"+(end.get ()-begin.gettime ()));내 컴퓨터 구성은 Core i5-2500K @ 3.6g이며 Java 8U40에서 실행하는 데 45 분 이상이 걸립니다 (45 분 후에 프로세스가 중지 됨). 동일한 코드를 실행하면 다음과 같은 해시 기능을 사용합니다.
@overridepublic int hashcode () {int key = 2097152-1; 반환 키+2097152*i;}실행하는 데 46 초가 걸립니다. 이전보다 훨씬 좋습니다! 새로운 해시 함수는 해시 파티션을 처리 할 때 이전 해시 기능보다 합리적이므로 put () 메소드를 호출하는 것이 더 빠릅니다. 지금 동일한 코드를 실행하지만 아래의 해시 함수를 사용하면 더 나은 해시 파티션을 제공합니다.
@overridepublic int hashcode () {return i;}이제 2 초 밖에 걸리지 않습니다!
해시 기능이 얼마나 중요한지 알 수 있기를 바랍니다. Java 7에서 동일한 테스트를 실행하면 첫 번째와 두 번째는 더 나빠집니다 (Java 7의 put () 메소드에는 O (n) 복잡성이 있고 Java 8의 복잡성은 O (log (n))가 있기 때문입니다.
Hashmap을 사용하는 경우 키를 가장 가능성이 높은 버킷에 퍼뜨릴 수있는 키에 대한 해시 기능을 찾아야합니다. 이렇게하려면 해시 충돌을 피해야합니다. 문자열 객체는 해시 기능이 양호하기 때문에 매우 좋은 키입니다. 해시가 고유 한 가치이기 때문에 정수도 좋습니다.
오버 헤드 크기 조정
많은 양의 데이터를 저장 해야하는 경우 해시 맵을 생성 할 때 초기 용량을 지정해야하며 원하는 크기에 가깝습니다.
이 작업을 수행하지 않으면 맵은 기본 크기 (예 : 16)를 사용하고 팩터로드 값은 0.75입니다. Put () 메소드에 대한 첫 11 번의 전화는 매우 빠르지 만 12 번째 (16*0.75) 호출은 길이 32 (및 해당 링크 된 목록/트리)의 새로운 내부 배열을 생성하고 Put () 메소드에 대한 13 ~ 22 번의 호출은 매우 빠르지 만 23 번째 (32*0.75) 호출은 새로운 내부 배열을 다시 만들고, 배열의 길이는 다시 재현됩니다. 그러면 put () 메소드가 48th, 96th, 192nd라고 불릴 때 내부 크기 조정 작업이 트리거됩니다. 데이터 양이 크지 않으면 내부 배열 재 구축 작업은 매우 빠르지 만 데이터 양이 클 경우 소비 된 시간은 몇 초에서 분에 걸쳐있을 수 있습니다. 초기화 중에 원하는 맵의 크기를 지정하면 작업 크기 조정으로 인한 소비를 피할 수 있습니다.
그러나 여기에는 단점이 있습니다. 배열을 예를 들어 2^28과 같은 배열로 설정하면 배열에 2^26 버킷을 사용하면 많은 메모리를 낭비합니다 (이 예에서 약 2^30 바이트).
결론적으로
간단한 사용 사례의 경우 O (1), O (N) 및 O (log (N))의 차이를 보지 않기 때문에 해시 맵의 작동 방식을 알 필요가 없습니다. 그러나 자주 사용되는이 데이터 구조의 메커니즘을 이해하는 것이 항상 유익합니다. 또한 이것은 Java 개발자 위치에 대한 일반적인 인터뷰 질문입니다.
큰 데이터 볼륨의 경우 해시 맵의 작동 방식을 이해하고 키에 대한 해시 기능의 중요성을 이해하는 것이 매우 중요합니다.
이 기사가 해시 맵의 구현을 깊이 이해하는 데 도움이되기를 바랍니다.