Форум программистов, компьютерный форум CyberForum.ru

Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице - C++

Восстановить пароль Регистрация
 
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
08.01.2012, 14:44     Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице #1
задание таково
организовать асоциированную карту строк, с возможностью быстрого поиска по хеш-таблице
хеш функция - md4

суть проблем в чем.
хеш-таблица в STL - hash_map. значит ключом должен быть - хеш,а значением - строка. но! я считал что добавлять в таблицу можно разные значения. то есть если уже строка содержится в таблице её добавить нельзя. но у меня почему-то добавляется.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <hash_map>
#include <iostream>
#include <Windows.h>
#include <stdlib.h>
#include <WinCrypt.h>
#include <string>
#pragma comment(lib,"crypt32.lib")
 
int _tmain(int argc, _TCHAR* argv[])
{
    std::hash_map<HCRYPTHASH*,std::string*> table;
    while(1)
    {
        ::system("cls");
        std::cout<<"Add---1\n";
        std::cout<<"View--2\n";
        std::cout<<"Find--3\n";
        int x;
        std::cin>>x;
        switch(x)
        {
        case 1:
            {
                ::system("cls");
                        std::string *tohash=new std::string();
                            std::cout<<"String to hash\n";
                            std::cin>>*tohash;
                        HCRYPTHASH *hash=new HCRYPTHASH();
                        HCRYPTPROV *prov=new HCRYPTPROV();
                        BYTE *buf1=(BYTE*)tohash->c_str();
                            DWORD buf1len=strlen((char*)buf1)+1;
                            ::CryptAcquireContext(prov,NULL,NULL,PROV_RSA_AES,0);
                            ::CryptCreateHash(*prov,CALG_MD4,0,0,hash);
                            ::CryptHashData(*hash,buf1,buf1len,0);
                        std::pair<HCRYPTHASH*,std::string*> pair;
                        pair.first=hash;
                        pair.second=tohash;
                        table.insert(pair);
                ::system("pause");
                break;
            }
        case 2:
            {
                ::system("cls");
                std::cout<<"Contains\n";
                            for each(std::pair<HCRYPTHASH*,std::string*> x in table)
                            {
                             BYTE hash[16];
                             DWORD length=16;
                             ::CryptGetHashParam(*x.first,HP_HASHVAL,hash,&length,0);
                             for(int i=0;i<length;i++)
                              std::cout<<hash[i];
                             std::cout<<" "<<*x.second;
                             std::cout<<std::endl;
                            }
                ::system("pause");
                break;
            }
        case 3:
            {
                ::system("cls");
                std::string *tocompare=new std::string();
                            std::cout<<"String to compare\n";
                            std::cin>>*tocompare;
                                HCRYPTPROV *provider=new HCRYPTPROV();
                            HCRYPTHASH *hashA=new HCRYPTHASH();
                            BYTE *buf11=(BYTE*)tocompare->c_str();
                            DWORD buf11len=strlen((char*)buf11)+1;
                            ::CryptAcquireContext(provider,NULL,NULL,PROV_RSA_AES,0);
                            ::CryptCreateHash(*provider,CALG_MD4,0,0,hashA);
                            ::CryptHashData(*hashA,buf11,buf11len,0);
                BYTE guf[16];
                            DWORD rip=16;
                            ::CryptGetHashParam(*hashA,HP_HASHVAL,guf,&rip,0);
                std::cout<<"Hash to compare\n";
                            for(int i=0;i<rip;i++)
                             std::cout<<guf[i];
                            std::cout<<" "<<*tocompare<<"\nResult of find\n";
                for each(std::pair<HCRYPTHASH*,std::string*> x in table)
                            {
                             BYTE hash[16];
                             DWORD length=16;
                             ::CryptGetHashParam(*x.first,HP_HASHVAL,hash,&length,0);
                             if (memcmp(guf,hash,16)==0)
                             {
                                 printf("Found\n");
                             break;
                             }
                            }
                ::system("pause");
                            break;
            }
        }
    }
}
еще непонятен быстрый поиск. я просто обхожу таблицу перебором. а как правильно надо?

Добавлено через 19 часов 38 минут
может быть проблема что ключом является указатель?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2012, 14:44     Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице
Посмотрите здесь:

Вопрос по хеш-таблице C++
Заполнение списка с возможностью перестановки его строк C++
C++ Кто знаком с алгоритмом быстрого поиска
C++ Телефонная книга: подскажите алгоритм быстрого поиска контактов
Хеш-таблица для строк C++
Организовать запись строк из одного файла в другой через одну C++
Программа для поиска соответствие строк, учитывая регистр, в текстовом файле с 10000+ строк C++
Разработать класс строк, с функцией вывода, подсчетом длины и возможностью сдвига строки на 1 символ вправо C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
08.01.2012, 15:35     Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице #2
Думаю, дело в том, что значением является указатель:
Цитата Сообщение от Artishok Посмотреть сообщение
std::string *tohash=new std::string();
Каждый раз объект-то новый, даже если содержимое одинаковое. И адрес объекта тоже новый.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
08.01.2012, 19:03  [ТС]     Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице #3
не не помогло.

я решил хранить вместо HCRYPTHASH массив байтов BYTE* и это тоже не помогло.

Добавлено через 1 час 49 минут
возможно ли использовать в качестве ключа - std::vector? потому что в таком случае
C++
1
2
3
4
5
6
7
8
    std::hash_map<std::vector<BYTE>,std::string> table1;
    std::pair<std::vector<BYTE>,std::string> pair1;
    std::vector<BYTE> *a=new std::vector<BYTE>();
    std::vector<BYTE>::iterator iter;
    a->insert(a->begin(),5);
    pair1.first=*a;
    pair1.second="noname";
    table1.insert(pair1);
ругается что
cannot convert from 'const std::vector<_Ty>' to 'size_t
Yandex
Объявления
08.01.2012, 19:03     Организовать ассоциированную карту строк, с возможностью быстрого поиска по хеш-таблице
Ответ Создать тему
Опции темы

Текущее время: 12:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru