Тип хеш-таблицы в Лиспе - PullRequest
       19

Тип хеш-таблицы в Лиспе

0 голосов
/ 06 октября 2018

Я обнаружил, что в хеш-таблице CL есть тип HASH-TABLE (на удивление).Тем не менее, вектор может быть просто VECTOR, но он также может быть указан далее как (вектор номер 12), например.

Кажется естественным, что хэш-таблица имеет тип списка, например, (число чисел в хеш-таблице) или что-то в этом роде, но, похоже, это не работает, и я не могу найти какую-либо ссылку на него.Любой совет?

1 Ответ

0 голосов
/ 06 октября 2018

TL; DR типизированные векторы могут быть оптимизированы для использования памяти, но типизированные хеш-таблицы в большинстве случаев бессмысленны.


Отказ от ответственности: в основном это основано на интуиции и недаже близко к авторитетному ответу.

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

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

Кроме того, напечатанная хеш-таблица не очень звучит в Лиспе.

...