面試官:HashMap默認負載因子0.75和泊松分布有關係嗎

2020-12-05 掘客DIGGKR

我們在看HashMap源碼時，知道HashMap默認的負載因子是0.75。那這個0.75是怎麼來的呢？

通常，加載因子需要在時間和空間成本上尋求一種折中。

加載因子過高：例如為1，雖然減少了空間開銷，提高了空間利用率，但同時也增加了查詢時間成本。

加載因子過低：例如0.5，雖然可以減少查詢時間成本，但是空間利用率很低，同時提高了rehash操作的次數。

在設置初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少rehash操作次數，所以一般在使用HashMap時建議根據預估值設置初始容量，減少擴容操作。

選擇0.75作為默認的加載因子，完全是時間和空間成本上尋求的一種折中選擇

HashMap源碼中有段注釋，如下：

翻譯如下：通常，默認加載因子 (.75) 在時間和空間成本上尋求一種折中。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設置初始容量時應該考慮到映射中所需的條目數及其加載因子，以便最大限度地減少 rehash 操作次數。如果初始容量大於最大條目數除以加載因子，則不會發生 rehash 操作。

有人說負載因子0.75和泊松分布有關係，那是什麼關係呢？

在HashMap的源碼中有這樣一段注釋：

泊松分布公式：

0.75作為加載因子，忽略方差，即X = λt，P(λt = k)，其中t=1，λ=0.5，λt = 0.5，帶入後：

k=0,1,2…可以得出下表：

可以看到當用 0.75 作為加載因子時，桶中元素到達 8 個的時候，概率已經變得非常小，因此每個位置的鍊表長度超過 8 個是幾乎不可能的，因此在鍊表節點到達 8 時才開始轉化為紅黑樹。

加載因子是0.75，決定了桶中元素到達 8 個的時候概率很小，進而轉為紅黑樹；而不是到達 8 個的時候概率很小所以加載因子是0.75。

歡迎小夥伴們留言交流~~

相關焦點

  • 面試官:HashMap加載因子為什麼是0.75?當場懵了
    HashMap的確有很多細節值得我們注意，正如被問到HashMap加載因子為什麼是0.75？，好了廢話不多說，直接上源碼分享。HashMap加載因子是什麼？HashMap的底層結構是哈希表 ，是以鍵值對形式存儲的。
  • HashMap的負載因子為什麼默認是0.75?這篇文章告訴你答案
    HashMap源碼分析（jdk1.8，保你能看懂）一、負載因子的作用對於HashMap的研究，我之前一直停留在考慮源碼是如何實現的，現在當我重新再來看的時候，才發現，系統默認的各種參數值，才是HashMap的精華所在。負載因子是和擴容機制有關的，意思是如果當前容器的容量，達到了我們設定的最大值，就要開始執行擴容操作。
  • Java初學者進階系列:HashMap的容量與性能
    （HashMap是常見的數據結構，也是面試和工作中常用到的數據結構，線下可以使用微通過crazy042438一起單點討論）1.1 Initial Capacity與Load FactorInitial Capacity：初始化容量，它表示HashMap底層的那個數組，也就是Entry數組有多長，這個值默認是16。
  • 看完這篇 HashMap,和面試官扯皮就沒問題了
    因此，如果遍曆元素很重要的話，不要把初始容量設置的太高或者負載因子設置的太低。HashMap 實例有兩個很重要的因素，初始容量和負載因子，初始容量指的就是 hash 表桶的數量，負載因子是一種衡量哈希表填充程度的標準，當哈希表中存在足夠數量的 entry，以至於超過了負載因子和當前容量，這個哈希表會進行 rehash 操作，內部的數據結構重新 rebuilt。
  • 泊松分布
    在這篇文章中，我們將討論用於模擬上述情況的泊松分布背後的理論，如何理解和使用它的公式，以及如何使用Python代碼來模擬它。離散型概率分布這篇文章假設你對概率有一個基本的了解。在我們開始真正的文章之前，我們將建立一些對離散概率分布的理解。
  • 機器學習:泊松分布與指數分布
    打開APP 機器學習：泊松分布與指數分布 阮一峰 發表於 2017-11-29 03:44:03 我舉一個例子，什麼是泊松分布和指數分布
  • 泊松分布與二項分布
    」，大部分的教科書上也都會給出這個收斂過程的數學推導，但是看懂它和真正理解還有很大距離。如果我們學習的意義是為了通過考試，那麼我們大可停留在「只會做題」的階段，因為試卷上不會出現「請發表一下你對泊松公式的看法」這樣的題目，因為那樣一來卷子就變得不容易批改。所以現在的大部分考試都會出一些客觀題。而如果我們學習的目的是為了理解一樣東西，那麼我們就有必要停下來去思考一下諸如「為什麼要有泊松分布？」、「泊松分布的物理意義是什麼？」這樣的「哲學」問題。
  • 搞定HashMap面試,深入講解HashMap的工作原理
    摘要：HashMap是近幾年java面試新秀，出場率高達80%以上，如此高頻的出場不得不讓碼農們慎重其事。但依舊拜倒在它的石榴裙下，讓面試場面一度尷尬。它也是開發中最常用到的key-value數據類型。
  • 史上最全 40 道 Dubbo 面試題及答案,看完碾壓面試官
    1）Spring 配置方式 2）Java API 配置方式 11、Dubbo 核心的配置有哪些？ 我曾經面試就遇到過面試官讓你寫這些配置，我也是蒙逼。。
  • 圖解泊松分布與二項分布之差別
    泊松分布刻畫了稀有事件在一段時間內發生次數這一隨機變量的分布，如電話交換臺單位時間內接到的呼喚次數等。
  • 原創 | 一文讀懂泊松分布,指數分布和伽馬分布
    本文以簡單直白的方式讓大家能夠理解泊松分布，指數分布和伽馬分布的實際含義和作用，並且由此推導其概率密度函數。
  • 如何理解泊松分布?
    公司樓下有家饅頭店：每天早上六點到十點營業，生意挺好，就是發愁一個事情，應該準備多少個饅頭才能既不浪費又能充分供應？老闆統計了一周每日賣出的饅頭（為了方便計算和講解，縮小了數據）：但是，如果把 周二 的七個饅頭放在線段上，分成四段就不夠了：從圖中看，每個時間段，有賣出3個的，有賣出2個的，有賣出1個的，就不再是單純的「賣出、沒賣出」了。不能套用二項分布了。
  • 10分鐘讓你理解泊松分布、指數分布
    我舉一個例子，什麼是泊松分布和指數分布？恐怕大多數人都說不清楚。我可以在10分鐘內，讓你毫不費力地理解這兩個概念。日常生活中，大量事件是有固定頻率的。有可能一下子出生6個，也有可能一個都不出生。這是我們沒法知道的。泊松分布就是描述某段時間內，事件具體的發生概率。
  • 從零開始學統計(五)——泊松分布
    。時，泊松分布近似為正態分布；上面第一條我剛說了，不重複，第二條怎麼理解呢？其實，對於一個總體抽出兩個樣本，樣本量分別為X1和X2，對於T= X1+ X2，一般來說是具有可加性和可乘性的，此時，當兩個樣本的均值分別為
  • 【陸勤筆記】《深入淺出統計學》7幾何分布、二項分布、泊松分布:堅持離散
  • 泊松分布及其實際應用場景
    泊松分布的均值和方差也可以通過二項分布的均值和方差進行推導。在泊松分布中，隨機事件成功的概率p=λ/n，失敗的概率為q=1-λ/n；因為λ/n趨近於0，所以q=1-λ/n趨近於1。正因為在泊松分布中的概率質量函數中只有一個參數，減少了對參數的確定與修改的工作量，構建模型比較簡單，因此具有很重要的實際意義。
  • 簡述泊松分布假設條件
    基礎準備泊松分布概率公式推導自二項分布，因為換一種角度來看待它，它就是二項分布；回顧泊松分布公式推導過程及應用案例請點擊下方連結：
  • 什麼是松泊分布?泊松回歸可以用來做什麼?
    接下來，本文將要介紹的這個回歸模型是專門針對計數數據的泊松回歸模型。泊松分布說到泊松回歸，首先要了解，什麼是泊松分布？首先，利用秒表和計數器，一分鐘過去了，有5個人闖紅燈；第二分鐘有4個人；而下一分鐘有4個人。持續記錄下去，你就可以得到一個模型，這便是「泊松分布」的原型。
  • 為什麼電話呼叫次數服從泊松分布?
    這裡，我們來討論一下泊松分布在電話呼叫中心資源配置中的應用。Poisson分布(法語：loi de Poisson，英語：Poisson distribution，譯名有泊松分布、普阿松分布、卜瓦松分布、布瓦松分布、布阿松分布、波以松分布、卜氏分配等)，是一種統計與概率學裡常見到的離散機率分布(discrete probability distribution)，由法國數學家西莫恩·德尼·泊松(Siméon-Denis Poisson)在1838
  • 六西格瑪管理基礎-常用離散分布之-泊松分布
    ，取這些值的概率為：此時，稱X服從泊松分布。「入」是泊松分布的重要參數，它給出了產品的平均不合格項數。泊松分布的數學期望-均值、方差、標準差由下面的公式給出。泊松分布的圖形表示如下當二項分布的n很大而p很小時，泊松分布可作為二項分布的近似，其中λ為np。通常當n≧20,p≦0.05時，就可以用泊松公式近似計算。