ВЫПОЛНЕНИЕ ПАРАЛЛЕЛЬНОГО ПОВТОРНОГО ХЭШИРОВАНИЯ ХЕШ-ТАБЛИЦЫ ДЛЯ МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ

1. Способ, содержащий:
выделяют второе количество сегментов для хеш-таблицы, совместно одновременно используемой множеством потоков, хеш-таблица, имеющая первое количество сегментов, второе количество сегментов, по меньшей мере, равное первому количеству сегментов, и каждый из второго количества сегментов логически отображают на соответствующий родительский один из первого или второго количества сегментов; и
публикуют обновленную емкость хеш-таблицы, включая в себя первое и второе количество сегментов, в которых выделение закончено, путем публикации обновленной емкости и без выполнения повторного хеширования элементов содержания первого количества сегментов.
2. Способ по п.1, дополнительно содержащий: выполняют проверку, не блокируя сегмент, чтобы определить, необходимо ли повторное хеширование.
3. Способ по п.1, дополнительно содержащий: затем выполняют повторное хеширование элементов содержания первого сегмента из первого количества сегментов до второго сегмента второго количества сегментов, выполняя операцию поиска для пары данных, присутствующей в первом сегменте.
4. Способ по п.1, дополнительно содержащий: вычисляют индекс сегмента, используя обновленную емкость, получают доступ к сегменту, используя индекс сегмента, определяют, что сегмент не был повторно хеширован, и рекурсивно вычисляют родительский индекс сегмента для родительского сегмента, пока повторно хешированный корневой сегмент не будет найден, на который сегмент логически отображает, используя обновленную емкость.
5. Способ по п.4, дополнительно содержащий: выполняют повторное хеширование, по меньшей мере, части элементов содержания повторно хешированного корневого сегмента до сегмента во время выполнения или до выполнения поиска пары данных запроса поиска.
6. Способ по п.5, дополнительно содержащий: устанавливают частичный индикатор повторного хеширования, когда только часть элементов содержания корневого сегмента повторно хеширована.
7. Способ по п.4, дополнительно содержащий поиск сегментов для пары данных запроса поиска и возврат пары данных и без выполнения повторного хеширования элементов содержания сегментов.
8. Способ по п.1, дополнительно содержащий: в ответ на операцию поиска первым потоком, который не находит запрашиваемую пару данных в первом сегменте первого количества сегментов, сравнивают текущую величину емкости хеш-таблицы со значением емкости хеш-таблицы, использовавшимся при определении индекса сегмента для операции поиска, и если величина тока и значение являются разными, вычисляют индекс самого близкого сегмента наследника, получают доступ к самому близкому сегменту наследника и определяют состояние повторного хеширования для самого близкого сегмента наследника.
9. Способ по п.8, дополнительно содержащий: повторно запускают операцию поиска, если состояние повторного хеширования не обозначает новое (повторно не хешированное) состояние.
10. Способ по п.1, дополнительно содержащий, объединяют множество выделений в одиночное выделение для второго количества сегментов.
11. Способ по п.1, дополнительно содержащий: публикуют множество выделений и публикуют обновленную емкость один раз для множества выделений.
12. Изделие, содержащее машиносчитываемый носитель информации, включающий в себя инструкции, которые, при их выполнении устройством, обеспечивают возможность для устройству выполнить способ, содержащий:
выполняют операцию просмотра хеш-таблицы, совместно используемой одновременно множеством потоков, включающую в себя вычисление индекса сегмента для первого сегмента хеш-таблицы, используя первое значение емкости, получение доступа для хеш-таблицы, получая доступ к первому сегменту, используя индекс сегмента, и определение, что первый сегмент не включает в себя пару данных операции поиска;
сравнивают текущее значение емкости емкости хеш-таблицы с первым значением емкости, и если текущее значение емкости и первое значение являются разными, вычисляют обновленный индекс сегмента, используя текущее значение емкости; и
если обновленный индекс сегмента и индекс сегмента являются разными, вычисляют следующий индекс сегмента, получая доступ к следующему сегменту, соответствующему обновленному индексу сегмента, и определяющему состояние повторного хеширования для следующего сегмента.
13. Изделие по п.12, в котором способ дополнительно содержит повторный запуск операции поиска, если состояние повторного хеширования не обозначает новое состояние.
14. Изделие по п.12, в котором способ дополнительно содержит повторное хеширование сегмента хеш-таблицы, получая доступ к сегменту во время операции поиска.
15. Изделие по п.12, в котором операция поиска выполняется первым потоком, и хеш-таблица расширяется вторым потоком после того, как первый поток получит первое значение емкости для вычисления, и третий поток начинает повторное хеширование первого сегмента прежде, чем первый поток получит доступ к первому сегменту.
16. Система, содержащая:
микропроцессор, включающий в себя первой ядро и второе ядро, каждое предназначенное для выполнения одного или больше потоков, в котором первый поток должен выделять второе количество сегментов для хеш-таблицы, совместно используемой одновременно множеством потоков, причем хеш-таблица ранее имела первое количество сегментов, второе количество сегментов, по меньшей мере, равно первому количеству сегментов, где каждое второе количество сегментов логически отображают либо на соответствующего родителя одного из первого количества сегментов, или на один из второго количества сегментов, и публикации обновленной емкости хеш-таблицы, включая в себя первое и второе количество сегментов, в которой первый поток должен закончить выделение путем публикации обновленной емкости и без выполнения повторного хеширования элементов содержания первого количества сегментов, и второй поток должен выполнить операцию поиска в первом сегменте первого количества сегментов, не проверяя переменную блокировки, чтобы определить, необходимо ли повторное хеширование; и
совместно используемое запоминающее устройство, соединенное с микропроцессором, для содержания хеш-таблицы, доступ к хеш-таблице одновременно получают, по меньшей мере, некоторые из множества потоков.
17. Система по п.16, в которой третий поток должен выполнить повторное хеширование элементов содержания от первого сегмента, содержащего первое количество сегментов, до второго сегмента, содержащего второе количества сегментов, при выполнении операции поиска для пары данных, присутствующих в первом сегменте.
18. Система по п.16, в которой второй поток должен вычислять индекс сегмента для сегмента, содержащего второе количество сегментов, используя обновленную емкость, получить доступ к сегменту, используя индекс сегмента, определить, что сегмент не был повторно хеширован, и рекурсивно вычислять индекс родительского сегмента для родительского сегмента, на который сегмент был логически отображен, пока не будет найден повторно хешированный корневой сегмент.
19. Система по п.18, в которой второй поток должен повторно хешировать, по меньшей мере, часть элементов содержания повторно хешированного корневого сегмента до сегмента во время выполнения или до выполнения поиска пары данных запроса на поиск.
20. Система по п.19, в которой второй поток должен установить частичный индикатор повторного хеширования корневого сегмента, когда только часть элементов содержания корневого сегмента повторно хеширована.