The question pretty much says it all, but I'm building a compiler 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?
views:
160answers:
3
+1
A:
Dictionary/Hashtable has a lookup speed of O(1) if I'm not mistaken.
Mike Trpcic
2010-02-21 22:46:33
+2
A:
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.
Robert Karl
2010-02-21 22:48:13
The hash function you suggest is rather bad, it makes all anagrams collide. The system hash function would be better (if there is one in the OP's favorite language).
Pascal Cuoq
2010-02-21 23:01:33
I'll have to figure out a better hash function to use, but a hash table does seem to be the way to go with a symbol table.
Silmaril89
2010-02-21 23:04:57
Anyone know how well the standard template library's SET container would perform as a symbol table?
Silmaril89
2010-02-21 23:14:37