Ищем реализацию хеш-таблицы массива (вместо связанного списка) в C

Я ищу реализацию хеш-таблицы в C, которая хранит свои объекты в (двумерных) массивах, а не в связанных списках. то есть, если произойдет столкновение, объект, вызвавший столкновение, будет сохранен в индексе следующей свободной строки, а не помещен в начало и первый элемент связанного списка.

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

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

Благодарность


c arrays hashtable hash-collision
person kingusiu    schedule 28.04.2010    source источник
comment
Поскольку у вас такие необычные и специфические требования к его реализации, я бы поспорил, что вам лучше всего написать такую ​​реализацию самостоятельно.   -  person Daniel Bingham    schedule 28.04.2010
comment
+1, тем не менее, интересный вопрос.   -  person Tim Post♦    schedule 28.04.2010

Ответы (3)


arrow_upward
6
arrow_downward

Супер простая реализация:

char hashtable[MAX_KEY][MAX_MEMORY];
int counts[MAX_KEY] = {0}; 

/* Inserting something into the table */
SomeStruct* some_struct;
int hashcode = compute_code(some_struct);
int size = sizeof(SomeStruct); 
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size);
++counts[hashcode];

Не забудьте проверить против MAX_MEMORY.

person Andreas Brinck    schedule 28.04.2010

arrow_upward
1
arrow_downward

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

person mjh2007    schedule 28.04.2010
comment
динамическое выделение памяти разрешено, но система представляет собой многоядерную архитектуру, которая работает лучше всего, если общие данные хранятся в непрерывной памяти, поэтому я хочу использовать массивы. рассчитать максимальное количество ожидаемых столкновений — хороший совет, спасибо! - person kingusiu; 28.04.2010
comment
@kingusiu: Обычный хэш цепочки связанных списков может сработать для вас, если вы объедините его с распределителем пула, чтобы все объекты выделялись из одного непрерывного пула. Прямые и обратные ссылки даже не должны быть указателями — они могут быть просто индексами пула. - person caf; 29.04.2010

arrow_upward
0
arrow_downward

Это не на C, а на C++, но взгляните на Google Sparse Hash - может дать вам некоторые идеи. Ключевое требование состоит в том, чтобы сохраняемый объект мог быть null.

person Nikolai Fetissov    schedule 28.04.2010