Я думаю, что есть несколько вещей, которые мне нужно объяснить более подробно, чтобы ответить на ваш вопрос.
Для начала, существует сильное различие между хэш-функцией, которая обычно используется вПрограмма и количество сегментов, используемых в хэш-таблице.В большинстве реализаций хеш-функции хеш-функция представляет собой некоторое отображение объектов на целые числа.Затем хеш-таблица может свободно выбирать любое количество сегментов, которое она хочет, а затем отображать обратно из целых чисел в эти сегменты.Обычно это делается путем взятия хеш-кода, а затем его изменения по количеству сегментов.Это означает, что если вы хотите сохранить точки в хеш-таблице, вам не нужно беспокоиться о том, насколько велики значения, которые создает ваша хеш-функция.Например, если в хэш-таблице только три сегмента и вы создаете объекты с хэш-кодами 0 и 1 000 000 000, то первый объект хэшируется в нулевой сегмент, а второй объект - в 1 000 000 000% 3 = 1-й сегмент.Вам не понадобится 1 000 000 000 ведер.Следовательно, вам не нужно беспокоиться о выборе хеш-функции, такой как x * 200 + y, поскольку, если ваша хеш-таблица не реализована очень странно, вам не нужно беспокоиться об использовании пространства.
Если вы создаетехеш-таблицу таким образом, что вы будете вставлять только один раз, а затем тратить много времени на доступ, вам может понадобиться совершенные хеш-функции и совершенные хеш-таблицыЭто структуры данных, которые работают, пытаясь найти хеш-функцию для набора точек, которые вы сохраняете, чтобы никогда не возникало коллизий.Они занимают (ожидаемое) O (n) время для создания и могут выполнять поиск в наихудшем случае O (1).Если исключить накладные расходы при вычислении хеш-функции, это самый быстрый способ поиска точек в пространстве.
Если бы вы просто выбросили все в древовидную карту, как это делают большинство реализаций std::map,Вы должны быть в порядке.Максимум 400x400 = 160 000 точек, время, необходимое для поиска точки, составило бы около 160 000 ≈ 18 просмотров.Это вряд ли будет узким местом в любом приложении, хотя, если вам действительно нужна вся производительность, вы можете получить вышеупомянутую идеальную хеш-таблицу, вероятно, будет лучшим вариантом.
Однако оба эти решения работают, только еслиинтересующие вас запросы имеют вид "существует ли точка p в наборе или нет?"Если вы хотите выполнить более сложные геометрические запросы, такие как поиск ближайших соседей или найти все точки в ограничительной рамке, вы можете рассмотреть более сложные структуры данных, такие как kd tree , которая поддерживает очень быстро (O (log n)) поиск и быстрый поиск ближайшего соседа и диапазона.
Надеюсь, это поможет!