什麼樣的數據結構能夠以最快的速度進行搜索和插入功能？

這個問題幾乎說明了這一切，但我正在構建一個編譯器，並試圖決定用於我的符號表的什麼樣的數據結構。考慮到符號表所需的唯一功能是搜索和插入，我希望使用可以儘快完成這些操作的數據結構。有什麼建議麼？什麼樣的數據結構能夠以最快的速度進行搜索和插入功能？

2010-02-21 adhanlon

Hash tables非常常用於此。使用N分箱和採用每個符號中的字母總和（模N）的散列函數的簡單實現在插入和搜索時應該非常接近O（1）。

2010-02-21 22:48:13

散列函數你的建議是很壞的哈希函數的複雜性，它使所有字謎碰撞。系統散列函數會更好（如果OP最喜歡的語言中有一個）。 – 2010-02-21 23:01:33

我將不得不找出一個更好的散列函數來使用，但散列表似乎是符號表的方式。 – adhanlon 2010-02-21 23:04:57

任何人都知道標準模板庫的SET容器如何以符號表的形式執行？ – adhanlon 2010-02-21 23:14:37

Dictionary/Hashtable如果我沒有弄錯，查找速度爲O（1）。

2010-02-21 22:46:33

關於散列表查找 - 只有在沒有或幾個衝突發生時纔是O（1） - 所以假設您有適當的散列函數，它通常是O（1），但在最糟糕的情況下，它可能會以O（N ）。對數據大小的良好估計至關重要。

而且你還要考慮時間，你打算使用

2010-11-06 22:56:08 PJK

回答