Хеш-таблицы с использованием VLists

Question

Фил Бэгвелл в своей статье 2002 о структуре данных VList указывает, что вы можете использовать VList для реализации постоянной хеш-таблицы. Однако его объяснение того, как это сработало, не содержало подробностей, и я этого не понимаю. Кто-нибудь может дать мне более подробное объяснение или даже примеры?

Кроме того, из того, что я вижу, мне кажется, что эта структура данных, хотя и может иметь ту же сложность big-O, что и Hashtable, будет медленнее, поскольку она выполняет дополнительный поиск. Кто-нибудь хочет провести подробный анализ того, насколько медленнее, желательно, включая поведение кеша? Как меняется соотношение производительности между этими двумя в случае отсутствия коллизий или множества?

Answer 1

Я посмотрел на эту статью, и она кажется очень предварительной. Тот факт, что более поздняя версия не была опубликована, и что оригинал появился в IFL (это совещание в стадии разработки), говорит о том, что вы можете тратить свое время.

Answer 2

Хммм, кажется, есть ряд проблем со структурами данных, предложенными в данной статье.

Вне всяких сомнений, упомянутым наивным первым спискам, по-видимому, нужны уникальные ссылки для того, чтобы получить что-то, близкое к предлагаемым гарантиям времени. Вы теряете способность по большей части делиться хвостами. Вы можете поделиться крошечными узлами в конце списка, но вам придется дублировать самый большой узел vlist в тот момент, когда вы добавляете что-то в CDR vlist, который все еще активен. Эта стоимость пропорциональна стоимости копирования всего списка.

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

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