Хэширование и поиск

@GFox89 · Регистрация: 20.05.2020

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

Прошу помощи студентке 2 курса... В С++ очень слаба, прошу прощения за корявый код. Задание:
1. Разработать подпрограмму хеширования массива целых чисел методом прямого связывания и подпрограмму поиска в хэш-таблице элемента по заданному ключу. Вывести на экран построенную хэш-таблицу.
Номер ячейки 0 1 2 3 … … m-1
Число
2. Реализовать подпрограмму хеширования массива целых чисел методом открытой адресации. Для разрешения коллизий использовать линейные и квадратичные пробы.
Вывести на экран заполненные хеш-таблицы для m=11 в виде
3. Подсчитать и сравнить количество коллизий при линейных и квадратичных пробах. Построить таблицу и проанализировать полученные результаты:
4. Организовать поиск элемента с заданным ключом для метода открытой адресации (линейные и квадратичные пробы).

Реализация пока такая:

C++

#include "pch.h"
#include <iostream>
 
using namespace std;
 
int m; // Размер хеш-таблицы
int table[100]; // Хеш-таблица
int n; // Размер массива чисел
int a[100]; // Массив чисел
bool overflow; // Равна true, если было переполнение таблицы
int collisions; // Количество коллизий
// Вычисляет хеш-функцию
int HashF(int num)
{
    return num % m;
}
// Создает хеш-таблицу методом линейных проб
void CreateTable1()
{
    int i;
    for (i = 0; i < m; i++) // Очищаем хэш-таблицу
        table[i] = 0;
    collisions = 0;
    int h, h0, g;
    for (i = 0; i < n; i++) {
        h = HashF(a[i]);
        h0 = h;
        g = 1;
        while (1) {
            if (table[h] == a[i]) // Если число повторяется
                break;
            if (table[h] == 0) { // Если нашли пустое место в хэш-таблице
                table[h] = a[i];
                break;
            }
            if (g >= m) { // Если переполнение
                overflow = true;
                return;
            }
            collisions++;
            h = h0 + g;
            if (h >= m)
                h -= m;
            g++;
        }
    }
    overflow = false;
}
 
// Создает хеш-таблицу методом квадратичных проб
void CreateTable2()
{
    int i;
    for (i = 0; i < m; i++) // Очищаем хэш-таблицу
        table[i] = 0;
    collisions = 0;
    int h, d;
    for (i = 0; i < n; i++) {
        h = HashF(a[i]);
        d = 1;
        while (1) {
            if (table[h] == a[i]) // Если число повторяется
                break;
            if (table[h] == 0) { // Если нашли пустое место в хэш-таблице
                table[h] = a[i];
                break;
            }
            if (d >= m) { // Если переполнение
                overflow = true;
                return;
            }
            collisions++;
            h += d;
            if (h >= m)
                h -= m;
            d += 2;
        }
    }
    overflow = false;
}
// Выводит хеш-таблицу на экран
void ShowTable()
{
    if (m == 11) {
        cout << ("------------------------------------------------------------------------\n");
        cout << ("| Номер ячейки |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |\n");
        cout << ("------------------------------------------------------------------------\n");
        cout << ("| Число        | ");
        for (int i = 0; i < m; i++)
            if (table[i] != 0)
                cout << " " << table[i] << " |";
            else
                cout << "   | ";
        cout << endl;
        cout << ("-----------------------------------------------------------------------\n");
    }
    if (!overflow)
        cout << ("Переполнения таблицы не было\n");
    else
        cout << ("Возникло переполнение таблицы\n");
    cout << ("Количество коллизий: ");
    cout << collisions << endl;
}
// Ищет число в хеш-таблице, построенной методом линейных проб
bool Search1(int num)
{
    int h, h0, g;
    h = HashF(num);
    h0 = h;
    g = 1;
    while (1) {
        if (table[h] == num) // Если число найдено
            return true;
        if (g >= m) // Если переполнение
            return false;
        h = h0 + g;
        if (h >= m)
            h -= m;
        g++;
    }
}
// Ищет число в хеш-таблице, построенной методом квадратичных проб
bool Search2(int num)
{
    int h, d;
    h = HashF(num);
    d = 1;
    while (1) {
        if (table[h] == num) // Если число найдено
            return true;
        if (d >= m) // Если переполнение
            return false;
        h += d;
        if (h >= m)
            h -= m;
        d += 2;
    }
}
 
 
int main(int argc, char* argv[])
{
    setlocale(LC_CTYPE, "Russian");
    cout << ("Введите размер хеш-таблицы: ");
    cin >> m;
    cout << ("Введите количество исходных чисел: ");
    cin >> n;
    int num; // Число для поиска
 
    int i;
    for (i = 0; i < n; i++) // Заполним массив чисел
        a[i] = rand() % n + 10;
    cout << ("Метод линейных проб:\n");
    CreateTable1();
    ShowTable();
    cout << ("Введите число для поиска: ");
    cin >> num;
    if (Search1(num))
        cout << ("Число было найдено\n");
    else
        cout << ("Число было не найдено\n");
    cout << ("\nМетод квадратичных проб:\n");
    CreateTable2();
    ShowTable();
    cout << ("Введите число для поиска: ");
    cin >> num;
    if (Search2(num))
        cout << ("Число было найдено\n");
    else
        cout << ("Число было не найдено\n");
 
    system("pause");
    return 0;
}

вроде бы корректно, но все время вылазит то одна, то другая ошибка. Осложняется все вечными лагами Вижлы 2019, из-за этого непонятно, где именно мой косяк - приходится скакать с компа на комп, то на винду 10, то на семерку. Подскажите, пож, что можно исправить в коде

@XLAT · 18.04.2021, 16:09

GFox89,
сразу заметно, что для такого алгоритма вычисления хеша:

Сообщение от GFox89

C++

int HashF(int num)
{
    return num % m;
}

количество ячеек, которые вам понадобятся будет равно = 10

а у вас тут:

Сообщение от GFox89

C++

85
86
87

        cout << ("------------------------------------------------------------------------\n");
        cout << ("| Номер ячейки |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |\n");
        cout << ("------------------------------------------------------------------------\n");

их аж 11

это конешъ мелочь, но не для арифметики.

@XLAT · 18.04.2021, 17:57

Сообщение от GFox89

но все время вылазит то одна, то другая ошибка

гляньте это:

C++

#include "pch.h"
#include <iostream>
#include <iomanip>
 
using namespace std;
 
int m = 10;            // Размер хеш-таблицы
int table[1000] = {0}; // Хеш-таблица
int n;                 // Размер массива чисел
int a[1000];           // Массив чисел
bool overflow;         // Равна true, если было переполнение таблицы
int collisions;        // Количество коллизий
// Вычисляет хеш-функцию
int HashF(int num)
{   return num % m;
}
// Создает хеш-таблицу методом линейных проб
void CreateTable1()
{   int i;
    for (i = 0; i < 1000; i++) // Очищаем хэш-таблицу
        table[i] = -1;
    
    collisions = 0;
    
    int h, h0, g;
    for(i = 0; i < n; i++)
    {   h  = HashF(a[i]);
        h0 = h;
        g  = 1;
        while (1)
        {   if (table[h] == a[i]) // Если число повторяется
                break;
            if (table[h] == -1)   // Если нашли пустое место в хэш-таблице
            {   table[h] = a[i];
                break;
            }
            if (g >= m)           // Если переполнение
            {   overflow = true;
                return;
            }
            collisions++;
            h = h0 + g;
            if (h >= m)
                h -= m;
            g++;
        }
    }
    overflow = false;
}
 
// Создает хеш-таблицу методом квадратичных проб
void CreateTable2()
{   int i;
    for (i = 0; i < 1000; i++) // Очищаем хэш-таблицу
        table[i] = -1;
 
    collisions = 0;
    int h, d;
    for (i = 0; i < n; i++)
    {   h = HashF(a[i]);
        d = 1;
        while (1)
        {   if (table[h] == a[i]) // Если число повторяется
                break;
            if (table[h] == -1)   // Если нашли пустое место в хэш-таблице
            {   table[h] = a[i];
                break;
            }
            if (d >= m)   // Если переполнение
            {   overflow = true;
                return;
            }
            collisions++;
            h += d;
            if (h >= m)
                h -= m;
            d += 2;
        }
    }
    overflow = false;
}
 
// Выводит хеш-таблицу на экран
void ShowTable()
{
    cout << ("-----------------------------------------------------------\n");
    cout << ("| Хеш   |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |\n");
    cout << ("-----------------------------------------------------------\n");
    cout << ("| Число |");
    for (int i = 0; i < 10; i++)
        cout << setw(3) << table[i] << " |";
    cout << endl;
    cout << "------------------------------------------------------------\n";
    
    if (!overflow) cout << "Переполнения таблицы не было\n" ;
    else           cout << "Возникло переполнение таблицы\n";
    cout << "Количество коллизий: " << collisions << endl;
}
 
// Ищет число в хеш-таблице, построенной методом линейных проб
bool Search1(int num)
{   int h = HashF(num);
    for(int g = h; g < m; ++h)
    {   if (table[h] == num) // Если число найдено
            return true;
    }
    return false; // Если переполнение
}
 
// Ищет число в хеш-таблице, построенной методом квадратичных проб
bool Search2(int num)
{   int h, d;
    h = HashF(num);
    d = 1;
    while (1)
    {   if (table[h] == num) // Если число найдено
            return true;
        if (d >= m) // Если переполнение
            return false;
        h += d;
        if (h >= m)
            h -= m;
        d += 2;
    }
}
 
int main(int argc, char* argv[])
{   setlocale(LC_CTYPE, "Russian");
    cout << ("Введите размер хеш-таблицы       : ") << m << '\n'; //cin >> m;
    cout << ("Введите количество исходных чисел: "); cin >> n;
 
    for (int i = 0; i < n; i++)
    {   a[i] = rand() % m + 10;
        std::cout << a[i] << ' ';
    }
    
    cout << ("\n\nМетод линейных проб:\n");/////////////////////////////////////
    CreateTable1();
    ShowTable();
 
    // Число для поиска
    int k; cout << ("Введите число для поиска: "); cin >> k;
 
    if (Search1(k))
        cout << ("Число было найдено\n");
    else
        cout << ("Число было не найдено\n");
        
    cout << ("\nМетод квадратичных проб:\n");///////////////////////////////////
    CreateTable2();
    ShowTable   ();
 
    cout << ("Введите число для поиска: ");
    cin >> k;
 
    if (Search2(k))
        cout << ("Число было найдено\n");
    else
        cout << ("Число было не найдено\n");
 
    system("pause");
    return 0;
}

если что вылазит, то пишите конкретно со всеми подробностями про ошипку.

@Ksardas02 · 21.09.2021, 21:45

Нашел проблему с коллизиями, при любом раскладе цифры в твоем примере будут совпадать с индексами, а если изменить немного рандом, то программа научится улавливать коллизии, еще можно добавить srand( time( NULL )); для полного кайфа, тогда все будет работать как часы

C++

1	a[i] = rand() % 100;

	21.09.2021, 21:45

Хэширование и поиск

Решение