views:

407

answers:

1

I've been using the TBucketList and TObjectBucketList for all my hashing needs, but never experiemented with switching the number of buckets. I vaguely remember what this means from Data Structures class, but could someone elaborated on the nuances of this particular class in Delphi

The following table lists the possible values:

Value   Number of buckets

bl2   2
bl4   4
bl8   8
bl16     16
bl32     32
bl64     64
bl128   128
bl256   256
+4  A: 

TBucketList and TObjectBucketList store pointers. The hash function they use simply masks out the upper bits of the address. How many bits get masked out depends on how many buckets the object has. If you use bl2, for example, 31 bits get masked out and only one bit of the address determines the bucket. With bl256, an entire byte of the pointer gets used. It's one of the middle two bytes. The trade-off is simply the number of buckets you'll have. A bucket only takes eight bytes, so having 256 of them isn't a huge cost.

Aside from that, TBucketList is just an ordinary hash table like you learned about in your data-structure class.

TIntegerBucketList uses the same hash function as the others. If you want a more sophisticated hash function, write a descendant of TCustomBucketList and override the BucketFor method. In your descendant class, you can also assign the protected BucketCount property to use something other than the counts provided by TBucketList. Note that the class makes no effort to redistribute items due to a change in the bucket count, so don't re-assign BucketCount after items have already been added to the list unless you plan to do the redistribution yourself.

Rob Kennedy
Nice job explaining that, Rob.
Ken White
Great answer, this is probably the best answer for anything I've asked on Stack Overflow.
Peter Turner