Поиск массива (по сравнению со связанным списком) реализация хеш-таблицы в C
Я ищу реализацию хеш-таблицы в C, который хранит его объекты в (двумерных) массивах, а не связанных списках. т.е. если коллизия произойдет, то объект, который вызывает коллизию, будет храниться в следующем бесплатном индексе строки, а не продвигаться к главному и первому элементу связанного списка.
плюс, сами объекты должны быть скопированы в хеш-таблицу, а не сосланы указателями. (объекты не живут для целой жизни программы, но таблица делает).
Я знаю, что такая реализация могла бы иметь серьезные недостатки эффективности и не является "стандартным способом хешировать", но поскольку я работаю над совершенно особой архитектурой системы, мне нужны те характеристики.
спасибо
3 ответа
Супер простая реализация:
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 .
Я предполагаю, что ваша система не поддерживает динамическое выделение памяти. Поэтому вам нужно будет определить границы переднего массива, которые являются разумными для ваших данных (общее количество объектов и максимальное ожидаемое количество столкновений), и, кроме того, пользовательскую хеш-функцию для ваших объектов, поэтому, возможно, лучше всего реализовать вашу собственную хеш-таблицу.
Это не на C, а на C++, но взгляните на Google Sparse Hash - это может дать вам несколько идей. Ключевым требованием является то, что хранимый объект должен иметь возможность быть null.