一、哈希和紅黑樹基本原理

創(chuàng)新互聯(lián)主要從事網(wǎng)頁(yè)設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、響應(yīng)式網(wǎng)站建設(shè)、程序開發(fā)、網(wǎng)站優(yōu)化、微網(wǎng)站、微信小程序定制開發(fā)等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷經(jīng)驗(yàn)，集策劃、開發(fā)、設(shè)計(jì)、營(yíng)銷、管理等多方位專業(yè)化運(yùn)作于一體。

哈希（hash）也稱散列，通過散列算法變成固定的輸出到數(shù)組，所有的線性數(shù)據(jù)結(jié)構(gòu)中，數(shù)組的定位速度最快，因?yàn)樗赏ㄟ^數(shù)組下標(biāo)直接定位到相應(yīng)的數(shù)組空間，就不需要一個(gè)個(gè)查找。

紅黑樹的自旋是天才的設(shè)計(jì)，是一種特殊的平衡二叉樹數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)也是從幾十萬(wàn)的數(shù)據(jù)里面幾步就能查找到，速度快。

二、使用場(chǎng)景

1、速度對(duì)比
物聯(lián)網(wǎng)可能是數(shù)百萬(wàn)設(shè)備或者用戶聯(lián)網(wǎng)，對(duì)高并發(fā)要求很大，所以，對(duì)網(wǎng)絡(luò)安全產(chǎn)品第一要求的是性能和速度?？傮w來說，哈希查找速度會(huì)比紅黑樹快，而且查找速度基本和數(shù)據(jù)量大小無關(guān)，屬于常數(shù)級(jí)別;而RB樹的查找速度是log(n)級(jí)別。
紅黑樹查找和刪除的時(shí)間復(fù)雜度都是O(logn)，Hash查找和刪除的時(shí)間復(fù)雜度都是O(1)。 如果紅黑樹的樹高度不深如小于8，采用的是數(shù)字查找，兩者性能沒有太多的差異。
也就是并非所有的場(chǎng)景，哈希都比紅黑樹快，要看代碼的優(yōu)化程度。hihttps使用的linux高并發(fā)EPOLL模式事件管理，就是紅黑樹。

2、數(shù)據(jù)預(yù)知
靜態(tài)數(shù)據(jù)，可以基本預(yù)知大小，用哈希。如t初始化的規(guī)則就幾百條在可控范圍內(nèi)，另外TOPIC黑白名單、URL地址等也不會(huì)太多，也是用的哈希就可以了。
動(dòng)態(tài)數(shù)據(jù)，如統(tǒng)計(jì)IP地址、任務(wù)調(diào)度、epoll高并發(fā)事件管理，無法判斷多少，可能很少，也可能巨多，用紅黑樹更佳。當(dāng)然，如果大概知道設(shè)備IP地址數(shù)量在一定范圍，如只有幾千，完全也可以用哈希。

3、內(nèi)存消耗
對(duì)內(nèi)存要求嚴(yán)格的地方，如嵌入式系統(tǒng)，用紅黑樹。紅黑樹占用的內(nèi)存更小（僅需要為其存在的節(jié)點(diǎn)分配內(nèi)存），而哈希事先就應(yīng)該分配足夠的內(nèi)存存儲(chǔ)散列表，浪費(fèi)內(nèi)存。
對(duì)內(nèi)存消耗無所謂的地方，如服務(wù)器有巨大的內(nèi)存，用哈希。哈希大的缺點(diǎn)是內(nèi)存分配得小，可能元素就會(huì)沖突，沖突的元素大于8個(gè)成鏈表，效率還不如紅黑樹。 Java 的hashmap就是把哈希和紅黑樹結(jié)合在以前的。當(dāng)同一個(gè)hash值的節(jié)點(diǎn)數(shù)不小于8時(shí)，不再采用單鏈表形式存儲(chǔ)，而是采用紅黑樹。

4 復(fù)雜程度
哈希更簡(jiǎn)單，紅黑樹算法復(fù)雜一點(diǎn)，不過這都不是事，大神早開源了很多穩(wěn)定的版本。

三、應(yīng)用場(chǎng)景總結(jié)
紅黑樹是有序的，哈希是無序的，根據(jù)項(xiàng)目需求來選擇，阿里巴巴的很多項(xiàng)目用紅黑樹更多，筆者認(rèn)為主要還是和內(nèi)存有關(guān)，如果內(nèi)存要求苛刻的項(xiàng)目，就用紅黑樹；如果內(nèi)存足夠大，犧牲內(nèi)存換取更快的速度，哈希完全適合。
Hiihttps開源waf大量采用哈希算法，可能和速度并發(fā)要求有關(guān)。總之，數(shù)據(jù)結(jié)構(gòu)是網(wǎng)絡(luò)安全最基礎(chǔ)的學(xué)科。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章名稱：紅黑樹和哈希表的區(qū)別-創(chuàng)新互聯(lián)
新聞來源：http://www.rwnh.cn/article4/djpiie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、用戶體驗(yàn)、移動(dòng)網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)