Как оценить количество сегментов для TBucketList

Question

Я использовал TBucketList и TObjectBucketList для всех своих нужд хеширования, но никогда не экспериментировал с переключением количества сегментов. Я смутно помню, что это значит для класса Data Structures, но кто-то мог бы подробно остановиться на нюансах этого конкретного класса в 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

Answer 1

TBucketList и TObjectBucketList указатели магазина. Используемая ими хеш-функция просто маскирует верхние биты адреса. Сколько битов маскируется, зависит от того, сколько сегментов имеет объект. Например, если вы используете bl2, 31 бит будет замаскирован, и только один бит адреса определяет сегмент. При bl256 используется целый байт указателя. Это один из двух средних байтов. Компромисс - это просто количество ведер, которые вы будете иметь. Ведро занимает всего восемь байтов, поэтому иметь 256 из них - это не огромные затраты.

Кроме того, TBucketList - это обычная хеш-таблица, о которой вы узнали в своем классе структуры данных.

TIntegerBucketList использует ту же хеш-функцию, что и остальные. Если вам нужна более сложная хеш-функция, напишите потомок TCustomBucketList и переопределите метод BucketFor. В своем классе-потомке вы также можете назначить защищенное свойство BucketCount, чтобы использовать что-то отличное от значений, предоставляемых TBucketList. Обратите внимание, что класс не прилагает усилий для перераспределения элементов из-за изменения количества сегментов, поэтому не назначайте повторно BucketCount после того, как элементы уже были добавлены в список, если вы не планируете делать это самостоятельно.