On Thu, Apr 28, 2011 at 9:13 PM, Robert Dewar <de...@adacore.com> wrote: > I think the hash table is a much better choice than the B+ tree. You > really are much more interested in average case performance in a compiler > than worst case, especially when the worst case will not > happen in practice.
Basically, I agree with you. Hash table is better in most cases, but is not always better, especially on ultra large key set. O(1) is better than O(log(n)), but is not much better. If you have 1 million elements, at most, you only need 20 comparisons. Comparison may be much cheaper than hashing. 20 comparisons may be faster than 1 hashing. -- Chiheng Xu Wuhan,China
