On 4/28/2011 8:55 AM, Richard Guenther wrote:
It seems to me that hash table in GCC is more like mapping(or
dictionary, or associated array, or function(Key->Value)), instead of
containter.
I think the main problem of hash table is that conflict rate is
unpredictable, so the lookup time is unpredictable. At it's worst
condition, you will run equal method on all the elements to find a
slot.
Perhaps using B+ tree to implement mapping may be an alternative.
Using hash table , you should implement hash and equal methods. Using
B+ tree, you should only implement compare method. Using B+ tree, the
time complexity of lookup is O(log(n)), which is much better.
Well, with a good hash-function your average lookup complexity is O(1)
which is much better.
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.
Richard.
