3

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
2
  • <snarky>Just ask Morgan Freeman</snarky> Feb 13, 2009 at 22:09
  • <very serious>I did, but he didn't know either.</very serious> Feb 13, 2009 at 22:29

1 Answer 1

6

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.

2
  • Nice job explaining that, Rob.
    – Ken White
    Feb 14, 2009 at 3:39
  • Great answer, this is probably the best answer for anything I've asked on Stack Overflow. Feb 16, 2009 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.