Проблема такая, что при очень большом массиве строк, для которых нужно составить таблицу хэшей , происходит очень долго соответственно нет смысла делать поиск зжшированием, ибо больше часа занимает времени что бы пройти по всем записям файла и захэшировать каждое слово, слов 5+лямов. Что посоветуете... Нужно именно поиск хэшированием , мб есть какой нибудь метод хэширования который дает наименьшее число коллизий и наибольшую скорость...

к примеру, пусть хеш будет первые три буквы + длина слова

например вот такой ключ (сейчас под ascii, но легко можно переделать под юникодные литеры - место оставлено)

struct s_my_hash_key
{
    typedef UINT64 td_base;

    td_base m_key;

    bool operator==(s_my_hash_key o2)const
    {
        return m_key==o2.m_key;
    }

    bool operator<(s_my_hash_key o2)const
    {
        return m_key<o2.m_key;
    }

    void operator=(s_my_hash_key o2)
    {
        m_key=o2.m_key;
    }

    struct s_parser
    {
        td_base letter0:16;
        td_base letter1:16;
        td_base letter2:16;
        td_base length_:16;
    };


    s_my_hash_key():m_key(0)
    {
    }

    s_my_hash_key(UINT16 letter0, UINT16 letter1, UINT16 letter2, UINT16 length_):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        p.letter0=letter0;
        p.letter1=letter1;
        p.letter2=letter2;
        p.length_=length_;
    }

    s_my_hash_key(const char* pWord):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        if(!pWord)return;

        p.length_=strlen(pWord);

        if(p.length_>0)p.letter0=pWord[0];
        if(p.length_>1)p.letter1=pWord[1];
        if(p.length_>2)p.letter2=pWord[2];

    }
};

//

s_my_hash_key h1;
s_my_hash_key h2;

if(h1==h2)
{
}

if(h1<h2)
{
}

h1=h2;

s_my_hash_key h3('a','b','c',10);
s_my_hash_key h4("abcdefghij");

Сообщение отредактировал Алексей1153 - 14.12.2011, 6:45

не понял, пример использовния можно ?


все, не заметил. не подходит, нужно генерить инт значения что бы вставить по индексу в струткруту запись

без проблем
typedef int td_base;

struct s_parser
{
td_base letter0:8;
td_base letter1:8;
td_base letter2:8;
td_base length_:8;
};

ну и символы - только ascii, а длина будет не больше 255 (вернее - будет обрезаться по модулю 256)

Сообщение отредактировал Алексей1153 - 14.12.2011, 13:27

Хм, здесь, насколько я понимаю, будут неслабые такие коллизии... это ТС устраивает?

ммм не понял о длинне, если слов 50+ лямов то и индексов должно быть столько же

А какой метод хеширования используется сейчас?
Попробуй использовать CRC32 - он довольно быстрый, и возможных хешей 2^32.

дело все в том что в текущем методе очень много коллизий получается

зато считаться будет мгновенно, а коллизии - "недлинные", так как вряд ли будет много таких совпадений - три первых символа и длина слова (хотя, я по словарю не сравнивал) . Тут тонок баланс между скоростью хеширования и скоростью поиска - можно регулировать этот баланс размером td_base

CRC32 всяко дольше будет считаться.

Можно усложнить задачу- использовать две таблицы хешей, одну "навскидку" - моим способом, другую точную, но она будет заполняться в фоне постепенно. Показаполняется точная, пользуемся быстрой и малоточной


при чём тут количество слов, я про длину слов )

Сообщение отредактировал Алексей1153 - 14.12.2011, 17:49

генерируются 9-и значные индексы начиная от 100000000 а как же <100000000