Hashovací tabulka se separátním zřetězením – C / C++ – Fórum – Programujte.com

Dobrý den, máme za úkol navrhnout hashovací tabulku kde se kolize řeší zřetězením. Hashovací tabulku se mi povedlo funkčně sestavit, ale k tomu máme ještě udělat průměr a maximum uložených seznamů. Chtěl bych se Vás tedy zeptat zda byste mi neporadili jak na to. Předem děkuji za Váš čas. 

#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#include<time.h>

#define min 5
#define max 20
#define M 10007
#define M2 10000

void InsertHash(char* str,unsigned int length,unsigned int i);
bool SearchHash(char* str,unsigned int length,unsigned int i);

struct ListItems
		{
			char* data;
			ListItems* next;
			ListItems* prev;
		};

struct List
{

		ListItems* head;

        List()
        {
            head = NULL;
        }


		bool Search(char* x)
		{
            ListItems* p;
            for (p = head; p != NULL; p = p->next)
                if (p->data == x)
                    return true;

            return false;
        }

		unsigned int  Insert(char *x)
            {

                    ListItems* p;
                    p = new ListItems;
                    p->data = x;
                    p->next = head;
                    if (head != NULL)
                        head->prev = p;
                    head = p;
                    p->prev = NULL;

            }

};

List HashTable[M];
List HashTable2[M2];

unsigned int DJBHash(const char* str,unsigned int length)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for (i = 0; i < length; ++str, ++i)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash%M;

}

void InsertHash(char* str,unsigned int length ,unsigned int i )
{
	unsigned int hashKey = DJBHash(str,length);
	if(i==1)
        HashTable[hashKey].Insert(str);
    else if(i==2)
        HashTable2[hashKey].Insert(str);
}
bool SearchHash(char* str,unsigned int length,unsigned int i)
{
	unsigned int hashKey = DJBHash(str,length);
	if(i==1)
        return HashTable[hashKey].Search(str);
    if(i==2)
        return HashTable2[hashKey].Search(str);
}


char *stri(unsigned int length)
{
    static const char letters[] = "abcdefghijklmnopqrstuvwxyz";
	char *s = (char*)malloc((length + 1) * sizeof(char));
	for (unsigned int i = 0; i < length; ++i)
	{
		s[i] = letters[rand() % (sizeof(letters) - 1)];

	}

	s[length] = '\0';
	return s;


}

int tab1(void)
{
    unsigned int length,i,j,c;
    char *str;


	for (i = 0; i < 5004; i++)
	{
		length = min + rand() % (max + 1 - min);
        str = stri(length);

		if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);

        }


	}

   for (i = 0; i < 2501; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {

            InsertHash(str,strlen(str),1);
        }



    }

     for (i = 0; i <2502 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);
        }



    }

    for (i = 0; i <2502 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),1)==false)
        {
            InsertHash(str,strlen(str),1);
        }



    }
    return 1;
}
int tab2(void)
{
    unsigned int length,i,j,c;
    char *str;

	for (i = 0; i < 5000; i++)
	{
		length = min + rand() % (max + 1 - min);
        str = stri(length);
		if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }

	}

   for (i = 0; i < 2500; i++)
    {
        length = min + rand() % (max+1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }

     for (i = 0; i <2500 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }

    for (i = 0; i <2500 ; i++)
    {
        length = min + rand() % (max + 1 - min);
        str = stri(length);
        if(SearchHash(str,strlen(str),2)==false)
        {
            InsertHash(str,strlen(str),2);
        }



    }
    return 1;
}

int main()
{
    srand(time(0));
    tab1();
    tab2();

	return 0;
}

Tím se asi myslí maximum a průměr délek těch seznamů.

Takže si třeba do Listu přidej počitadlo vložených prvků.

Pak ještě tomu Listu doplň destruktor, ve kterém uvolníš alokovanou paměť (taky by bylo dobré pořešit kopírování). Z DJBHash vyhoď to modulo M, když zjevě používáš 2 různé hodnoty. A vykopej ty funkce InserHash/SearchHash a globální proměnné.

struct Table
{
	Table(size_t m)
	{
		lists.resize(m);
	}

	void Insert(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % lists.size();
		lists[hashKey].Insert(str);
	}

	bool Search(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % lists.size();
		return lists[hashKey].Search(str);
	}

	size_t MaxKeyUse()
	{
		size_t max = 0;
		for (List& list : lists)
			max = std::max(max, list.size);
		return max;
	}

private:
	std::vector<List> lists;
};

Table table1(M);
Table table2(M2);

table1.Insert(strdup("hrcprc"));
table1.MaxKeyUse();

#2 gna
Děkuji za odpověď, nešlo by to ale udělat bez použití vektorů. Vektory jsme ještě neměli nevím jestli by mi to uznali tu úlohu.

Klidně tam udělej klasické pole, na tom nezáleží.

struct Table
{
	Table(size_t m)
	{
		size = m;
		lists = new List[size];
	}

	~Table()
	{
		delete[] lists;
	}

	void Insert(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % size;
		lists[hashKey].Insert(str);
	}

	bool Search(char *str)
	{
		unsigned int hashKey = DJBHash(str, strlen(str)) % size;
		return lists[hashKey].Search(str);
	}

	size_t MaxKeyUse()
	{
		size_t max = 0;
		for (size_t i = 0; i < size; i++)
			if (lists[i].size > max)
				max = lists[i].size;
		return max;
	}

private:
	List* lists;
	size_t size;
};