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