Хэш-карта с таким полным заполнением переходит в линейный поиск, поэтому вы захотите, чтобы они были заполнены на 90% меньше.
Вы правы в отношении открытой адресации, используя меньше памяти, для создания цепочки потребуется указатель илиполе смещения в каждом узле.
Я создал структуру данных хеш-массива для случаев, когда мне нужны очень легкие хеш-таблицы, в которых не будет много вставок.Чтобы поддерживать низкое использование памяти, все данные встраиваются в один и тот же блок памяти со структурой HashArray в начале, затем двумя массивами для хэшей и значений.Hasharray можно использовать только с ключом поиска, который хранится в значении.
typedef uint16_t HashType; /* this can be 32bits if needed. */
typedef uint16_t HashSize; /* this can be made 32bits if large hasharrays are needed. */
struct HashArray {
HashSize length; /* hasharray length. */
HashSize count; /* number of hash/values pairs contained in the hasharray. */
uint16_t value_size; /* size of each value. (maximum size of value 64Kbytes) */
/* these last two fields are just for show, they are not defined in the HashArray struct. */
uint16_t hashs[length]; /* array of hashs for each value, this helps with resolving bucket collision */
uint8_t values[length * value_size]; /* array holding all values. */
};
#define hasharray_get_hashs(array) (HashType *)(((uint8_t *)(array)) + sizeof(HashArray))
#define hasharray_get_values(array) ((uint8_t *)(array)) + sizeof(HashArray) + \
((array)->length * sizeof(HashType))
#define hasharray_get_value(array, idx) (hasharray_get_values(array) + ((idx) * (array)->value_size))
Макросы hasharray_get_hashs & hasharray_get_values используются для получения массивов 'hashs' & 'values'.
Iиспользовал это для добавления быстрого поиска сложных объектов, которые уже хранятся в массиве.У объектов есть строковое поле 'name', которое используется для поиска.Имена хэшируются и вставляются в хеш-массив с индексом объектов.Значения, хранящиеся в хэш-массиве, могут быть индексами / указателями / целыми объектами (я использую только малые 16-битные значения индексов).
Если вы хотите упаковать хеш-массив до его почти полного заполнения, тогда вы захотите использовать полный32-битные хэши вместо 16-битных, определенных выше.Большие 32-битные хэши помогут поддерживать быстрый поиск, когда хэш-массив заполнен более чем на 90%.
Хэш-массив, как определено выше, может содержать максимум 65535, что хорошо, так как я никогда не использую его для чего-либо, что могло бы иметьболее нескольких сотен значений.Все, что требует большего, чем просто обычная хеш-таблица.Но если память действительно является проблемой, тип HashSize может быть изменен на 32 бита.Также я использую длины степени 2 для быстрого поиска хеша.Некоторые люди предпочитают использовать простую длину сегмента, но это необходимо только в том случае, если хеш-функция имеет неправильное распределение.
#define hasharray_empty_hash 0xFFFF /* hash value to mark empty slots. */
void *hasharray_search(HashArray *array, HashType hash, uint32_t *next) {
HashType *hashs = hasharray_get_hashs(array);
uint32_t mask = array->length - 1;
uint32_t start_idx;
uint32_t idx;
hash = (hash == hasharray_empty_hash) ? 0 : hash; /* need one hash value to mark empty slots. */
start_hash_idx = (hash & mask);
if(*next == 0) {
idx = start_idx; /* new search. */
} else {
idx = *next & mask; /* continuing search to next slot. */
}
/* find hash in hash array. */
do {
/* check for hash match. */
if(hashs[idx] == hash) goto found_hash;
/* check for end of chain. */
if(hashs[idx] == hasharray_empty_hash) break;
idx++;
idx &= mask;
} while(idx != start_idx);
/* maximum tries reached (i.e. did a linear search of whole array) or end of chain. */
return NULL;
found_hash:
*next = idx + 1; /* where to continue search at, if this is not the right value. */
return hasharray_get_values(array) + (idx * array->value_size);
}
произойдет коллизия хеша, поэтому код, вызывающий hasharray_search (), должен сравнить ключ поиска стот, который хранится в объекте значения.Если они не совпадают, тогда вызывается hasharray_search ().Также могут существовать неуникальные ключи, так как поиск может продолжаться до тех пор, пока не будет возвращено «NULL», чтобы найти все значения, которые соответствуют одному ключу.Функция поиска использует линейное зондирование для кэширования по-дружески.
typedef struct {
char *name; /* this is the lookup key. */
char *type;
/* other field info... */
} Field;
typedef struct {
Field *list; /* array of Field objects. */
HashArray *lookup; /* hasharray for fast lookup of Field objects by name. The values stored in this hasharray are 16bit indices. */
uint32_t field_count; /* number of Field objects in 'list'. */
} Fields;
extern Fields *fields_new(uint16_t count) {
Fields *fields;
fields = calloc(1, sizeof(Fields));
fields->list = calloc(count, sizeof(Field));
/* allocate hasharray to hold at most 'count' uint16_t values.
* The hasharray will round 'count' up to the next power-of-2.
* That power-of-2 length must be atleast (count+1), so that there will always be one empty slot.
*/
fields->lookup = hasharray_new(count, sizeof(uint16_t));
fields->field_count = count;
}
extern Field *fields_lookup_by_name(Fields *fields, const char *name) {
HashType hash = str_to_hash(name);
Field *field;
uint32_t next = 0;
uint16_t *rc;
uint16_t idx;
do {
rc = hasharray_search(fields->lookup, hash, &next);
if(rc == NULL) break; /* field not found. */
/* found a possible match. */
idx = *rc;
assert(idx < fields->field_count);
field = &(fields->list[idx]);
/* compare lookup name with field's name. */
if(strcmp(name, field->name) == 0) {
/* found match. */
return field;
}
/* field didn't match continue search to next field. */
} while(1);
return NULL;
}
Поиск в худшем случае приведет к линейному поиску всего массива, если он заполнен на 99%, а ключ не существует.Если ключи являются целыми числами, то линейный поиск не должен быть плохим, также нужно сравнивать только ключи с одинаковым значением хеш-функции.Я стараюсь сохранять размер хеш-массивов таким образом, чтобы они были заполнены только на 70-80%, пространство на пустых слотах не слишком много, если значения только 16-битные.При таком дизайне вы используете только 16 байтов на пустой слот при использовании 16-битных хэшей и 16-битных значений индекса.Массив объектов (структуры полей в приведенном выше примере) не имеет пустых мест.
Также большинство реализаций хеш-таблиц, которые я видел, не хранят вычисленные хэши и требуют полного сравнения ключей для разрешения столкновений сегментов.Сравнение хэшей очень помогает, поскольку для поиска сегмента используется только небольшая часть значения хэша.