圖解 blind 75: Array & HashTable

前言

本篇主要是介紹這個類型題目所會用到的演算法及資料結構

以下分別針對 Array 與 HashTable 做概念性介紹

Array(陣列)

Array 這種資料結構是用來儲存一整堆或一序列相同類型的資料

當遇到需要處理大量同類型的資料，最常使用 Array 來做處理。

特點是可以快速透過位址來存取每個在陣列中的資料

每個資料都是相鄰擺放，可以透過相對於第一個起始點的位置做位移來存取

HashTable(雜湊表)

HashTable 這種資料結構是透過一個雜湊函數來把資料內容產生一個對應值

然後以對應值作為索引建立一個對應值與原始資料的對應表

因為查詢方式是使用雜湊函數

所以擺放的位置會比較平均，可以加速搜尋對應表的速度

而設計良好的雜湊函數有機會在常數時間複雜度搜尋到其對應的資料

這類資料結構通常可以用來做緩存，避免重複查詢已拜訪過得資料

特別要注意的是，雜湊函數如果設計不夠好可能發生兩個資料出現相同的雜湊對應值

選用具有唯一性的資料特徵值來做雜湊對應是一個比較好的選擇