единая 16-битная хеш-функция для строк

Question

У меня есть около 50 000 слов, которые я хочу сопоставить каждому из них с 16-битным числом, и я ищу хэш-функцию для запуска на j2me. Чтобы быть более конкретным, я ищу хэш-функцию по следующим критериям:

1. несколько (или нет) столкновений
2. легкая загрузка процессора
3. У меня есть все слова сейчас
4. Лавинный эффект не важен, так как речь не идет о безопасности. Это просто справочная таблица.

Я тестировал java Strign.hashCode (), ропотный хеш, jenkins по одному и несколько простых ручных, но все они имеют как минимум 30% коллизий.
Минимальное идеальное хеширование, по-видимому, также сильно загружает процессор для небольшого мобильного телефона.

Кто-нибудь может мне помочь с этим?

примечание: как вы знаете, для алгоритма ропота требуется начальное число, и разные начальные числа имеют разную однородность. Как мне найти семя с минимальными коллизиями?

Заранее спасибо

Answer 1

Этот ответ может быть запоздалым, но для справки MurmurHash 3 достаточно быстр, чтобы удовлетворить ваши критерии скорости.Однако из-за ограничений, которые вы наложили, коллизии будут довольно распространенными, поскольку 16 битов могут представлять диапазон 65536 значений, ваши 50000 слов могут создать некоторые коллизии.* используйте 20+ битов для ключа (с 32 битами, есть одно столкновение в нескольких миллионах выборок)

напишите тестовую программу для поиска подходящего начального числа для 16 битов, вот несколько полезных инструментов: http://code.google.com/p/smhasher/

Answer 2

Вот функция, которую я использую в C # для сопоставления имени файла с 16-битным числом. В моих тестах он показал лучшие результаты, чем хэширование Пирсона.

    public static unsafe int Get16BitHash(string str)
    {
        int hash = 0;
        int len = str.Length;

        fixed (char* ch = str)
        {
            for (int i = 0; i < len; i++)
            {
                hash = hash + ((hash) << 5) + *(ch + i) + ((*(ch + i)) << 7);
            }
        }

        return ((hash) ^ (hash >> 16)) & 0xffff;
    }

Answer 3

Вы можете заглянуть в старомодный CRC . Они очень быстрые и без столкновений. Просто не совсем в 16 битах, как показывает этот эксперимент . Но, тем не менее, вы можете попробовать, может быть, этого достаточно для ваших целей.