題組內容

二、R（A,B,C,D,E,F,H,I）為一個含有A、B、C、D、E、F、H、I八個屬性，且符合1NF（firstnormalform）要求之關聯表格。該表格有五個功能相依（FunctionalDependency）：AB→F;A→E;B→H;BC→I;C→D。

三、資料庫中，採用雜湊法索引及採用循序檔之資料結構，以儲存資料檔案時，對兩者⑴在最壞的資料找尋時間上，⑵在儲存空間的利用率上， ⑶資料是否需事先經過排序，⑷是否適合建構在linkedlist資料結構下作業等方面，進行比較。（20分）

詳解提供者：Phil(112高普雙榜)

其比較如下-

	雜湊法索引	循序檔
最壞的資料尋找時間	最差情況為所尋找資料不存在於bucket中，時間複雜度為O(n)，n為bucket大小。	最差情況為所尋找的資料不存在於數列中，時間複雜度為O(n)，n為數列的數量。
儲存空間利用率	需視碰撞後的處理策略而定，在最差的情況下，輸入的資料跟每一筆已儲存的資料都發生碰撞。	較佳，由於資料儲存時是依序儲存，因此其儲存空間利用率較高。
資料是否需事先排序	無需事先排序，因為是利用雜湊函數進行運算	在儲存需要有效率的前提下，資料需事先排序
是否適合建構在Linked List上	適合，在完美雜湊的前提下，使用Linked List會更快地找到所需資料。	不適合，因為循序檔需要從頭開始搜尋，使用Linked List會大幅降低搜尋效率，且需花費額外空間儲存指標。

詳解提供者：hchungw

在資料庫中，採用雜湊法索引（Hash Index）和循序檔（Sequential File）來儲存資料檔案時，這兩種方法在各方面都有不同的特性和適用場景。以下是對這兩種資料結構在四個方面的比較：

雜湊法索引：
- 最壞情況：O(n)（在發生大量碰撞的情況下）。
- 雜湊法索引通常能夠在O(1)的時間內找到資料，這是因為雜湊函數將資料直接映射到特定位置。然而，在最壞情況下，如果雜湊函數設計不佳或存在大量碰撞，找尋時間可能變成O(n)。
循序檔：
- 最壞情況：O(n)。
- 循序檔的資料按順序存儲，最壞情況下需要進行線性搜索，因此最壞的找尋時間是O(n)。

雜湊法索引：
- 雜湊法通常需要額外的空間來處理碰撞（例如鏈接地址法需要指針，開放定址法需要空槽），因此儲存空間的利用率會受到一定影響。此外，當哈希表變得很大時，未使用的槽位也會佔用空間。
循序檔：
- 循序檔不需要額外的空間來處理碰撞，儲存空間的利用率通常較高。數據是順序存儲的，並且沒有額外的空位，因此空間利用率通常更高。

雜湊法索引適合快速存取和插入的情況，但可能需要更多的儲存空間來處理碰撞。循序檔適合於順序存取和批量處理，但插入和查找的最壞情況效率較低，且要求數據事先排序。兩者的選擇取決於具體的應用需求和資料特性。