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

Question

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

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

Answer 1

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

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

Answer 2

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

EDIT:

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

Answer 3

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

Answer 4

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

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

Answer 5

Там Джуди Массивы http://judy.sourceforge.net/

Answer 6

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

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

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

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