Re: [boost] portable hash_map

From: Matt Austern (austern_at_[hidden])
Date: 2001-03-05 15:50:37

Beman Dawes wrote:
> 
> At 11:27 AM 3/5/2001 -0800, Matt Austern wrote:
> 
>  > - I might have an new idea that will permit fast iteration
>  >   without giving up any of the other desirable properties:
>  >   have a single slist for all the elements, and then have
>  >   a separate vector of slist iterator pairs for the buckets.
>  >   My new insight is that elements in that single slist do
>  >   not have to appear in bucket order.  I don't know why that
>  >   didn't occur to me before today.
> 
> Please remember that hash lists used for speed efficiency (at low loading
> factors), space efficiency (at high loading factors), and speed-space
> efficiency blends (at moderate loading factors).
> 
> So doing something that adds even one additional pointer per bucket (to
> speed iteration) impacts some uses.

Agreed.  I have a vague idea that I can do this without affecting
performance in other respects, but I'll have to work through it
to make sure that I'm right.

Certainly, iteration speed is one of the least important aspects
of hashtable performance.  If this change affects lookup speed,
I won't do it.

                        --Matt