[Insight-developers] hash_map

[Joshua Cates]

Hi Brad, 

WatershedImageFilter uses hash_map vs map for speed (average constant time
access versus log time access).  Also, the stl map sorts its elements.
The algorithm depends pretty heavily on the hash table data structures.

My feeling is that a good hash table implementation should dynamically
manage its bucket count for efficiency.  I'm assuming that the stl
implentation does this?    The order of iteration is arbitrary in a hash
table since it is by definition unordered.  So iteration should proceed by
the fastest path.

Josh.

______________________________
 Josh Cates			
 School of Computer Science	
 University of Utah
 Email: cates@cs.utah.edu
 Phone: (801) 587-7697
 URL:   www.cs.utk.edu/~cates


On Tue, 27 Feb 2001, Brad King wrote:

> Hello all,
> 
> We at Kitware have discussed various approaches to a hash table, and have
> decided that it would be best to add an STL hash_map implementation to
> Insight's repository.  Our problem is that the SGI implementation of the
> hash_map header is interdependent on most of the rest of SGI's stl
> implementation, and cannot be included alone without a large amount of
> hacking.  If someone would like to volunteer to take the time to do this,
> the job is yours.
> 
> I'm asking the list for opinions and arguments about a hash table
> implementation.  Is it worth adding one now?  Does WatershedImageFilter
> depend heavily on a hash table, or would the stl map suffice?
> 
> There are many design decisions to make in writing a generic hash
> table.  Does it automatically expand the bucket count when the load factor
> is too high?  In what order do iterators move across the buckets and their
> contents?  What is the implementation in each bucket, an stl list?
> 
> I'd like to get some discussion started about this so we can determine now
> what is best for the project.
> 
> -Brad
> 
> 
> _______________________________________________
> Insight-developers mailing list
> Insight-developers@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-developers
>