Подскажите несколько несложных алгоритмов хэширования строк

#java #алгоритм #pascal #хеширование #любой_язык

Опишите пару алгоритмов для хэширования строк. Если есть, то с кодом на java или pascal. 
    

Ответы

Ответ 1

Пожалуйста, открываем исходники класса java.lang.String, находим там метод hashCode:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}


Ответ 2

Когда еще в стандарте С++ не было unordered_map, в своей реализации достаточно успешно
использовал CRC (конкретно тогда использовал CRC16).

У Гантерота в "Оптимизация программ на С++" описан следующий вариант:

struct hash_c_string {
    void hash_combine(size_t& seed, T const& v) {
        seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    std::size_t operator() (char const* p) const {
        size_t hash = 0;
        for (; *p; ++p)
            hash_combine(hash, *p);
        return hash;
    }
};


А вообще - надо экспериментировать, для конкретного набора может пройти кажущийся
совершенно плохим хэш, ну, и наоборот...

Вдогонку - можно посмотреть такую вещь, как GPERF - хотя это и далеко не самый несложный
хэш :)