Советы по хэшированным массивам на языке C

Question

Мне нужно несколько идей, чтобы разработать хорошую функцию хеширования для моего задания. У меня есть список всех стран мира (около 190). Названия каждой страны являются ключом для функции хеширования. Есть ли особый вид хеширующей функции, который кто-либо порекомендовал бы для сохранения этих данных в хеш-функции без множества коллизий? Также, можете ли вы привести пример того, как это реализовать?

Answer 1

Для этого вы можете использовать сгенерированный идеальный хеш (GNU perf).

Если набор строк является динамическим, то вы можете использовать троичное три.Для N уникальных строк вам будет дан уникальный номер [1..N].В вашем случае это будет быстрее, чем с хеш-таблицами.Вот моя реализация такой вещи: http://code.google.com/p/tiscript/source/browse/trunk/tool/tl_ternary_tree.h

Answer 2

Использование GNU gperf . Для таких входных данных, как ваш, он сгенерирует для вас C-код, который реализует идеальную хеш-функцию (для заданных входных данных). Никаких столкновений, никаких забот.

Answer 3

Самый простой подход, который я могу придумать, состоит в том, чтобы название каждой страны вычисляло сумму значений ASCII в ее представлении и использовало это в качестве хеш-значения:

int hash(const char *s)
{
    int h = 0;

    while (s && *s)
          h += *s++;

    return h;
}

Если ваша хеш-карта имеет размер N, вы храните названия стран с map[hash(my_country) % N] = my_country.Концептуально.

Просто попробуйте этот подход и посмотрите, достаточно ли равномерно распределены полученные хеш-значения.Обратите внимание, что качество распределения также может зависеть от N.