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