Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > помогите написать прогу hash-таблица


Автор: Алёнка 22.2.2005, 17:35
Народ!Может кто-нибудь сможет мне помочь. Мне нужно написать прогу hash-таблица. Т.е. все операции с хэш-таблицей: поиск, добавить, найти, минимум.

Автор: sergejzr 22.2.2005, 17:36
Начинай, мы поможем, если будут вопросы smile темка интересная.

Автор: chaos 22.2.2005, 17:39
на сколько я понимаю хаш таблица это в стл map и multimap
советую заглянуть в реализацию по этим классам, станет легче )
Ну а что не ясно обращайся, "поможем", как сказал sergej.z

Автор: pablo 22.2.2005, 18:28
Цитата
на сколько я понимаю хаш таблица это в стл map и multimap
советую заглянуть в реализацию по этим классам, станет легче )
Ну а что не ясно обращайся, "поможем", как сказал sergej.z


Нет. Таблица хаш это не map, multimap, т.к они реализованы ввиде сбалансированного бинарного дерева.
Это чуток из другой оперы. smile

Автор: chaos 22.2.2005, 18:48
Цитата(pablo @ 22.2.2005, 18:28)
Цитата
на сколько я понимаю хаш таблица это в стл map и multimap
советую заглянуть в реализацию по этим классам, станет легче )
Ну а что не ясно обращайся, "поможем", как сказал sergej.z


Нет. Таблица хаш это не map, multimap, т.к они реализованы ввиде сбалансированного бинарного дерева.
Это чуток из другой оперы. smile

хорошо!!!
Объясни тогда что это такое, что бы знать на будущее smile

Автор: sergejzr 22.2.2005, 19:03
Вот, глянь..
http://forum.vingrad.ru/index.php?showtopic=42834&hl=hash#

Автор: Алёнка 22.2.2005, 23:06
все внимательно прочитала. даже фигню какую то по аглицки. тока мало что поняла. про хэш таблицу нам на лекциях впаривали. я экзамен сдавала. что это такое я знаю. сама могу кому угодно объяснить. у меня проблема именно с программой.

Автор: sergejzr 22.2.2005, 23:10
Алёнка, а ссылку chaos попросил. smile

В чём проблема с программой? Не знаешь как начать? Как закончить? Уже есть наброски? Выкладывай что есть. (фигню по англицки не надо smile )

Автор: bel_nikita 22.2.2005, 23:51
Вот, примерчик ХЭШ smile
Код

#ifndef __id2string_h__
#define __id2string_h__

#include <wtypes.h>

class cIDStrings
{
 DWORD *pdwStringID;
 DWORD *pdwStringHash;
 char **pszStrings;
 char **pszCompareString;
 int iCapacity, iCount;
public:
 cIDStrings(int iMaxSize);
 ~cIDStrings(void);
 void  AddString(DWORD dwID, char *szString);
 int   FindIDByString(char *szString);
 char* FindStringByID(DWORD dwID);
};

#endif

Код

#include "id2String.h"

char szNULLString[2]="";

#define COMPUTE_HASH(StrLengh,String) ((StrLengh)&0xFFFF)|((BYTE)((String)[0])<<16)|((BYTE)((String)[1])<<24)

cIDStrings::cIDStrings(int iMaxSize)
{
 iCapacity=iMaxSize; iCount=0;
 pdwStringID      = (DWORD*)malloc(iCapacity*sizeof(DWORD));
 pdwStringHash    = (DWORD*)malloc(iCapacity*sizeof(DWORD));
 pszStrings       = (char**)malloc(iCapacity*sizeof(char*));
};

cIDStrings::~cIDStrings(void)
{
 if (pdwStringID)      free(pdwStringID),      pdwStringID=NULL;
 if (pdwStringHash)    free(pdwStringHash),    pdwStringHash=NULL;
 if (pszStrings)       free(pszStrings);       pszStrings=NULL;
 iCapacity=0; iCount=0;
};

void cIDStrings::AddString(DWORD dwID, char *szString)
{
 if ((iCount>=iCapacity)||(!pdwStringID)||(!pdwStringHash)||(!pszStrings)) return;
 pszStrings[iCount]       = szString;
 pdwStringID[iCount]      = dwID;
 pdwStringHash[iCount]    = COMPUTE_HASH(strlen(szString),szString);
 iCount++;
};

int cIDStrings::FindIDByString(char *szString)
{
 if ((iCount>=iCapacity)||(!pdwStringID)||(!pdwStringHash)||(!pszStrings)||(!szString)) return -1;
 char  **pszLines=pszStrings;
 DWORD *pdwHash=pdwStringHash, dwSize=iCount;
 int iLength=strlen(szString);
 DWORD dwHash=COMPUTE_HASH(iLength,szString);
 int iResult;
 __asm
 {
   mov edx,pszLines
   mov edi,pdwHash
   mov ecx,dwSize
   mov eax,dwHash
   cld
 fc_loop:
   jcxz fc_err_end
   repne scasd
   jnz fc_err_end
   push ecx
   push edi
   mov ebx,dwSize
   sub ebx,ecx
   dec ebx
   mov esi,[edx+4*ebx]
   mov edi,szString
   mov ecx,eax
   and ecx,0xFFFF
   repz cmpsb
   pop edi
   pop ecx
   jnz fc_loop
   mov iResult,ebx
   jmp fc_ok_end
 fc_err_end:
   xor ebx,ebx
   not ebx
   mov iResult,ebx
 fc_ok_end:
 };
 if (iResult>=0) iResult=pdwStringID[iResult];
 return iResult;
};

char* cIDStrings::FindStringByID(DWORD dwID)
{
 if ((iCount>=iCapacity)||(!pdwStringID)||(!pdwStringHash)||(!pszStrings)) return szNULLString;
 DWORD *pdwID=pdwStringID, dwSize=iCount;
 int iResult;
 __asm
 {
   mov edi,pdwID
   mov ecx,dwSize
   mov eax,dwID
   cld
   jcxz fc_err_end
   repne scasd
   jnz fc_err_end
   mov ebx,dwSize
   sub ebx,ecx
   dec ebx
   mov iResult,ebx
   jmp fc_ok_end
 fc_err_end:
   xor ebx,ebx
   not ebx
   mov iResult,ebx
 fc_ok_end:
 };
 if (iResult>=0) return pszStrings[iResult]; else return szNULLString;
};

Типа использование. Думаю понятно, особо объяснять не нужно
Код

 cIDStrings     *StrHelp;
 StrHelp=    new cIDStrings(12);
 StrHelp->AddString(ID_DIR,"DIR");
 StrHelp->AddString(ID_DEL,"DEL");
 StrHelp->AddString(ID_CD,"CD");
 StrHelp->AddString(ID_RD,"RD");
 StrHelp->AddString(ID_MD,"MD");
 StrHelp->AddString(ID_COPY,"COPY");
 StrHelp->AddString(ID_REN,"REN");
 StrHelp->AddString(ID_CMD_EXECUTE,"Command executing\r\n");
 StrHelp->AddString(ID_CMD_BAD,"Bad command\r\n");
 StrHelp->AddString(ID_CMD_BADPARAM,"Bad parameter(s)\r\n");

 dwCmdID=StrHelp->FindIDByString(pszCmd);

char *pszResult=StrHelp->FindStringByID(dwCmdResult);

Автор: mr.DUDA 23.2.2005, 08:14
bel_nikita, а теперь без ассемблера и не только для стрингов, плиз smile

Автор: pablo 23.2.2005, 14:55
Цитата(chaos @ 22.2.2005, 18:48)
Цитата (pablo @ 22.2.2005, 18:28)
Цитата
на сколько я понимаю хаш таблица это в стл map и multimap
советую заглянуть в реализацию по этим классам, станет легче )
Ну а что не ясно обращайся, "поможем", как сказал sergej.z



Нет. Таблица хаш это не map, multimap, т.к они реализованы ввиде сбалансированного бинарного дерева.
Это чуток из другой оперы. 


хорошо!!!
Объясни тогда что это такое, что бы знать на будущее 


Извините за дизинформацию.
Map прекрасно подходит для этих целей, но надо прeдусмотреть выявление коллизий.

Согласно дяде Бъерну Страуструпу, для организации хеш таблиц в стандартной библиотеке предусмотрены два контейнера.

map<string, int> m1; //сравнение строк при помоши оператора <

map<string, int, Nocase> // сравнение строк при помощи оператора Nocase

hash_map<string, int, hfct> //хеширование при помощи hfct, бес этой функции хеширование будет при помощи Hash<string> и сравнение при помощи оператора ==

hash_map<string, int, hfct, eql> //хеширование при помощи hfct, сравнение при помощи eql

Автор: Алёнка 24.2.2005, 15:23
само задание звучит так: хэш таблица + минимум. для реализации минимума испльзовать кучу.
куча это такая штука, когда сыновья меньше чем отец.
т.е. самый главный папаша самый большой. его сыновья меньше. сыновья сыновей еще меньше и т.д.по крайней мере препод так объяснял.
пусть у нас будет 10 ячеек в хэш таблице. в хэш таблицу приходит данное с некоторым ключом например 13. оно помещается в ячейку 3. если придет данное с ключом 23. то оно поместится в ячейку 4 т.к. ячейка 3 уже занята. либо можно на каждой ячейке использовать указатель на ключ.
вот такие дела. smile
если честно проблема с самим заданием. ни начать ни закончить не могу. еще более или менее могу с вычматом разобратся, но указатели это не моё. а препод уже пообещал троих отчислить из-за того что группа большая smile.
а этот код который мне написал bel nikita он на ассемблере написан? я уже сотню раз такое встречала но нас такому не учили. он чем то на C++ похож. а насколько они похожи мне кто нибудь сказать может?

Автор: En_t_end 24.2.2005, 16:31
Алёнка 
У асм'а с С++ ничего общего нет. Просто большинство компиляторов для( + если я не ошибаюсь, в си вообще стандартом предусмотрены вставки из асм'а) си поддерживает вставки из асм'а + дебугер разбирает код переведенный на асм.

Автор: Алёнка 24.2.2005, 16:55
хорошо. а как ту штуку с ассемблера на с++ перевести. мне этот язык абсолютно незнаком. я пару раз видела какие то программы которые переводят с одного языка на другой, но это было давно. где их можно найти?

Автор: En_t_end 24.2.2005, 17:14
Не знаю, я только встречал дизассемблеры - программы дизассемблирующие машинный код. Одним я как раз активно пользуюсь. smile
Логически возможен перевод с одного языка на другой, но я о таком не слышал, набери в гугле запрос. smile

Автор: Алёнка 25.2.2005, 00:04
наверно такую штуку я и видела. а что такое гугл?

Автор: sergejzr 25.2.2005, 00:06
Гугл это Google. Только он не поможет.

С ассемблера на Си перевести нельзя. И нет таких тулов.

Автор: En_t_end 25.2.2005, 11:10
Цитата
С ассемблера на Си перевести нельзя.

Вот и авторитетный товарисч подтвердил smile

Автор: Guest 26.2.2005, 20:53
а че тогда с той прогой можно сделать. кто-нить может помочь перевести?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)