Кукушкино хеширование: различия между версиями
Patarakin (обсуждение | вклад) м 1 версия импортирована |
|||
(нет различий)
| |||
Текущая версия от 20:55, 19 октября 2022
Кукушкино хеширование — алгоритм разрешения коллизий значений хеш-функций в таблице с постоянным временем выборки в Шаблон:Не переведено 5.
Предложено в 2001 году{{#if: | }}<ref name="{{#if: | | _427266838b550b3c }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}. Название отсылает к поведению некоторых видов кукушек, когда птенец выталкивает из гнезда яйца или других птенцов; аналогичным образом в алгоритме предусматривается возможность выталкивания старого ключа при вставке нового.
Операции
Кукушкино хеширование является видом Шаблон:Не переведено 5, в которой каждая непустая ячейка хеш-таблицы содержит ключ или пару «ключ — значение». Хеш-функция используется для определения места для каждого ключа, и его присутствие в таблице (или значение, ассоциированное с ним) может быть найдено путём проверки этой ячейки в таблице. Однако открытая адресация страдает от коллизий, которые случаются, когда более одного ключа попадают в одну ячейку. Основная идея кукушкиного хеширования заключается в разрешении коллизий путём использования двух хеш-функций вместо одной. Это обеспечивает два возможных положения в хеш-таблице для каждого ключа. В одном из обычных вариантов алгоритма хеш-таблица разбивается на две меньшие таблицы меньшего размера и каждая хеш-функция даёт индекс в одну из этих двух таблиц. Можно обеспечить также для обеих хеш-функций индексирование внутри одной таблицы.
Выборка требует просмотра всего двух мест в хеш-таблице, что требует постоянного времени в худшем случае (см. «O» большое и «o» малое). Это контрастирует с многими другими алгоритмами хеш-таблиц, которые не обеспечивают постоянное время выборки в худшем случае. Удаление также может быть осуществлено очищением ячейки, содержащей ключ за постоянное время в худшем случае, что осуществляется проще, чем в других схемах, таких как линейное зондирование.
Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же, когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется жадный алгоритм — ключ помещается в одну из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако, случай, когда процесс вставки заканчивается неудачей, попадая в бесконечный цикл или когда образуется слишком длинная цепочка (длиннее, чем заранее заданный порог, зависящий логарифмически от длины таблицы). В этом случае хеш-таблица перестраивается Шаблон:Не переведено 5 с новыми хеш-функциями:Шаблон:Цитата
Вычислительная сложность
Ожидаемое время вставки постоянно{{#if: | }}<ref name="{{#if: | | _427266838b550b3c }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}, даже если принимать во внимание возможную необходимость перестройки таблицы, пока число ключей меньше половины ёмкости хеш-таблицы, то есть Шаблон:Не переведено 5 меньше 50 %.
Чтобы обеспечить это, используется теория случайных графов — можно образовать неориентированный граф, называемый «кукушкиным графом», в котором вершинами являются ячейки хеш-таблицы, а рёбра для каждого хешируемого соединяют два возможных положения (ячейки хеш-таблицы). Тогда жадный алгоритм вставки множества значений в кукушкину хеш-таблицу успешно завершается тогда и только тогда, когда кукушкин граф для этого множества значений является псевдолесом, графом максимум с одним циклом в каждой компоненте связности. Любой порождённый вершинами подграф с числом рёбер, большим числа вершин, соответствует множеству ключей, для которых число слотов в хеш-таблице недостаточно. Если хеш-функция выбирается случайно, кукушкин граф будет случайным графом в Шаблон:Не переведено 5. С высокой степенью вероятности для случайного графа, в котором отношение числа рёбер к числу вершин ограничено сверху 1/2, граф является псевдолесом и алгоритм кукушкиного хеширования располагает успешно все ключи. Более того, та же теория доказывает, что ожидаемый размер компонент связности кукушкиного графа мал, что обеспечивает постоянное ожидаемое время вставки{{#if: | }}<ref name="{{#if: | | _489279d25a075f4d }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.
Пример
Если даны следующие две хеш-функции:
- [math]\displaystyle{ h\left(k\right)=k\mod 11 }[/math]
- [math]\displaystyle{ h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\mod 11 }[/math]
| k | h(k) | h'(k) |
|---|---|---|
| 20 | 9 | 1 |
| 50 | 6 | 4 |
| 53 | 9 | 4 |
| 75 | 9 | 6 |
| 100 | 1 | 9 |
| 67 | 1 | 6 |
| 105 | 6 | 9 |
| 3 | 3 | 0 |
| 36 | 3 | 3 |
| 39 | 6 | 3 |
Столбцы в следующих двух таблицах показывают состояние хеш-таблицы после вставки элементов.
| 1. table for h(k) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| 0 | ||||||||||
| 1 | 100 | 67 | 67 | 67 | 67 | 100 | ||||
| 2 | ||||||||||
| 3 | 3 | 36 | 36 | |||||||
| 4 | ||||||||||
| 5 | ||||||||||
| 6 | 50 | 50 | 50 | 50 | 50 | 105 | 105 | 105 | 50 | |
| 7 | ||||||||||
| 8 | ||||||||||
| 9 | 20 | 20 | 53 | 75 | 75 | 75 | 53 | 53 | 53 | 75 |
| 10 | ||||||||||
| 2. table for h'(k) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| 0 | 3 | 3 | ||||||||
| 1 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | ||
| 2 | ||||||||||
| 3 | 39 | |||||||||
| 4 | 53 | 53 | 53 | 50 | 50 | 50 | 53 | |||
| 5 | ||||||||||
| 6 | 75 | 75 | 75 | 67 | ||||||
| 7 | ||||||||||
| 8 | ||||||||||
| 9 | 100 | 100 | 100 | 100 | 105 | |||||
| 10 | ||||||||||
Циклы
Если вы хотите вставить элемент 6, вы получите бесконечный цикл. В последней строке таблицы мы находим ту же начальную ситуацию, что и в начале.
[math]\displaystyle{ h\left(6\right)=6\mod 11=6 }[/math]
[math]\displaystyle{ h'\left(6\right)=\left\lfloor\frac{6}{11}\right\rfloor\mod 11=0 }[/math]
| ключ | table 1 | table 2 | ||
| старое значение |
новое значение |
старое значение |
новое значение | |
| 6 | 50 | 6 | 53 | 50 |
| 53 | 75 | 53 | 67 | 75 |
| 67 | 100 | 67 | 105 | 100 |
| 105 | 6 | 105 | 3 | 6 |
| 3 | 36 | 3 | 39 | 36 |
| 39 | 105 | 39 | 100 | 105 |
| 100 | 67 | 100 | 75 | 67 |
| 75 | 53 | 75 | 50 | 53 |
| 50 | 39 | 50 | 36 | 39 |
| 36 | 3 | 36 | 6 | 3 |
| 6 | 50 | 6 | 53 | 50 |
Вариации
Изучались некоторые вариации кукушкиного хеширования, в основном с целью улучшить использование пространства путём увеличения Шаблон:Не переведено 5. В этих вариантах может достигаться порог загрузки больше 50 %. Некоторые из этих методов могут быть использованы для существенного уменьшения числа необходимых перестроек структуры данных.
От обобщения кукушкиного хеширования, использующего более двух хеш-функций, можно ожидать лучшего использования хеш-таблицы, жертвуя некоторой скоростью выборки и вставки. Использование трёх хеш-функций повышает коэффициент загрузки до 91 % {{#if: | }}<ref name="{{#if: | | _79ab71ecc71efd1f }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}. Другое обобщение кукушкиного хеширования, называемое блочным кукушкиным хешированием, содержит более одного ключа на ячейку. Использование двух ключей на ячейку позволяет повысить загрузку выше 80 %{{#if: | }}<ref name="{{#if: | | _623fe03d854a8bbb }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.
Ещё один изучавшийся вариант — кукушкино хеширование с запасом. «Запас» — это массив ключей постоянной длины, который используется для хранения ключей, которые не могут быть успешно вставлены в главную хеш-таблицу. Эта модификация уменьшает число неудач до обратно-полиномиальной функции со степенью, которая может быть произвольно большой, путём увеличения размера запаса. Однако большой запас означает более медленный поиск ключа, которого нет в основной таблице, либо если он находится в запасе. Запас можно использовать в комбинации с более чем двумя хеш-функциями или с блоковым кукушкиным хешированием для получения как высокой степени загрузки, так и малого числа неудач вставки{{#if: | }}<ref name="{{#if: | | _3e425c9b92244afa }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}. Анализ кукушкиного хеширования с запасом распространился и на практические хеш-функции, не только случайные модели хеш-функций, используемые в теоретическом анализе хеширования{{#if: | }}<ref name="{{#if: | | _9c24c81ecb5f7a0d }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.
Некоторые исследователи предлагают использовать в некоторых кэшах процессора упрощенное обобщение кукушкиного хеширования, называемого несимметричным ассоциативным кэшем.<ref> «Micro-Architecture». </ref>
Сравнение с аналогичными структурами
Есть другие алгоритмы, которые используют несколько хеш-функций, в частности фильтр Блума — эффективная по памяти структура данных для нечётких множеств. Альтернативная структура данных для задач с теми же нечёткими множествами, основанная на кукушкином хешировании, называемая кукушкиным фильтром, использует даже меньшую память и (в отличие от классических фильтров Блума) позволяет удаление элемента, не только вставку и проверку существования. Однако теоретический анализ этих методов проведён существенно слабее, чем анализ фильтров Блума{{#if: | }}<ref name="{{#if: | | _5887f09cc5d371ff }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.
Исследования 2006 года{{#if: | }}<ref name="{{#if: | | _0b69433823b1d481 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }} показали, что кукушкино хеширование существенно быстрее метода цепочек для малых хеш-таблиц, находящихся в кэше современных процессоров. В том же году{{#if: | }}<ref name="{{#if: | | _262327bd7f0b45b4 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }} разработана блочная версия кукушкиного хеширования (блок содержит более одного ключа), которая работает быстрее обычных методов для больших хеш-таблиц в случае высокого коэффициента загрузки. Скорость работы блочной версии кукушкиной хеш-таблицы исследована в 2009 году{{#if: | }}<ref name="{{#if: | | _b0a71b3d7a12278f }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.
См. также
- Шаблон:Не переведено 5
- Линейное зондирование
- Шаблон:Не переведено 5
- Коллизия хеш-функции
- Хеширование
- Шаблон:Не переведено 5
- Шаблон:Не переведено 5
Примечания
| {{#switch: 2
| узкие = columns reflist-narrow
| широкие = columns reflist-wide
| #default = columns
}}
| {{#switch: 2
| 1 =
| 2 | 3 = columns
| #default = columns reflist-narrow
}}
}}
| columns
}}
}}" style="{{#if:
| column-width:{{{colwidth}}};
| {{#if: 2
| {{#iferror: {{#ifexpr: 2 > 1 }}
| {{#switch: 2
| узкие | широкие =
| #default = column-width:2;
}}
}}
}}
}} list-style-type: {{#switch:
| upper-alpha
| upper-roman
| lower-alpha
| lower-greek
| lower-roman = {{{group}}}
| #default = decimal
}};">
<references group="" responsive="{{#if:
| 0
| {{#if: 2
| {{#iferror: {{#expr: 2 > 1 }}
| {{#switch: 2
| узкие | широкие = 1
| #default = 0
}}
| {{#switch: 2
| 1 = 0
| #default = 1
}}
}}
| 1
}}
}}"></references>Ошибка скрипта: Модуля «Check for unknown parameters» не существует.
Литература
- {{#if:Rasmus Pagh, Flemming Friche Rodler|Rasmus Pagh, Flemming Friche Rodler }}{{#if: Cuckoo Hashing|{{#if: |[{{{ссылка часть}}} Cuckoo Hashing]| Cuckoo Hashing}} // }}{{#if:|[[:s:{{{викитека}}}|Algorithms — ESA 2001]]|{{#if:|[{{{ссылка}}} Algorithms — ESA 2001]|Algorithms — ESA 2001}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Algorithms — ESA 2001|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2001|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2001.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2001.
|иг= — {{{издательство}}}, 2001.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2001.
}}{{#if:| — {{{том как есть}}}.}}{{#if:2161| — Т. 2161.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:121–133| — С. 121–133.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:Lecture Notes in Computer Science| — (Lecture Notes in Computer Science).}}{{#if:| — Шаблон:Nobr}}{{#if:978-3-540-42493-2| — ISBN 978-3-540-42493-2}}
- {{#if:Reinhard Kutzelnigg|Reinhard Kutzelnigg }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Fourth Colloquium on Mathematics and Computer Science]]|{{#if:|[{{{ссылка}}} Fourth Colloquium on Mathematics and Computer Science]|Fourth Colloquium on Mathematics and Computer Science}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Fourth Colloquium on Mathematics and Computer Science|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2006|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2006.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2006.
|иг= — {{{издательство}}}, 2006.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2006.
}}{{#if:| — {{{том как есть}}}.}}{{#if:AG| — Т. AG.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:403–406| — С. 403–406.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:Discrete Mathematics and Theoretical Computer Science| — (Discrete Mathematics and Theoretical Computer Science).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN {{{isbn}}}}}
- {{#if:M. Mitzenmacher|M. Mitzenmacher }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Proceedings of of the 17th Annual European Symposium on Algorithms (ESA)]]|{{#if:|[{{{ссылка}}} Proceedings of of the 17th Annual European Symposium on Algorithms (ESA)]|Proceedings of of the 17th Annual European Symposium on Algorithms (ESA)}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Proceedings of of the 17th Annual European Symposium on Algorithms (ESA)|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2009|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2009.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2009.
|иг= — {{{издательство}}}, 2009.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2009.
}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN {{{isbn}}}}}
- {{#if:Martin Dietzfelbinger, Christoph Weidling|Martin Dietzfelbinger, Christoph Weidling
}}{{#if:
| [{{{ссылка}}} Balanced allocation and dictionaries with tightly packed constant size bins]
| Balanced allocation and dictionaries with tightly packed constant size bins
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:Theoret. Comput. Sci.|и}}
|аи= // {{{автор издания}}} Theoret. Comput. Sci.
|а= // {{{автор издания}}}
|и= // Theoret. Comput. Sci.
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2007|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2007.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2007.
|иг= — {{{издательство}}}, 2007.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2007.
}}{{#if:1—2| — В. 1—2.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:380| — Т. 380.
}}{{#if:| — № {{{номер}}}.
}}{{#if:47–68| — С. 47–68. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:10.1016/j.tcs.2007.02.054| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder|Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder
}}{{#if:
| [{{{ссылка}}} More robust hashing: cuckoo hashing with a stash]
| More robust hashing: cuckoo hashing with a stash
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:SIAM J. Comput.|и}}
|аи= // {{{автор издания}}} SIAM J. Comput.
|а= // {{{автор издания}}}
|и= // SIAM J. Comput.
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2010|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2010.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2010.
|иг= — {{{издательство}}}, 2010.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2010.
}}{{#if:4| — В. 4.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:39| — Т. 39.
}}{{#if:| — № {{{номер}}}.
}}{{#if:1543–1561| — С. 1543–1561. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:10.1137/080728743| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel|Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
}}{{#if:
| [{{{ссылка}}} Explicit and efficient hash families suffice for cuckoo hashing with a stash]
| Explicit and efficient hash families suffice for cuckoo hashing with a stash
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:Algorithmica|и}}
|аи= // {{{автор издания}}} Algorithmica
|а= // {{{автор издания}}}
|и= // Algorithmica
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2014|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2014.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2014.
|иг= — {{{издательство}}}, 2014.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2014.
}}{{#if:3| — В. 3.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:70| — Т. 70.
}}{{#if:| — № {{{номер}}}.
}}{{#if:428–456| — С. 428–456. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:10.1007/s00453-013-9840-x| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Bin Fan, Michael Kaminsky, David Andersen|Bin Fan, Michael Kaminsky, David Andersen
}}{{#if:
| [{{{ссылка}}} Cuckoo Filter: Better Than Bloom]
| Cuckoo Filter: Better Than Bloom
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:;login:|и}}
|аи= // {{{автор издания}}} ;login:
|а= // {{{автор издания}}}
|и= // ;login:
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:USENIX|и}}{{#if:2013|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: USENIX, 2013.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: USENIX.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2013.
|иг= — USENIX, 2013.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — USENIX.
|г= — 2013.
}}{{#if:4| — В. 4.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:38| — Т. 38.
}}{{#if:| — № {{{номер}}}.
}}{{#if:36–40| — С. 36–40. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Marcin Zukowski, Sandor Heman, Peter Boncz|Marcin Zukowski, Sandor Heman, Peter Boncz
}}{{#if:
| [{{{ссылка}}} Architecture-Conscious Hashing]
| Architecture-Conscious Hashing
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:|и}}
|аи= // {{{автор издания}}} {{{издание}}}
|а= // {{{автор издания}}}
|и= // {{{издание}}}
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:Proceedings of the International Workshop on Data Management on New Hardware (DaMoN)|и}}{{#if:2006|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: Proceedings of the International Workshop on Data Management on New Hardware (DaMoN).
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2006.
|иг= — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN).
|г= — 2006.
}}{{#if:| — В. {{{выпуск}}}.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:| — Т. {{{том}}}.
}}{{#if:| — № {{{номер}}}.
}}{{#if:| — С. {{{страницы}}}. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Kenneth Ross|Kenneth Ross
}}{{#if:
| [{{{ссылка}}} Efficient Hash Probes on Modern Processors]
| Efficient Hash Probes on Modern Processors
}}{{#if:
| {{#ifexist: Шаблон:ref-{{{language}}}
| {{ref-{{{language}}}}}
| ({{{language}}})
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:|и}}
|аи= // {{{автор издания}}} {{{издание}}}
|а= // {{{автор издания}}}
|и= // {{{издание}}}
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:IBM Research Report RC24100|и}}{{#if:2006|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: IBM Research Report RC24100, 2006.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: IBM Research Report RC24100.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2006.
|иг= — IBM Research Report RC24100, 2006.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — IBM Research Report RC24100.
|г= — 2006.
}}{{#if:| — В. {{{выпуск}}}.
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:| — Т. {{{том}}}.
}}{{#if:| — № {{{номер}}}.
}}{{#if:| — С. {{{страницы}}}. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
- {{#if:Nikolas Askitis|Nikolas Askitis }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Fast and Compact Hash Tables for Integer Keys]]|{{#if:|[{{{ссылка}}} Fast and Compact Hash Tables for Integer Keys]|Fast and Compact Hash Tables for Integer Keys}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Fast and Compact Hash Tables for Integer Keys|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009)| — Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009).}}{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2009|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2009.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2009.
|иг= — {{{издательство}}}, 2009.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2009.
}}{{#if:| — {{{том как есть}}}.}}{{#if:91| — Т. 91.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:113–122| — С. 113–122.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:978-1-920682-72-9| — ISBN 978-1-920682-72-9}}
Ссылки
- A cool and practical alternative to traditional hash tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
- Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
- Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.
- {{#if:Moni Naor, Gil Segev, Udi Wieder|Moni Naor, Gil Segev, Udi Wieder }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|International Colloquium on Automata, Languages and Programming (ICALP)]]|{{#if:|[{{{ссылка}}} International Colloquium on Automata, Languages and Programming (ICALP)]|International Colloquium on Automata, Languages and Programming (ICALP)}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:International Colloquium on Automata, Languages and Programming (ICALP)|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:Reykjavik, Iceland|м}}{{#if:|и}}{{#if:2008|г}}
|миг= — {{#if:Reykjavik, Iceland|{{#switch:Reykjavik, Iceland|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:Reykjavik, Iceland|Reykjavik, Iceland}} }}: {{{издательство}}}, 2008.
|ми= — {{#if:Reykjavik, Iceland|{{#switch:Reykjavik, Iceland|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:Reykjavik, Iceland|Reykjavik, Iceland}} }}: {{{издательство}}}.
|мг= — {{#if:Reykjavik, Iceland|{{#switch:Reykjavik, Iceland|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:Reykjavik, Iceland|Reykjavik, Iceland}} }}, 2008.
|иг= — {{{издательство}}}, 2008.
|м= — {{#if:Reykjavik, Iceland|{{#switch:Reykjavik, Iceland|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:Reykjavik, Iceland|Reykjavik, Iceland.}} }}
|и= — {{{издательство}}}.
|г= — 2008.
}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. {{{страницы}}}.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN {{{isbn}}}}}
- Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.
