大家好，大家好，我是寫代碼成bug的大頭菜。 公眾號：大頭菜科技()。 原創不易，但歡迎轉載。
前言
有網友指出，在《面試Java——收斂之和》一文中，至于為什么是8，還可以加上一句符合泊松分布的句子。 所以我了解泊松的發表后，確實和網友說的一致。 同時也非常感謝這位網友指出了文章中的缺陷。 在接下來的內容中，大頭菜將嘗試使用泊松分布來演示為什么鏈表成為樹的閾值是8。
泊松分布
首先，什么是泊松分布？
維基百科官網解釋：
泊松布（法語：loi de，英語：）又稱為散布、帕森布、布瓦松布、泊松布、泊松布、泊松布、布散布、派松小數定律（小定律），是一種常見的離散概率分布統計與概率論，由法國數學家西蒙·丹尼斯·泊松于 1838 年發表。
泊松分布適合描述單位時間內發生的隨機事件數量的概率分布。 例如，某個服務設施在一定時間內收到的服務請求數、電話交換機接到的呼叫數、公交車站的乘客數、機器故障數、自然數等。災難、DNA序列突變的數量、放射性、原子核的衰變數量、激光的光子數量傳播等。
泊松分布的概率質量函數為：
讓我簡單總結一下：泊松分布描述了單位時間內發生的獨立事件的數量。
舉個簡單的例子讓大家熟悉一下：
例如：平均每小時有3個嬰兒在醫院出生。 下一小時內將有多少個嬰兒出生？
可能有6個出生，也可能沒有出生。 這是我們無從知曉的事情。
如果嘗試用泊松分布來表示：等號右邊，P代表概率，N代表某種函數關系，t代表時間，n代表數量什么是閾值，1小時內出生3個嬰兒的概率為表示為 P(N(1) = 3)。 等號左邊，λ表示事件發生的頻率。
未來兩個小時內沒有嬰兒出生的概率是0.25%，這根本就是不可能的。
接下來的一個小時內最多有兩個嬰兒出生的概率是 80%。
泊松分布的形狀大致如上圖所示。
可以看到，在頻率附近，事件發生的概率最高，然后向兩側對稱下降，即變大變小的可能性變小。 如果每小時出生三個嬰兒，這是最有可能的結果什么是閾值，出生的嬰兒越多或越少，這種可能性就越小。
讀完示例后，您應該對泊松分布有一個粗略的了解。 接下來，我們嘗試使用泊松分布來分析鏈表到樹。
為什么鏈表轉樹的閾值是8？
根據泊松分布：單位時間內發生的獨立事件的數量。
按鍵碰撞問題，每次按鍵碰撞可以被認為是一個獨立的事件。 與上次按鍵沖突還是下次按鍵沖突無關。
因此，用泊松分布嘗試表達：P代表概率，N代表某種函數關系，t代表時間，n代表數量，每1秒密鑰傳輸碰撞次數為k，表達為P(N( 1) = k )。 等號左邊，λ表示事件發生的頻率。 密鑰發生沖突的概率為 0.5。
將相應的值代入泊松分布公式：
$P(N(1)=k) = 0.6065*(0.5^k)/k!$
是不是發現上面的后果有點眼熟：
對比文字：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million當k=9時，即碰撞次數為9時，概率為3億，碰撞概率有限接近于0。
如果設置為9，則意味著幾乎不會發生碰撞。 換句話說，現在鏈表的長度是8，碰撞只會從鏈表變成樹。 但它永遠不會成為一棵樹，因為概率太小了。 所以設置為9確實沒有必要。
這就是為什么鏈表成為樹的閾值是8。
參考資料
非常感謝您閱讀本文。 如果您覺得文章寫得不錯，請關注、點贊、分享（對我來說非常有用）。
如果您覺得文章需要改進，非常期待您對我的建議，請留言。
如果您有什么想看的，我很樂意聽取您的意見。
您的支持和支持是我創作最大的能量源泉！