What data structure would have the fastest time for search and insert functions?

The question pretty much says it all, but I'm building a compil开发者_如何学Goer and am trying to decide on what sort of data structure to use for my symbol table. Considering the only functions the symbol table will need is a search and an insert I'd like to use a data structure that can do those as quickly as possible. Any suggestions?

---

Hash tables are very commonly used for this. A simple implementation with N bins and a hash function that takes the sum of the letters in each symbol (mod N) should be very close to O(1) on insert and search.

---

Dictionary/Hashtable has a lookup speed of O(1) if I'm not mistaken.

---

About the hashtable lookup - it's O(1) only if none or few collisions occur - so assuming that you have appropriate hashing function, it's O(1) typically, but under worst circumstances it could end up with O(N). Good estimation of data size is crucial.

And you should also consider time complexity of the hashing function you intend to use