哈希表（初步認(rèn)識哈希表）
哈希表（Hash table谓苟，也叫散列表）
是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄卑笨，以加快查找的速度仑撞。
關(guān)鍵碼值(Key value)也可以當(dāng)成是key的hash值，這個映射函數(shù)叫做散列函數(shù)
存放記錄的數(shù)組叫做散列表座舍。
Hash table需要自定義的內(nèi)容：
散列函數(shù)與散列表大小
hash 沖突的解決方案
裝填因子：為什么需要這個值陨帆？因為數(shù)據(jù)越接近數(shù)組最大值，可能產(chǎn)生沖突的情況就越多
特點：
數(shù)組(順序表)：尋址容易
鏈表：插入與刪除容易
哈希表：尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)缺點：
擴(kuò)容需要消費大量的空間和性能應(yīng)用：電話號碼纲爸，字典缩焦，點歌系統(tǒng)，QQ盖桥，微信的好友等
設(shè)計：
java1.8之前： 拉鏈法
從java1.8開始：當(dāng)鏈表長度超過閾值揩徊，就轉(zhuǎn)換成紅黑樹
關(guān)于哈希表的詳細(xì)介紹和分析塑荒，等樹的內(nèi)容介紹完成以后再介紹
樹的基礎(chǔ)介紹
樹：是n(n>=0)個節(jié)點的有限集姜挺，n=0時候稱為空樹。在任意一棵非空樹中：
1.有且僅有一個特定的稱為根的結(jié)點凌箕；
2.當(dāng)n>1時,其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,....TM词渤，其中每一個集合本身又是一棵樹缺虐，并且稱為根的子樹；
樹的一些概念介紹：
結(jié)點擁有的子樹稱為結(jié)點的度慧妄；
度為0的節(jié)點稱為葉子結(jié)點或終端結(jié)點，度不為0的結(jié)點稱為非終端結(jié)點或者分支結(jié)點韧掩；
除根節(jié)點以外窖铡，分支節(jié)點也稱為內(nèi)部結(jié)點费彼；
樹的度是樹內(nèi)各結(jié)點的度的最大值口芍；
image.png節(jié)點的層次：從根開始定義起鬓椭，根為第一層，根的孩子為第二層翘瓮。若某結(jié)點在第一層资盅，則其子樹的根就在1+1層踊赠。其雙親在同一層的結(jié)點互為堂兄弟。樹中結(jié)點最大層次稱為樹的深度或高度今穿。
image.png
樹的存儲結(jié)構(gòu)：
1.雙親表示法：
image.png2.孩子表示法：
image.png3.雙親孩子表示法：
把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作為存儲結(jié)構(gòu)鸽斟，
則n個結(jié)點有n個孩子鏈表富蓄，如果是葉子結(jié)點則此單鏈表為空，
然后n個頭指針又組成一個線性表灭红，采用順序存儲結(jié)構(gòu)，存放在一個一維數(shù)組中
image.png4.孩子兄弟表示法:
孩子兄弟表示法為每個節(jié)點設(shè)計三個域：
一個數(shù)據(jù)域君珠，一個該節(jié)點的第一個孩子節(jié)點域策添，一個該節(jié)點的下一個節(jié)點的兄弟指針域
image.png
二叉樹
斜樹：二叉樹：Binary Tree 是n(n>=0)個結(jié)點的有限集合唯竹，n=0時候稱為空二叉樹苦丁。
在任意一棵非空二叉樹中：一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹产上。
二叉樹的存儲結(jié)構(gòu):
1.順序存儲：使用的不多，不做多余討論
2.鏈?zhǔn)酱鎯Γ?div id="p54y4ns" class="image-package">image.png
