Хэш - таблица методом цепочек

@d3vn · Регистрация: 18.11.2013

Студворк — интернет-сервис помощи студентам

Всем привет!
Есть задание реализовать хеш-таблицу методом цепочек + с хэш - функциями: деление и умножение.
Я не до конца понимаю, что вообще из себя представляет хэш - таблица в плане реализации на языке C++.
Я создал структуру (пока что я думаю, что это структура):

C++
1
2
3
4
5
struct HashTable
{
     int key; 
     int value;
} hash[n];

Инициализирую:

C++
1
2
3
4
5
for (i = 0; i < n; i++)
    {
        hash[i].key = ByDivisionHashFunction(A[i]);
        hash[i].value = A[i];
    }

И это я типо создал хэш-таблицу? У меня получается так, что key бывает одинаковое, я так понял - это коллизия и нужно делать указатель на еще один список... Здесь вообще непонятки, откуда он берется? Как они создаются? Плюс сказано, что я должен искать элемент в хэш - таблице по значению. То есть мне дают элемент, я его загоняю в функцию поиска, дальше, я так понял, получаю его key и говорю есть такой или нет, а потом вывожу его и все это за линейное время. Но ведь нужен вроде как прогон двумя циклами... Объясните, пожалуйста, эту базу, не нашел годного материала, который раскрывает все мои вопросы. Спасибо.

@Koala_Rus · 20.02.2019, 08:24

там конечно многое что криво и своеобразно и вообще она не доделана, работают пока только создание и вывод на экран, но проблема в том, что выводятся только первые элементы в структуре, можете подсказать как это исправить? проблема в выводе, или в формировании?

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
#include "iostream"
#include <fstream> 
#include <stdio.h>
#include <windows.h>
#include <string.h> 
#include <string>
#include <conio.h>
#include <time.h> 
#include <math.h> 
#include <sstream>
 
using namespace std;
 
struct HeshList
{
    string FIO;//surname name patronymic
    string DOB;//date of birth
    string POL;//place of living
    HeshList* Begining;
    HeshList* NextElement;
};
 
void sozdanie(HeshList* Heshtable[200], int &KolElementov, int &KolKluchey, int &KolCollisons)
{
    ////temporary (dynamic) components
    int Keytemp;
    string FIOtemp;
    string DOBtemp;
    string POLtemp;
    ////
 
    ///////////Рандомные данные человека
    string FIOName[15] = { "Виктор","Александр","Владимир","Павел","Артём","Валерий","Алексей","Максим","Вячеслав","Кирилл","Сергей","Владимир","Руслан","Андрей","Даниил" };
    string FIODadName[15] = { "Евгеньевич","Александрович","Тарасович","Станиславович","Геннадиевич","Вольфович","Павлович","Иванович","Семенович","Анатольевич","Сергеевич" };
    string FIOSurName[10] = { "Гончаров","Аристов","Кукушкин","Попов","Никрасов","Якупов","Вавилов","Орлов","Некифоров","Козлов" };
    string DOBDay[28] = { "01","02","03","04","05","06","07","08","09","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28" };
    string DOBMonth[12] = { "01","02","03","04","05","06","07","08","09","10","11","12" };
    string DOBYear[21] = { "1980", "1981", "1982", "1983", "1984", "1985", "1986", "1987", "1988", "1989", "1990", "1991", "1992", "1993", "1994", "1995", "1996", "1997", "1998", "1999", "2000" };
    string ADRStreet[15] = { "Пушкина","Центральная","Молодёжная","Советская","Пролетарская","Набережная","Ленина","Луговая","Гагарина","Юбилейная","Нагорная","Озерная","Победы","Строителей","Свободы" };
    string ADRNumber[500] = { "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" , "96" , "97" , "98" , "99" , "100" , "101" , "102" , "103" , "104" , "105" , "106" , "107" , "108" , "109" , "110" , "111" , "112" , "113" , "114" , "115" , "116" , "117" , "118" , "119" , "120" , "121" , "122" , "123" , "124" , "125" , "126" , "127" , "128" , "129" , "130" , "131" , "132" , "133" , "134" , "135" , "136" , "137" , "138" , "139" , "140" , "141" , "142" , "143" , "144" , "145" , "146" , "147" , "148" , "149" , "150" , "151" , "152" , "153" , "154" , "155" , "156" , "157" , "158" , "159" , "160" , "161" , "162" , "163" , "164" , "165" , "166" , "167" , "168" , "169" , "170" , "171" , "172" , "173" , "174" , "175" , "176" , "177" , "178" , "179" , "180" , "181" , "182" , "183" , "184" , "185" , "186" , "187" , "188" , "189" , "190" , "191" , "192" , "193" , "194" , "195" , "196" , "197" , "198" , "199" , "200" , "201" , "202" , "203" , "204" , "205" , "206" , "207" , "208" , "209" , "210" , "211" , "212" , "213" , "214" , "215" , "216" , "217" , "218" , "219" , "220" , "221" , "222" , "223" , "224" , "225" , "226" , "227" , "228" , "229" , "230" , "231" , "232" , "233" , "234" , "235" , "236" , "237" , "238" , "239" , "240" , "241" , "242" , "243" , "244" , "245" , "246" , "247" , "248" , "249" , "250" , "251" , "252" , "253" , "254" , "255" , "256" , "257" , "258" , "259" , "260" , "261" , "262" , "263" , "264" , "265" , "266" , "267" , "268" , "269" , "270" , "271" , "272" , "273" , "274" , "275" , "276" , "277" , "278" , "279" , "280" , "281" , "282" , "283" , "284" , "285" , "286" , "287" , "288" , "289" , "290" , "291" , "292" , "293" , "294" , "295" , "296" , "297" , "298" , "299" , "300" , "301" , "302" , "303" , "304" , "305" , "306" , "307" , "308" , "309" , "310" , "311" , "312" , "313" , "314" , "315" , "316" , "317" , "318" , "319" , "320" , "321" , "322" , "323" , "324" , "325" , "326" , "327" , "328" , "329" , "330" , "331" , "332" , "333" , "334" , "335" , "336" , "337" , "338" , "339" , "340" , "341" , "342" , "343" , "344" , "345" , "346" , "347" , "348" , "349" , "350" , "351" , "352" , "353" , "354" , "355" , "356" , "357" , "358" , "359" , "360" , "361" , "362" , "363" , "364" , "365" , "366" , "367" , "368" , "369" , "370" , "371" , "372" , "373" , "374" , "375" , "376" , "377" , "378" , "379" , "380" , "381" , "382" , "383" , "384" , "385" , "386" , "387" , "388" , "389" , "390" , "391" , "392" , "393" , "394" , "395" , "396" , "397" , "398" , "399" , "400" , "401" , "402" , "403" , "404" , "405" , "406" , "407" , "408" , "409" , "410" , "411" , "412" , "413" , "414" , "415" , "416" , "417" , "418" , "419" , "420" , "421" , "422" , "423" , "424" , "425" , "426" , "427" , "428" , "429" , "430" , "431" , "432" , "433" , "434" , "435" , "436" , "437" , "438" , "439" , "440" , "441" , "442" , "443" , "444" , "445" , "446" , "447" , "448" , "449" , "450" , "451" , "452" , "453" , "454" , "455" , "456" , "457" , "458" , "459" , "460" , "461" , "462" , "463" , "464" , "465" , "466" , "467" , "468" , "469" , "470" , "471" , "472" , "473" , "474" , "475" , "476" , "477" , "478" , "479" , "480" , "481" , "482" , "483" , "484" , "485" , "486" , "487" , "488" , "489" , "490" , "491" , "492" , "493" , "494" , "495" , "496" , "497" , "498" , "499" , "500" };
    ///////////
 
    for (;;)
    {
        cout << "____________________________________________________________________________\n\nВведите количество элемтов (людей): ";
        cin >> KolElementov;
        if (KolElementov > 0)
        {
            break;
        }
        cout << "Ошибка: не правильно введен элемент! Введите заново! \n\n";
    }
 
    for (int i = 0; i < KolElementov; i++)
    {
        int SumOfWord = 0;
 
        FIOtemp = FIOSurName[rand() % 10] + " " + FIOName[rand() % 15] + " " + FIODadName[rand() % 15];
        DOBtemp = DOBDay[rand() % 28] + "/" + DOBMonth[rand() % 12] + "/" + DOBYear[rand() % 21];
        POLtemp = ADRStreet[rand() % 15] + " " + ADRNumber[rand() % 500];
 
        //Find the Key
        for (int i = 0; i < POLtemp.length(); i++)
        {
            SumOfWord = SumOfWord + (int)POLtemp[i];
        }
        if (SumOfWord < 0)
        {
            SumOfWord = SumOfWord * (-1);
        }
        float podstanovka1 = SumOfWord * 0.61;
        Keytemp = trunc(200 * ((podstanovka1)-trunc(podstanovka1)));////KEY IS FOUND
        //
 
 
 
        //PutInHeshTable
        if (Heshtable[Keytemp] == NULL)
        {
            HeshList *HeshElement = new HeshList;
            HeshElement->FIO = FIOtemp;
            HeshElement->DOB = DOBtemp;
            HeshElement->POL = POLtemp;
            Heshtable[Keytemp] = HeshElement;
            HeshElement->NextElement = NULL;
        }
        else
        {
            KolCollisons++;
            HeshList *HeshElement = Heshtable[Keytemp];
            for (int j = 0;; j++)
            {
                if (HeshElement->NextElement != NULL)
                {
                    HeshElement = HeshElement->NextElement;
                }
                else
                {
                    HeshElement = HeshElement->NextElement;
                    HeshElement = new HeshList;
                    HeshElement->FIO = FIOtemp;
                    HeshElement->DOB = DOBtemp;
                    HeshElement->POL = POLtemp;
                    HeshElement->NextElement = NULL;
                    break;
                }
            }
        }
        //
 
    }
 
    if (KolElementov > 1)
    {
        cout << "При " << KolElementov << " элементах нашлось " << KolCollisons << " коллизий\n";
        cout << "\nСписок успешно создан!\n\n";
    }
    else
    {
        cout << "При " << KolElementov << " элементе нашлось " << KolCollisons << " коллизий\n";
        cout << "\nСписок успешно создан!\n\n";
    }
 
}
 
///void nahojdenie();
///void dobavlenie();
///void udalenie();
 
void vivodnaekran(HeshList* Heshtable[200], int &KolElementov, int &KolKluchey, int &KolCollisons)
{
    
    for (int i = 0; i < KolKluchey; i++)
    {
        if (Heshtable[i] != NULL)
        {
            cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n";
            cout << "Под данным клучём (" << i + 1 << ") хранятся следующие элементы :\n";
            HeshList *HeshElement = new HeshList;
            HeshElement = Heshtable[i];
            for (;;)
            {
                cout << "ФИО: " << HeshElement->FIO <<"\n";
                cout << "День Рождения: " << HeshElement->DOB <<"\n";
                cout << "Адрес проживания: " << HeshElement->POL <<"\n\n";
                if (HeshElement->NextElement != NULL)
                {
                    HeshElement = HeshElement->NextElement;
                    cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n";
                }
                else
                {
                    break;
                }
            }
        }
    }
    
    cout << "\nСписок успешно создан!\n\n";
}
 
///void sohranenie();
///void vosstanovlenie();
 
int main()
{
    //fundamental
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    setlocale(LC_ALL, "Russian");
    srand(time(0));
    //main
    int Vibor = 0;
    int StariyVibor = 0;
    int KolElementov = 0;//PERENOSIMOE (po funktsiyam)
    //hesh
    int KolCollisons = 0;//PERENOSIMOE (po funktsiyam)
    //stuct
    int KolKluchey = 200;//PERENOSIMOE (po funktsiyam)
    int CounterSave = 0;
    HeshList* Heshtable[200];//PERENOSIMOE (po funktsiyam)
    //for struct
    for (int i = 0; i < KolKluchey; i++)
    {
        Heshtable[i] = NULL;
    }
    //
 
 
    for (;;)
    {
        for (;;)
        {
            cout << "Меню\n 1. Создать список\n 2. Найти элемент\n 3. Добавить элемент\n 4. Удалить элемент\n 5. Вывести на экран\n 6. Сохранить список\n 7. Воссатновить список\n 0. Закончить работу\n\nВаш выбор: ";
            cin >> Vibor; cout << "\n";
            if (Vibor < 0 || Vibor > 7)
            {
                cout << "Ошибка: не правильно введен элемент! Введите заново\n\n";
                cout << "____________________________________________________________________________\n\n";
            }
            else
            {
                break;
            }
        }
 
        switch (Vibor)
        {
        case 1://Создание
            if (StariyVibor == 1 || StariyVibor == 2 || StariyVibor == 3 || StariyVibor == 4 || StariyVibor == 5 || StariyVibor == 6 || StariyVibor == 7)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            sozdanie(Heshtable, KolElementov, KolKluchey, KolCollisons);
            StariyVibor = Vibor;
            break;
        case 2://Нахождение
            if (StariyVibor == 0)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            ///nahojdenie();
            StariyVibor = Vibor;
            break;
        case 3://Добавление
            if (StariyVibor == 0)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            ///dobavlenie();
            StariyVibor = Vibor;
            break;
        case 4://Удаление
            if (StariyVibor == 0)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            ///udalenie();
            StariyVibor = Vibor;
            break;
        case 5://Вывод
            if (StariyVibor == 0)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            vivodnaekran(Heshtable, KolElementov, KolKluchey, KolCollisons);
            StariyVibor = Vibor;
            break;
        case 6://Сохранение
            if (StariyVibor == 0)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            if (StariyVibor == 6)
            {
                cout << "Данное действие уже выполнено! Выбите другое!\n\n";
                break;
            }
            CounterSave = 1;
            ///sohranenie();
            StariyVibor = Vibor;
            break;
        case 7://Восстановление
            if (StariyVibor == 0 || StariyVibor == 1)
            {
                cout << "Данное действие не возможно! Выбите другое!\n\n";
                break;
            }
            if (StariyVibor == 7)
            {
                cout << "Данное действие уже выполнено! Выбите другое!\n\n";
                break;
            }
            if (CounterSave != 1)
            {
                cout << "Данное действие невозможно, так как сначала надо сохранить список! \nВыбите другое действие!\n\n";
                break;
            }
            ///vosstanovlenie();
            StariyVibor = Vibor;
            break;
        case 0://Выход
        {
            fstream file("Struct.txt", ios::out | ios::trunc);
            file.close();
        }
        exit(0);
        break;
        }
        cout << "____________________________________________________________________________\n\n";
    }
 
    system("pause");
}

Добавлено через 11 минут
мой вопрос выше был громоздким, выделю главные компоненты

это как формирую

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
for (int i = 0; i < KolElementov; i++)
    {
        int SumOfWord = 0;
 
        FIOtemp = FIOSurName[rand() % 10] + " " + FIOName[rand() % 15] + " " + FIODadName[rand() % 15];
        DOBtemp = DOBDay[rand() % 28] + "/" + DOBMonth[rand() % 12] + "/" + DOBYear[rand() % 21];
        POLtemp = ADRStreet[rand() % 15] + " " + ADRNumber[rand() % 500];
 
        //Find the Key
        for (int i = 0; i < POLtemp.length(); i++)
        {
            SumOfWord = SumOfWord + (int)POLtemp[i];
        }
        if (SumOfWord < 0)
        {
            SumOfWord = SumOfWord * (-1);
        }
        float podstanovka1 = SumOfWord * 0.61;
        Keytemp = trunc(200 * ((podstanovka1)-trunc(podstanovka1)));////KEY IS FOUND
        //
 
 
 
        //PutInHeshTable
        if (Heshtable[Keytemp] == NULL)
        {
            HeshList *HeshElement = new HeshList;
            HeshElement->FIO = FIOtemp;
            HeshElement->DOB = DOBtemp;
            HeshElement->POL = POLtemp;
            Heshtable[Keytemp] = HeshElement;
            HeshElement->NextElement = NULL;
        }
        else
        {
            KolCollisons++;
            HeshList *HeshElement = Heshtable[Keytemp];
            for (int j = 0;; j++)
            {
                if (HeshElement->NextElement != NULL)
                {
                    HeshElement = HeshElement->NextElement;
                }
                else
                {
                    HeshElement = HeshElement->NextElement;
                    HeshElement = new HeshList;
                    HeshElement->FIO = FIOtemp;
                    HeshElement->DOB = DOBtemp;
                    HeshElement->POL = POLtemp;
                    HeshElement->NextElement = NULL;
                    break;
                }
            }
        }
        //
 
    }

это как вывожу

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
for (int i = 0; i < KolKluchey; i++)
    {
        if (Heshtable[i] != NULL)
        {
            cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n";
            cout << "Под данным клучём (" << i + 1 << ") хранятся следующие элементы :\n";
            HeshList *HeshElement = new HeshList;
            HeshElement = Heshtable[i];
            for (;;)
            {
                cout << "ФИО: " << HeshElement->FIO <<"\n";
                cout << "День Рождения: " << HeshElement->DOB <<"\n";
                cout << "Адрес проживания: " << HeshElement->POL <<"\n\n";
                if (HeshElement->NextElement != NULL)
                {
                    HeshElement = HeshElement->NextElement;
                    cout << "- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n\n";
                }
                else
                {
                    break;
                }
            }
        }
    }

Новые блоги и статьи Все статьи Все блоги /
Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .