2）哈希表的基本操作？

寫(xiě)入：O(1)、讀取：O(1)、擴(kuò)容O(n)。

3）什么是哈希函數(shù)？

哈希表本質(zhì)上是一個(gè)數(shù)組，只是數(shù)組只能根據(jù)下標(biāo)，像a[0] a[1] a[2] a[3] 這樣來(lái)訪問(wèn)，而哈希表的key則是以字符串類型為主的。

通過(guò)哈希函數(shù)，我們可以把字符串或其他類型的key，轉(zhuǎn)化成數(shù)組的下標(biāo)index。

如給出一個(gè)長(zhǎng)度為8的數(shù)組，則：

當(dāng)key=001121時(shí)，

index = HashCode ("001121") % Array.length = 7

當(dāng)key=this時(shí)，

index = HashCode ("this") % Array.length = 6

4）什么是哈希沖突？

不同的key通過(guò)哈希函數(shù)獲得的下標(biāo)有可能是相同的，例如002936這個(gè)key對(duì)應(yīng)的數(shù)組下標(biāo)是2，002947對(duì)應(yīng)的數(shù)組下標(biāo)也是2，這種情況就是哈希沖突。

5）如何解決哈希沖突？

開(kāi)放尋址法：例子Threadlocal。

6 樹(shù)

1）什么是樹(shù)？

樹(shù)（tree）是n（n≥0）個(gè)節(jié)點(diǎn)的有限集。

當(dāng)n=0時(shí)，稱為空樹(shù)。在任意一個(gè)非空樹(shù)中，有如下特點(diǎn)：

• 有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)。
• 當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集，每一個(gè)集合本身又是一個(gè)樹(shù)，并稱為根的子樹(shù)。

2）樹(shù)的遍歷？

（1）深度優(yōu)先

前序：根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)。

中序：左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)。

后序：左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)。

實(shí)現(xiàn)方式：遞歸或棧。

（2）廣度優(yōu)先

層序：一層一層遍歷。

實(shí)現(xiàn)方式：隊(duì)列。

7 二叉樹(shù)

1）什么是二叉樹(shù)?

二叉樹(shù)（binary tree）是樹(shù)的一種特殊形式。二叉，顧名思義，這種樹(shù)的每個(gè)節(jié)點(diǎn)最多有2個(gè)孩子節(jié)點(diǎn)。注意，這里是最多有2個(gè)，也可能只有1個(gè)，或者沒(méi)有孩子節(jié)點(diǎn)。

2）什么是滿二叉樹(shù)?

一個(gè)二叉樹(shù)的所有非葉子節(jié)點(diǎn)都存在左右孩子，并且所有葉子節(jié)點(diǎn)都在同一層級(jí)上，那么這個(gè)樹(shù)就是滿二叉樹(shù)。

3）什么是完全二叉樹(shù)?

對(duì)一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，按層級(jí)順序編號(hào)，則所有節(jié)點(diǎn)的編號(hào)為從1到n。如果這個(gè)樹(shù)所有節(jié)點(diǎn)和同樣深度的滿二叉樹(shù)的編號(hào)為從1到n的節(jié)點(diǎn)位置相同，則這個(gè)二叉樹(shù)為完全二叉樹(shù)。

8 二叉查找樹(shù)

1）什么是二叉查找樹(shù)？

二叉查找樹(shù)在二叉樹(shù)的基礎(chǔ)上增加了以下幾個(gè)條件：

• 如果左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值。
• 如果右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。
• 左、右子樹(shù)也都是二叉查找樹(shù)。

2）二叉查找樹(shù)的作用？

• 查找==》二分查找。
• 排序==》中序遍歷。

3）二叉樹(shù)的實(shí)現(xiàn)方式？

• 鏈表。
• 數(shù)組：對(duì)于稀疏二叉樹(shù)來(lái)說(shuō)，數(shù)組表示法是非常浪費(fèi)空間的。

9 二叉堆

1）什么是二叉堆？

二叉堆是一種特殊的完全二叉樹(shù)，它分為兩個(gè)類型：最大堆和最小堆。

• 最大堆的任何一個(gè)父節(jié)點(diǎn)的值，都大于或等于它左、右孩子節(jié)點(diǎn)的值。
• 最小堆的任何一個(gè)父節(jié)點(diǎn)的值，都小于或等于它左、右孩子節(jié)點(diǎn)的值。

2）二叉堆的基本操作？

（1）插入：插入最末，節(jié)點(diǎn)上浮。

（2）刪除：刪除頭節(jié)點(diǎn)，尾節(jié)點(diǎn)放到頭部，再下沉。

（3）構(gòu)建二叉堆：二叉樹(shù)==》二叉堆，所有非葉子節(jié)點(diǎn)依次下沉。

3）二叉堆的實(shí)現(xiàn)方式？

數(shù)組：