хэши, огромный размер

[BuRn]

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

[BRE]

// quint32 - index
// QString - word
QHash<quint32, QString> hash;

Хеш функция генерирует индекс, этот индекс будет ключом в КуХеше. Эдакое двойное хеширование.

[BuRn]

ммм вы не поняли , функция хэширования моя вот сырец :

Код:

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct Torg 
{
   char seller[30];//продавец
};

Torg *mas[20000]; //массив указателей на структуру

int HF(char* b) //ХЕШ-ФУНКЦИЯ = формула Rhash(c)i = hash(c)i + ai + bi^2
{
   int c = 0;

   for(int i = 0; i < strlen(b); i++)
   {
      c += b[i]; 
   }
   return c % 256;
}

Torg* search(char* seller)//поиск
{
   int c = HF(seller); // результат хеш функции
   int a = 0, b = 0;
   //разрешение коолиизии
   while ((mas[a+b+c]!=NULL)&&(strcmp(mas[c+a+b]->seller, seller)!=0)&&(c+a+b<20000)) { // пока не нашли нужный элемент двигаемся оп хеш талице
      a++;
      b = a*a;
   }
   if ((a+b+c<20000)&&(mas[a+b+c])) return mas[a+b+c];//если нашли возвращаем
   return NULL;
}

void add(Torg *d)//добавление
{
   int c = HF(d->seller);
   unsigned long int a = 0, b = 0;
     //разрешение коолиизии
   while ((mas[c+a+b]!=NULL)&&(c+a+b<20000)) {//пока не нашли свободное место и не вышли за размер массива двигаемся по хеш таблице
      a++;
      b = a*a;
   }
   if (a+b+c < 20000) mas[a+b+c] = d; // если нашли добавляем в эту позицию
}

int main()
{
   memset(mas, sizeof(mas), 0);
   char a;
   FILE *f = fopen("dic1.txt","r");
    for(int i=0;i<20000;i++)
    {
       Torg* t;
       t = new Torg;
       fscanf(f,"%s",t->seller);
       cout<<t->seller<<endl<<i;
       add(t);
    }
   return 1;
}

20000 макс , а что сделать когда записей очень много

[Igors]

20000 макс , а что сделать когда записей очень много

Распределять по мере необходимости, когда вставляются новые элементы. С a + b + c придется расстаться, не беда. Для начала прямолинейно выделяйте такую напр структуру

Код

C++ (Qt)
strict CTorgPtr {
 CTorgPtr * mNext;
 Torg * mData;
};
 

Потом можно выделять лучше и прицепить template. Во всяком случае сделать свой хэш - это интересно

[BRE]

Для начала прямолинейно выделяйте такую напр структуру

А как такая организация данных позволит быстро искать нужную запись?
С такой организацией мы теряем все достоинства хеш-поиска.

[BuRn]

реализовал, кому интересно пишите, скину

[Igors]

А как такая организация данных позволит быстро искать нужную запись?

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

[fuCtor]

Для начала прямолинейно выделяйте такую напр структуру

А как такая организация данных позволит быстро искать нужную запись?
С такой организацией мы теряем все достоинства хеш-поиска.

Хеш функция может и иметь коллизии, в этом случае будет хеш таблица корзин, в которые будут попадать значения, там уже может работать либо еще одна хеш таблица (с другой хеш функцией), либо другая структура данных в принципе. При таком раскладе на больших объемах будет только выигрыш: хеш функции проще быстрее, время поиска увеличится не значительно, но будет проигрыш по памяти =).