Хеш-функция строго не зависит от размера строкового ключа
Я делаю хеш-таблицу, и мне нужно сделать хеш-функцию, которая зависит не только от размера строкового ключа, так как элементы периодической таблицы имеют только от 1 до 3 символов. Как я могу создать хеш-функцию, которая дает мне индекс, возможно, основанный на байтах каждого символа строки?
Решение
Довольно много каждый хеш-функция на строках хеширует символы; очень редко можно увидеть строки, хэшированные чисто по их длине.
Одно простое семейство хеш-функций смещаться-надстройку XOR, который, как следует из названия, использует комбинацию битовых сдвигов, дополнений и XOR для получения хеш-функции из строки. Это легко реализовать и дает достаточно хорошее распределение ключей.
Тем не менее, если вам гарантировано, что вы просто используете символы периодической таблицы, вы можете попытаться найти идеальную хеш-функцию для элементов. Это хеш-функция, специально созданная для набора данных, который вы используете, и никогда не имеет коллизий. Инструменты как gperf может быть использован для создания таких функций.
Надеюсь это поможет!
Другие решения
Самое простое решение — использовать существующее, например, FNV.
Однако будьте осторожны — некоторые очень распространенные хеш-функции
выступать плохо, когда дают много очень коротких строк (один
java.lang.String использует, например). Для общего хэша
функция, я обычно использую что-то вроде:
size_t
hash( std::string const& value )
{
size_t result = 2166136261;
for ( std::string::const_iterator current = value.begin();
current != value.end();
++ current ) {
result = 127 * result + static_cast< unsigned char >( *current );
}
return result;
}
На машинах с медленным умножением это немного быстрее
чем FNV, и я еще не нашел случай, когда распределение было
значительно беднее.
Однако вы упоминаете, что максимальная длина строки равна трем.
В этом случае вы, вероятно, можете использовать еще более простую технику:
size_t
hash( std::string const& value )
{
union {
size_t results;
char input[ sizeof( size_t ) ];
} working = 0;
assert( value.size() <= sizeof( size_t ) );
value.copy( working.input, sizeof( size_t ) );
return working.results;
}
Оба из них гарантируют уникальные значения хеш-функции для всех строк
печатные символы ASCII длиной менее sizeof(,
size_t )