Как я могу избежать нехватки памяти с растущим TDictionary? - PullRequest
Новая
       13

Как я могу избежать нехватки памяти с растущим TDictionary?

8 голосов
/ 02 декабря 2011

TDictionary<TKey,TValue> использует внутренний массив, который удваивается, если он заполнен: 

newCap := Length(FItems) * 2;
if newCap = 0 then
  newCap := 4;
Rehash(newCap);

Это хорошо работает со средним числом элементов, но если он достигает верхнего предела, это очень неудачно, потому чтоон может вызвать исключение EOutOfMemory, даже если почти половина доступной памяти все еще доступна.

Есть ли способ повлиять на это поведение?Как другие классы коллекций справляются с этим сценарием?

1 Ответ

9 голосов
/ 02 декабря 2011

Вы должны понимать, как работает словарь.Словарь содержит список «хэш-блоков», в которые помещаются вставляемые вами элементы.Это конечное число, поэтому, как только вы его заполните, вам нужно распределить больше сегментов, и нет никакого способа обойти это.Поскольку назначение объектов в сегменты основано на результате хеш-функции, вы не можете просто добавить сегменты в конец массива и поместить туда вещи, вам нужно перераспределить весь список блоков,перешифруйте все и поместите его в (новые) соответствующие сегменты.

При таком поведении единственный способ сделать словарь не перераспределить после заполнения, это убедиться, что он никогданаполняетсяЕсли вы знаете количество элементов, которые вы вставите в словарь, передайте его в качестве параметра конструктору, и все будет готово, перераспределения словаря больше не будет.

Если вы не можете этого сделать (вы нене знаю, сколько элементов у вас будет в словаре) вам нужно пересмотреть то, что заставило вас сначала выбрать TDictionary и выбрать структуру данных, которая предлагает лучший компромисс для вашего конкретного алгоритма.Например, вы можете использовать двоичные деревья поиска, поскольку они выполняют балансировку, вращая информацию в существующих узлах, без необходимости перераспределения ever .

...