HashMap에서 로드 팩터의 중요성은 무엇입니까?

HashMap에서 로드 팩터의 중요성은 무엇입니까?

HashMap에는 두 중요한.size ★★★★★★★★★★★★★★★★★」load factor자바 문서를 살펴보니0.75f는 초기 부하 계수입니다.하지만 나는 그것의 실제 용도를 찾을 수 없다.

부하율을 설정할 필요가 있는 다양한 시나리오가 무엇이며, 다른 케이스에 대한 이상적인 샘플은 무엇입니까?

문서에서는 다음과 같이 설명하고 있습니다.

HashMap 인스턴스에는 성능에 영향을 미치는 두 가지 매개 변수(초기 용량과 부하 계수)가 있습니다.capacity는 해시 테이블 내의 버킷 수입니다.초기 capacity는 단순히 해시 테이블 작성 시점의 capacity입니다.로드 팩터는 해시 테이블의 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 찰 수 있는지를 나타내는 척도입니다.해시 테이블 내의 엔트리 수가 로드 팩터의 곱과 현재 캐퍼시티를 초과하면 해시 테이블이 재플래시(즉, 내부 데이터 구조가 재구축됨)되므로 해시 테이블에는 버킷 수가 약 2배가 됩니다.

일반적으로 기본 부하 계수(.75)는 시간과 공간 비용 간의 균형을 잘 유지합니다.값이 클수록 공간 오버헤드는 감소하지만 검색 비용은 증가합니다(get 및 put을 포함한 HashMap 클래스의 대부분의 작업에 반영됨).초기 용량을 설정할 때 맵 내의 예상 엔트리 수와 부하 계수를 고려하여 재해시 작업 횟수를 최소화해야 합니다.초기 용량이 최대 엔트리 수를 로드 팩터로 나눈 값보다 클 경우 재해시 작업은 발생하지 않습니다.

모든 성능 최적화와 마찬가지로 너무 빨리(즉, 병목 현상에 대한 하드 데이터 없이) 최적화를 피하는 것이 좋습니다.

" " " "HashMaptakes 16, 0.75f(75%)는 어느 수준인지를 .HashMap용량을 두 배로 늘려야 합니다.

예를 들어 용량과 부하 계수의 곱은 다음과 같습니다.16 * 0.75 = 12의 쌍을 "12" - "12"에 HashMap32번입니다.

실제로 제 계산에 따르면 "완벽한" 부하 계수는 로그 2(~ 0.7)에 가깝습니다.단, 부하계수가 이보다 작을 경우 퍼포먼스가 향상됩니다.75구경은 아마 모자에서 꺼낸 것 같아요

실증:

버킷이 비어 있는지 여부를 예측하여 체인을 피하고 분기 예측을 이용할 수 있습니다.버킷이 비워질 확률이 0.5를 초과할 경우 버킷은 비어 있을 수 있습니다.

사이즈와 n개의 추가된 키의 수를 나타냅니다.이항 정리를 사용하면 버킷이 비워질 확률은 다음과 같습니다.

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

따라서 버킷이 다음 값보다 작을 경우 버킷은 비어 있을 수 있습니다.

log(2)/log(s/(s - 1)) keys

s가 무한대에 도달하고 추가된 키 수가 P(0) = .5인 경우 n/s는 log(2)에 빠르게 접근합니다.

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...

부하율이란?

HashMap이 용량을 늘리기 위해 소모되는 용량의 양입니다.

왜 부하율일까요?

로드 팩터는 기본적으로 초기 용량(16)의 0.75이므로 버킷의 25%는 용량이 증가하기 전에 비워집니다.이것에 의해, 새로운 해시 코드를 포인트로 하는 많은 새로운 버킷이 버킷의 수가 증가한 직후에 존재하게 됩니다.

빈 버킷을 많이 유지해야 하는 이유와 빈 버킷을 유지하는 것이 성능에 미치는 영향은 무엇입니까?

부하 계수를 1.0으로 설정하면 매우 흥미로운 일이 발생할 수 있습니다.

니가 hashCode은 888및 당신의 hashmap에 개체 x을 추가하고 있다.;당신의 hashmap의 버킷은 해시 코드입니다.을 대표하는 자유입니다, 그래서 개체)은 양동이야 하지만 만약 여러분이 hashCode은 또한 888이 bucke 다음 개체는 y확실히 하지만 그 양동이 말일(추가할 것이다 다른 개체는 y를 추가하고 있을 뿐 지금 다시 추가된다.한 tslinked List 실장 이외에는 키, 값 및 next)를 저장하는 실장에서는 퍼포먼스에 영향이 있습니다.이 시점에서 오브젝트 y는 버킷의 선두에 존재하지 않기 때문에 룩업을 실행해도 O(1)가 되지 않습니다.이 시간은 같은 버킷에 있는 항목의 수에 따라 달라집니다.참고로 이것은 해시 충돌이라고 불리며 부하 계수가 1 미만일 때도 발생합니다.

퍼포먼스, 해시 충돌 및 부하 계수와의 상관 관계

• 낮은 하중 계수 = 더 많은 여유 버킷 = 충돌 가능성 감소 = 고성능 = 높은 공간 요구 사항입니다.
• 하중 계수가 높을수록 = 빈 버킷 감소 = 충돌 가능성 높음 = 성능 저하 = 공간 요구 사항 감소.

매뉴얼에서 다음 항목을 참조하십시오.

로드 팩터는 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 찰 수 있는지를 나타내는 척도입니다.

실제로 고객의 특정 요건에 따라 다르며, 초기 부하 계수를 지정하기 위한 "경험의 법칙"은 없습니다.

HashMap DEFAULT_INITIAL_CAPACITY = 16 및 DEFAULT_LOAD_FACTOR = 0.75f의 경우 HashMap = 16 * 0.75 = 12의 모든 엔트리의 최대 수를 의미합니다.13번째 요소가 추가되면 HashMap의 용량(어레이 크기)이 2배가 됩니다!완벽한 일러스트는 이 질문에 대한 답을 제시합니다.이미지는 여기서 가져옵니다.

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

양동이들이 너무 가득 차면, 우리는 그 양동이들을 살펴봐야 합니다.

매우 긴 링크 리스트.

그리고 그것이 요점을 뒤집는 것이다.

여기 4개의 버킷이 있는 예가 있습니다.

해쉬셋에 코끼리와 오소리가 있어요

꽤 괜찮은 상황이죠?

각 요소에는 0 또는 1개의 요소가 있습니다.

이제 HashSet에 두 가지 요소를 추가했습니다.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

이것도 나쁘지 않아요.

모든 양동이에 원소가 하나밖에 없어요. 그래서 내가 알고 싶다면, 여기에 팬더가 들어있나요?

1번 버킷은 금방 볼 수 있는데

거기다가

우리 수집품에는 없는 줄 알았어요.

고양이가 들어있는지 알고 싶으면 양동이를 보고

넘버 3

고양이를 찾아요, 그게 우리 안에 있는지 금방 알 수 있어요.

수집.

코알라를 더하면 어때요? 나쁘지 않네요.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

어쩌면 지금은 1번 버킷에 있는 게 아니라

1개의 요소,

두 개를 봐야겠어요.

하지만 적어도 코끼리, 오소리, 그리고

고양이.

내가 다시 팬더를 찾는다면, 그것은 양동이에만 있을 수 있다.

넘버 1과

수달과 수달 말고는 아무것도 볼 필요가 없어

코알라.

하지만 이제 내가 악어를 1번 양동이에 넣고 넌 할 수 있어

이게 어떻게 돌아가는지 알아봐야지

1번 버킷이 점점 커지고

더 크게, 그리고 기본적으로 모든 것을 살펴봐야 합니다.

찾아야 할 요소들

1번 버킷에 있어야 할 것 같아요

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

다른 버킷에 문자열을 추가하기 시작하면

맞아요, 문제는 점점 더 커져서

싱글 버킷

어떻게 하면 양동이들이 너무 꽉 차는 것을 막을 수 있을까요?

여기서의 해결책은

          "the HashSet can automatically

        resize the number of buckets."

HashSet은 버킷이 다음 정보를 얻는다는 것을 인식합니다.

너무 꽉 찼어요.

이 모든 검색의 이점을 잃고 있습니다.

요소들.

또한 더 많은 버킷(일반적으로 이전보다 2배)을 생성하기만 하면 됩니다.

그런 다음 요소를 올바른 버킷에 넣습니다.

여기에서는, 각각 다른 HashSet 를 실장하고 있습니다.

체인이 되어 있습니다.이제 "자기 크기 조정 해시 세트"를 만듭니다.

이 HashSet은 버킷이 다음 중 하나임을 인식합니다.

너무 배불러서

버킷이 더 필요해요.

loadFactor는 HashSet 클래스의 다른 필드입니다.

load Factor는 평균 요소 수를 나타냅니다.

버킷,

크기를 조정할 수 있습니다.

load Factor는 공간과 시간의 균형입니다.

버킷이 너무 차면 크기를 조정합니다.

물론 시간이 걸리긴 하지만

양동이가 길가에 있는 시간을 절약해당 시간을 절약할 수 있을 겁니다

조금 더 비어있네요.

예를 들어보자.

여기 HashSet이 있습니다.지금까지 4가지 요소를 추가했습니다.

코끼리, 개, 고양이, 물고기.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

이 시점에서 load Factor는

임계값,

버킷당 정상인 평균 요소 수

포함은 0.75입니다.

버킷의 수는 buckets.length로 6입니다.

이 시점에서 HashSet에는 4가지 요소가 있습니다.

현재 사이즈는 4 입니다.

해시 세트의 크기를 조정합니다. 즉, 버킷을 더 추가합니다.

버킷당 평균 요소 수가 다음을 초과할 때

로드 팩터

현재 크기를 buckets.length로 나눈 경우

load Factor보다 큽니다.

이 시점에서 버킷당 평균 요소 수

4 나누기 6 입니다.

원소 4개, 양동이 6개, 0.67입니다.

이는 내가 설정한 임계값 0.75보다 작기 때문에

알았어요.

크기를 조정할 필요가 없습니다.

하지만 이제 우드척을 추가한다고 가정해봅시다.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

우드척은 결국 3번 양동이로 끝날 것이다.

이 시점에서 current Size는 5입니다.

이제 버킷당 평균 요소 수는

current Size를 buckets.length로 나눈 값입니다.

5개의 원소를 6개의 버킷으로 나누면 0.83이 됩니다.

이 값은 load factor(0.75)를 초과합니다.

이 문제에 대처하기 위해서는

양동이를 조금.

더 비어있기 때문에 조작이 예를 들어, 의 유무를 판별하는 것과 같이

버킷 포함

요소가 조금 덜 복잡할 것입니다. 크기를 조정하고 싶습니다.

내 해시 세트

HashSet의 사이즈는 2단계입니다.

먼저 버킷의 수를 두 배로 늘려서 6개의 버킷이 있었는데

이제 12개의 양동이를 가질 거예요.

여기서 0.75로 설정한 load Factor는 그대로 유지됩니다.

하지만 변경된 버킷의 수는 12개입니다.

요소의 수는 5개입니다.

5 나누기 12는 약 0.42로, 이것은 우리의 수보다 훨씬 낮다.

부하 계수,

이제 괜찮아요

하지만 이 요소들 중 일부는 아직 끝나지 않았습니다.

잘못된 양동이로군.

예를 들면 코끼리.

코끼리는 2번 버킷에 있었다. 왜냐하면 코끼리의 수는

코끼리의 등장인물

8이었습니다.

양동이 6개, 8 빼기 6은 2입니다.

그래서 2등이 된 거예요.

하지만 이제 12개의 버킷이 있고 8개의 mod 12는 8입니다.

코끼리는 더 이상 2번 버킷에 속하지 않는다.

코끼리는 8번 양동이에 속한다.

우드척은 어때?

우드척이 이 모든 문제를 일으킨 장본인이다.

우드척은 결국 3번 버킷에 갇혔다.

9 mod 6은 3이기 때문이다.

하지만 지금은 9 mod 12를 사용합니다.

9 mod 12는 9, 우드척은 9번 버킷으로 갑니다.

그리고 이 모든 것의 장점을 볼 수 있습니다.

3번 버킷에는 2개의 요소만 있습니다.이전에는 3개였습니다.

자, 여기 우리의 코드가 있습니다.

HashSet에 별도의 체인을 연결했습니다.

크기를 조정하지 않았습니다.

크기 조정 기능을 사용하는 새로운 구현이 있습니다.

이 코드들은 대부분 똑같아요

우리는 여전히 그 안에 이 물질들이 들어있는지 아닌지를 결정할 것이다.

값은 이미 설정되어 있습니다.

그렇지 않다면, 어떤 양동이인지 알아내야 합니다.

에 들어가야 합니다.

그런 다음 버킷에 추가하고 LinkedList에 추가합니다.

이제 currentSize 필드를 늘립니다.

current Size는 번호를 추적하는 필드입니다.

HashSet에 포함된 요소의 수.

증가시키고 나서 다시 한 번 살펴봅시다.

평균 부하에서

버킷당 평균 요소 수

아래쪽에 있는 분담을 해보겠습니다.

여기에 캐스팅을 좀 해야 할 것 같아요

더블을 얻었다고.

그런 다음 이 평균 부하를 현장 부하와 비교합니다.

로 설정한

예를 들어 이 HashSet을 작성했을 때 0.75는 다음과 같습니다.

로드 팩터

평균 부하가 load Factor보다 클 경우

즉, 버킷당 요소가 너무 많다는 뜻입니다.

평균이고 다시 삽입해야 해요

여기 재삽입하는 방법이 있습니다.

모든 요소

먼저 oldBuckets라는 로컬 변수를 만듭니다.

즉, 현재 버켓이 있는 그대로의 버켓을 말합니다.

모든 것을 크기 조정하기 전에 말이죠

링크 리스트의 새로운 배열을 아직 작성하지 않았습니다.

그냥 버킷 이름을 oldBuckets로 바꾸는 거야

양동이가 우리 반의 밭이었다는 걸 기억하렴, 난 갈 거야.

새 어레이를 만듭니다.

그러나 이것은 두 배나 많은 요소를 가질 것이다.

처음처럼 말이야

이제 실제로 재삽입을 해야 하는데

나는 모든 오래된 양동이를 반복할 것이다.

oldBuckets의 각 요소는 문자열의 LinkedList입니다.

저것은 양동이입니다.

내가 저 양동이를 뒤져서 저 안에 있는 각 요소들을

두레인지

이제 새 버킷에 다시 삽입할 거야

hash Code를 취득합니다.

어떤 지수인지 알아볼게요.

이제 새로운 버킷, 새로운 Linked List를 얻을 수 있습니다.

스트링과

새 양동이에 넣겠습니다.

요약하면 지금까지 살펴본 HashSet은 Linked의 어레이입니다.

목록 또는 버킷.

자기크기 조정 HashSet은 어느 정도의 비율을 사용하여 실현할 수 있습니다.

테이블 사이즈를 n * 1.5 또는 n + (n >> 1)로 하면 분할 없이 0.6666~의 부하율을 얻을 수 있습니다.이것은 대부분의 시스템, 특히 하드웨어에 분할이 없는 노트북 컴퓨터에서는 느린 속도입니다.

언급URL : https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap