подходит для большого количества в массив

У меня есть array10^5 размер. скажем array[100000].
Мне нужно вставить данные в этот массив, например индексирование для быстрого извлечения. подобный array[index] = value.подходит для большого количества в массив

т.е., 124 элемента [123 Индекс] имеет некоторое число 23423423 в качестве значения, так что я положил

array[123] = 23423423;

так что я могу обратиться к этому значению с индексом 123.

Теперь проблема в том, что у меня есть значение индекса до 10^9, но размер массива не может содержать много большого числа, так что есть какой-либо способ поместить весь индекс и значения в массив.

Я использую C как мой язык.

источник

2014-01-07 avinashse

См. Таблицу хешей. http://en.wikipedia.org/wiki/Hash_table –

Вам нужно либо найти реализацию «разреженного массива», либо реализовать «карту». Любой из них будет иметь немного отличающийся синтаксис от индексации нормального массива, но будет выделять хранилище только для того, что вы на самом деле используете, а не для всего пространства 10^9. Они будут внутренне управлять индексированием, чтобы быть быстрым, основанным на каком-то хеше. – mah

Звучит как [проблема XY] (http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem), то есть, возможно, вы приближаетесь ко всему, что пытаетесь сделать неправильно, но , не сообщая нам, что это такое, мы не можем помочь (но хеш-таблица действительно может быть правильным ответом на вопрос, который не задан). – Dukeling

Если вы добавляете новое значение в свой стол и никогда не удаляете его, вы можете использовать хэш-таблицу мультипроцессора. См. Мою реализацию: http://olegh.cc.st/src/words.c.txt Существует реализованный алгоритм «двойного хэширования» (некоторая мультипликация).

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

источник

2014-01-07 23:10:02 maxihatop

подходит для большого количества в массив

ответ

Смежные вопросы