Таблицы хэшей с использованием VLists

Question

Phil Bagwell, в своем 2002 paper on the VList data structure, указывает, что вы можете использовать VList для реализации постоянной хэш-таблицы. Однако его объяснение того, как это работает, не включает в себя много деталей, и я не понимаю. Может ли кто-нибудь дать мне более подробное объяснение или даже примеры?

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

Answer 1

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

Answer 2

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

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

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

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