Проверка членства с открытой цепочкой и отдельной адресацией

Question

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

Спасибо!

Answer 1

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

Редактировать:

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