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

Question

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

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

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

спасибо

Answer 1

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

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.

Answer 2

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

Answer 3

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