1、hashtable
哈希表和數(shù)組、以及鏈表的對比：
(1).數(shù)組的特點(diǎn)：尋址容易，插入和刪除困難；?數(shù)組存儲連續(xù),查找一個元素的時間復(fù)雜度為O(1)；
(2).鏈表的特點(diǎn)：尋址困難，插入和刪除容易。鏈表存儲區(qū)是離散的，遍歷鏈表的元素的時間復(fù)雜度為O(N)。
(3).hash-table是根據(jù)關(guān)鍵值（key-value）來直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，它結(jié)合了數(shù)組和鏈表的優(yōu)點(diǎn)。hash表的難點(diǎn)
??這里是一些聯(lián)系人的信息，如果要存儲這些信息你會怎么做？我們比較直觀的想法是，設(shè)計(jì)一個結(jié)構(gòu)體，用鏈表來存儲。結(jié)構(gòu)體里面包含一個char型數(shù)組存放名字，char字符串存放電話號碼，和一個結(jié)構(gòu)體指針用來存放下個結(jié)構(gòu)體的地址。
- 張三?13980593357??
- 李四?15828662334??
- 王五?13409821234??
- 張帥?13890583472??
張三 13980593357 李四 15828662334 王五 13409821234 張帥 13890583472
當(dāng)要查找”王五 15828662334“這條記錄是否在這張鏈表中時，可能會從鏈表的頭結(jié)點(diǎn)開始遍歷，依次將每個結(jié)點(diǎn)中的姓名同”李四“進(jìn)行比較，直到查找成功或者失敗為止，這種做法的時間復(fù)雜度為O(n)。即使采用二叉排序樹進(jìn)行存儲，也最多為O(logn)。假設(shè)能夠通過”王五“這個信息直接獲取到該記錄在表中的存儲位置，就能省掉中間關(guān)鍵字比較的這個環(huán)節(jié)，復(fù)雜度直接降到O(1)。Hash表就能夠達(dá)到這樣的效果。
Hash表采用一個映射函數(shù) f : key —> address 將關(guān)鍵字映射到該記錄在表中的存儲位置，從而在想要查找該記錄時，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲位置，通常情況下，這種映射關(guān)系稱作為Hash函數(shù)，而通過Hash函數(shù)和關(guān)鍵字計(jì)算出來的存儲位置(注意這里的存儲位置只是表中的存儲位置，并不是實(shí)際的物理地址)稱作為Hash地址。比如上述例子中，假如聯(lián)系人信息采用Hash表存儲，則當(dāng)想要找到“李四”的信息時，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可。
2、RB-tree
R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點(diǎn)上都有存儲位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
紅黑樹的特性:
（1）每個節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
注意：
(01) 特性(3)中的葉子節(jié)點(diǎn)，是只為空(NIL或null)的節(jié)點(diǎn)。
(02) 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
紅黑樹示意圖如下：
