Hash Table(雜湊表) VS Binary Search Tree(二元搜尋樹)

資料來源:https://afteracademy.com/blog/binary-search-tree-vs-hash-table

https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/
http://www.cs.uno.edu/~jaime/Courses/2125/ch27f.pdf
https://www.baeldung.com/cs/hash-table-vs-balanced-binary-tree
https://pjchender.dev/dsa/dsa-bst/

介紹:

    ▲哈希表

        哈希表（也稱為哈希映射）是一種數據結構，用於以未排序的方式將鍵映射到值。此處的鍵表示指向我們正在存儲的值的唯一標識符。

        該概念的一個簡單示例是電話簿。想像一下，我們將聯繫人姓名字符串作為鍵，並將他們對應的電話號碼作為我們存儲的數據。然而，計算機不能直接將字符串與數據相關聯，而是與數字相關聯。

        這就是為什麼哈希表電話簿中的每個新條目都需要通過哈希函數來計算索引的原因。然後使用該索引指向我們所有聯繫人數據數組中的一個桶。

        稍後，當我們需要呼叫電話簿中的某人時，我們可以通過散列他們的姓名並找到相應的值來輕鬆檢索他們的號碼。

        這個概念非常有效，但也非常依賴散列函數的選擇。一個完美的函數會將每個鍵分配給一個唯一的桶，但實際上，哈希表實現使用了一個不完美的哈希函數，這可能會導致兩個不同的輸入產生相同的索引。

        在我們的例子中，這意味著兩個名字不同的人會指向同一個電話號碼。這也稱為碰撞，通常使用開放尋址或鏈接等方法來解決。

    ▲自平衡 BST

        如果一棵樹的每個節點最多有兩個孩子，稱為左孩子和右孩子，則該樹稱為二叉樹。

        一個二叉搜索樹是二叉樹，其內部節點每家商店的關鍵，每個人都有兩位傑出的子樹，又通常表示為左 和 右。 此外，每個節點中的鍵都大於節點左子樹中的所有鍵，而小於其右子樹中的鍵。

        這種特殊的結構允許以整齊排序的方式存儲諸如數字之類的數據，但對它的大多數操作所花費的時間與樹的高度成正比。因此，為了使樹的高度盡可能小，可以應用樹旋轉例程。如果存在這樣的例程，則該樹稱為自平衡樹。典型的變體包括 AVL 樹、B 樹、紅黑樹等。

比較：BST 與 HashTable

什麼時候使用哪種數據結構？

    所以我們已經看到了二叉搜索樹和哈希表的區別。現在，這裡出現的問題是我們什麼時候應該使用 BST 而不是 Hash Table，我們應該在哪些地方更喜歡 Hash Table 而不是 BST？我們應該一直使用哈希表，因為插入、刪除和搜索的時間複雜度是 O(1) 還是我們應該使用 BST？

    BST和Hash Table的使用根據情況需要而定。讓我們看看如何！

        01.輸入大小已知：如果輸入大小已知，那麼我們可以使用哈希表並製作一些哈希函數來統一生成密鑰。如果您事先不知道輸入大小，則使用BST。

        02.範圍搜索：如果你想執行範圍搜索，即在一些鍵之間搜索某個鍵，那麼你應該使用二叉搜索樹，因為在二叉搜索樹中，你會忽略那個不可能有答案的子樹。

        03.緩存友好：如果你想做一些緩存友好的應用程序，那麼你應該使用哈希表，因為它需要更少的內存讀取。

        04.哈希函數：哈希函數是哈希表中最重要的部分。因此，如果您的哈希函數可以均勻分配密鑰，那麼您應該使用哈希表。但是如果你發現很難製作一些哈希函數，那麼去二叉搜索樹。

        

    BST 的一些優點

        01.只需執行 BST 的中序遍歷，我們就可以按排序順序獲取所有鍵。這不是哈希表中的自然操作，需要額外的努力。

        02.這樣做為了統計，查找最接近更低和更高的元素，做範圍查詢是容易做到BSTS。像排序一樣，這些操作不是哈希表的自然操作。

        03.與散列相比，BST 易於實現，我們可以輕鬆實現自己定制的 BST。為了實現Hashing，我們通常依賴於編程語言提供的庫。

        03.使用自平衡 BST，所有操作都保證在 O(Logn) 時間內工作。但是對於散列，Θ(1) 是平均時間，某些特定操作可能會很昂貴，尤其是在調整表大小時。