При выборе одного из методов представления разреженного массива — с помощью связанного списка, двоичного дерева, массива указателей или хэширования — необходимо руководствоваться требованиями к скорости и эффективному использованию памяти. Кроме того, необходимо учесть, насколько плотно будет заполнен разреженный массив.
Если логический массив заполнен очень редко, самыми эффективными по использованию памяти оказываются связанные списки и двоичные деревья, поскольку в них память выделяется только для тех элементов, которые действительно используются. Для самих связей требуется очень небольшой дополнительный объем памяти, которым обычно можно пренебречь. Представление в виде массива указателей предполагает создание целиком всего массива из указателей, даже если некоторые элементы не используются. При этом в памяти должен не только поместиться весь массив, но еще должна остаться свободная память для работы приложения. В некоторых случаях это может быть серьезной проблемой. Обычно можно заранее оценить примерный объем свободной памяти и решить, достаточен ли он для вашей программы. Метод хэширования занимает промежуточное место между представлениями с помощью массива указателей и связанного списка или двоичного дерева. Несмотря на то, что весь первичный массив, даже если он не используется, должен находиться в памяти, этот массив все равно будет меньше, чем массив указателей.
Если логический массив будет заполнен довольно плотно, ситуация существенно меняется. В этом случае создание массива указателей и хэширование становятся более приемлемыми методами. Более того, время поиска элемента в массиве указателей постоянно и не зависит от степени заполнения логического массива. Хотя время поиска при хэшировании и не постоянно, оно ограничено сверху некоторым небольшим значением. Но в случае связанного списка и двоичного дерева среднее время поиска увеличивается по мере заполнения массива. Это следует помнить, если время доступа является критическим фактором.