1. 개요
이 기사에서는 Java의 HashMap 에서로드 팩터의 중요성 과 이것이 맵의 성능에 어떤 영향을 미치는지 살펴볼 것입니다.
2. HashMap 은 무엇입니까 ?
HashMap의 클래스는 자바 컬렉션 프레임 워크에 속하며의 기본 구현을 제공하는 지도 인터페이스를. 키-값 쌍으로 데이터를 저장하고자 할 때 사용할 수 있습니다. 이러한 키-값 쌍을 맵 항목이라고하며 Map.Entry 클래스 로 표시됩니다 .
3. HashMap 내부
부하율을 논의하기 전에 몇 가지 용어를 검토해 보겠습니다.
-
- 해싱
- 생산 능력
- 문지방
- 다시 해싱
- 충돌
HashMap 은 객체 데이터를 대표 정수 값에 매핑하는 알고리즘 인 해싱 원칙에 따라 작동 합니다 . 해싱 함수는 키-값 쌍을 저장하고 검색하기 위해 버킷의 인덱스를 계산하기 위해 키 객체에 적용됩니다.
용량은 HashMap 의 버킷 수입니다 . 초기 용량은 M ap 가 생성 될 때의 용량 입니다. 마지막으로 HashMap 의 기본 초기 용량 은 16입니다.
HashMap 의 요소 수가 증가하면 용량이 확장됩니다. 부하율은 지도 의 용량을 늘릴시기를 결정하는 척도입니다 . 기본 부하율은 용량의 75 %입니다.
HashMap 의 임계 값 은 대략 현재 용량과 부하 계수의 곱입니다. Rehashing은 이미 저장된 항목의 해시 코드를 다시 계산하는 프로세스입니다. 간단히 말해, 해시 테이블의 항목 수가 임계 값을 초과하면 맵 이 다시 해시 되어 이전보다 약 두 배의 버킷 수가 있습니다.
해시 함수가 두 개의 다른 키에 대해 동일한 버킷 위치를 반환하면 충돌이 발생합니다.
HashMap을 만들어 보겠습니다 .
Map<String, String> mapWithDefaultParams = new HashMap<>();
mapWithDefaultParams.put("1", "one");
mapWithDefaultParams.put("2", "two");
mapWithDefaultParams.put("3", "three");
mapWithDefaultParams.put("4", "four");
지도 의 구조는 다음과 같습니다 .
보시다시피 HashMap 은 기본 초기 용량 (16)과 기본 부하 계수 (0.75)로 생성되었습니다. 또한 임계 값은 16 * 0.75 = 12이므로 12 번째 항목 (키-값 쌍)이 추가 된 후 용량이 16에서 32로 증가합니다.
4. 사용자 지정 초기 용량 및 부하 계수
이전 섹션에서는 기본 생성자로 HashMap 을 만들었습니다 . 다음 섹션에서는 초기 용량과로드 팩터를 생성자에 전달 하는 HashMap 을 만드는 방법을 살펴 봅니다 .
4.1. 초기 용량 포함
먼저 초기 용량 으로 맵 을 생성 해 보겠습니다 .
Map<String, String> mapWithInitialCapacity = new HashMap<>(5);
초기 용량 (5) 및 기본 부하 계수 (0.75)가 포함 된 빈 맵 이 생성됩니다 .
4.2. 초기 용량 및 부하 계수 포함
마찬가지로 초기 용량과 부하율을 모두 사용하여 맵 을 생성 할 수 있습니다 .
Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5, 0.5f);
여기에서 초기 용량이 5이고 부하 계수가 0.5 인 빈 맵 이 생성됩니다 .
5. 성능
초기 용량과 부하율을 유연하게 선택할 수 있지만 현명하게 선택해야합니다. 둘 다 지도 의 성능에 영향을 미칩니다 . 이러한 매개 변수가 성능과 어떤 관련이 있는지 살펴 보겠습니다.
5.1. 복잡성
아시다시피 HashMap은 내부적으로 키-값 쌍을 저장하기위한 기반으로 해시 코드를 사용합니다. 는 IF 해시 코드 () 메소드가 잘 기록, HashMap의는 모든 버킷에서 항목을 배포합니다. 따라서 HashMap 은 일정한 시간 O (1)에 항목을 저장하고 검색합니다 .
그러나 항목 수가 증가하고 버킷 크기가 고정되면 문제가 발생합니다. 각 버킷에 더 많은 항목이 있으며 시간 복잡성을 방해합니다.
해결책은 항목 수가 증가 할 때 버킷 수를 늘릴 수 있다는 것입니다. 그런 다음 모든 버킷에 항목을 재배포 할 수 있습니다. 이러한 방식으로 각 버킷에 일정한 수의 항목을 유지하고 O (1) 의 시간 복잡성을 유지할 수 있습니다.
여기에서 부하 계수는 버킷 수를 늘릴시기를 결정하는 데 도움이됩니다 . 부하 계수가 낮을수록 더 많은 빈 버킷이 있으므로 충돌 가능성이 줄어 듭니다. 이것은 우리의 지도 성능을 향상시키는 데 도움이 될 것 입니다. 따라서 낮은 시간 복잡성을 달성하기 위해 부하 계수를 낮게 유지해야합니다 .
해시 MAP 통상의 공간 복잡도 갖는다 O (N)를 , 여기서 N 엔트리의 수이다. 로드 비율 값이 높을수록 공간 오버 헤드가 감소하지만 조회 비용이 증가합니다 .
5.2. 재해 싱
맵 의 항목 수가 임계 값 제한을 초과하면 맵 의 용량 이 두 배가됩니다. 앞에서 설명한 것처럼 용량이 증가하면 모든 항목 (기존 항목 및 새 항목 포함)을 모든 버킷에 균등하게 배포해야합니다. 여기서 우리는 재해 싱이 필요합니다. 즉, 기존의 각 키-값 쌍에 대해 증가 된 용량을 매개 변수로 사용하여 해시 코드를 다시 계산합니다.
기본적으로 부하율이 증가하면 복잡성이 증가합니다. 리 해싱은 모든 작업에 대해 낮은 부하 계수와 낮은 복잡성을 유지하기 위해 수행됩니다.
Map을 초기화합시다 .
Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5,0.75f);
mapWithInitialCapacityAndLF.put("1", "one");
mapWithInitialCapacityAndLF.put("2", "two");
mapWithInitialCapacityAndLF.put("3", "three");
mapWithInitialCapacityAndLF.put("4", "four");
mapWithInitialCapacityAndLF.put("5", "five");그리고 Map 의 구조를 살펴 보겠습니다 .
이제 맵에 더 많은 항목을 추가해 보겠습니다 .
mapWithInitialCapacityAndLF.put("6", "Six");
mapWithInitialCapacityAndLF.put("7", "Seven");
//.. more entries
mapWithInitialCapacityAndLF.put("15", "fifteen");그리고 Map 구조를 다시 살펴 보겠습니다 .
재해 싱은 복잡성을 낮추는 데 도움이되지만 비용이 많이 드는 프로세스입니다. 방대한 양의 데이터를 저장해야하는 경우 충분한 용량으로 HashMap 을 만들어야합니다 . 이것은 자동 재해 싱보다 더 효율적입니다.
5.3. 충돌
잘못된 해시 코드 알고리즘으로 인해 충돌이 발생할 수 있으며 종종 Map 의 성능이 저하됩니다 .
Java 8 이전에는 Java의 HashMap 이 LinkedList 를 사용하여 맵 항목을 저장 하여 충돌을 처리 합니다. 키가 다른 항목이 이미있는 동일한 버킷에있는 경우 LinkedList 의 헤드에 추가됩니다 . 최악의 경우 복잡성이 O (n)로 증가 합니다.
이 문제를 방지하기 위해 Java 8 및 이후 버전에서는 LinkedList 대신 균형 트리 ( 빨강-검정 트리 라고도 함 ) 를 사용하여 충돌 된 항목을 저장합니다. 이것은 O (n) 에서 O (log n) 까지 HashMap 의 최악의 경우 성능을 향상시킵니다 .
HashMap은 처음에 LinkedList를 사용합니다 . 그런 다음 항목 수가 특정 임계 값을 초과하면 LinkedList 를 균형 잡힌 이진 트리로 바꿉니다 . TREEIFY_THRESHOLD의 일정이 임계 값을 결정한다. 현재이 값은 8입니다. 즉, 동일한 버킷에 8 개 이상의 요소가있는 경우 Map 은 트리를 사용하여 해당 요소 를 보유합니다.
6. 결론
이 기사에서는 가장 인기있는 데이터 구조 중 하나 인 HashMap에 대해 논의했습니다 . 또한 용량과 함께 부하 계수가 성능에 어떤 영향을 미치는지 확인했습니다.