Использование хеш-таблицы для создания неограниченного массива

Question

В настоящее время я занимаюсь разработкой языка программирования на C и хочу позволить пользователям создавать, по-видимому, «неограниченные» массивы с числовыми индексами, не жертвуя при этом производительностью. Например, table [1000000000] в идеале может быть создан и доступен в одно мгновение без дополнительной памяти на столе в 1 000 000 000 элементов, 999 999 999 из которых не были использованы; но массив также будет работать хорошо, если table [n] определено, скажем, для 1 ≤ n ≤ 1000000.

У вас есть предложения по внедрению такой системы обработки массивов?

Answer 1

Есть Джуди Массив http://judy.sourceforge.net/

Answer 2

Вы создаете Sparse Array , как упоминается в статье в Википедии, они могут быть представлены связанным списком.

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

Answer 3

Использование cmph не поможет. Вам необходимо знать все ключи заранее, чтобы создать (минимальную) идеальную хеш-функцию.

Вам нужна простая ассоциативная структура отображения, которая позволит вам реализовать разреженный массив. Подойдет любая хеш-таблица или древовидная структура. Вы можете использовать hash_map или map из коробки из вашей реализации c ++ stl или любой подобной структуры данных.

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

Сделай простую вещь. Самый простой из доступных хеш-таблиц - лучший ответ. Даже не думайте о хэш-функциях или о чем-то подобном: все, что предоставляет ваша платформа, будет работать достаточно хорошо.

Answer 4

Теоретически я думаю, что это возможно.Вам нужен очень хороший алгоритм хеширования (чтобы избежать коллизий).Так что если кто-нибудь скажет table [100..0];вам не нужно выделять место сразу.Выделите место по мере необходимости.Поэтому, если в таблице [100..0] я пытаюсь заполнить первые 5 значений, я буду хранить только эти пять значений, и если я попытаюсь получить доступ, скажем, к таблице [100], то я должен получить что-то вроде 'undef'или 'nil' ....

библиотека, упомянутая the_void, кажется хорошей ... хотя я не проверял ...:)

Answer 5

Как насчет использования указателя, вам не нужно определять количество элементов для него, вы можете добавить столько элементов, сколько захотите

Answer 6

Я думаю, вы сами на это ответили.Взгляните на CMPH - C Minimal Perfect Hash Library .

РЕДАКТИРОВАТЬ:

Или вы можете использовать B + Tree для сопоставления целого числа с реальным индексом в массиве.Использование B Trees имеет еще одно преимущество: вы можете выполнять запросы диапазона.