Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
1

Вывод хеш-таблицы

11.11.2019, 01:03. Просмотров 1172. Ответов 16
Метки нет (Все метки)

Доброго времени суток! Проблема с функцией Print - не могу понять, почему не выводит хеш-таблицу. То выводит что-то, то нет, то выводит только последнюю введенную пару. Да, могут быть коллизии, это уже следующая лабораторная, но я ввожу разные данные и оно всё равно выводится не так или не выводится совсем. Буду очень благодарна, если подскажете, что я сделала не так

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
    class Element
    {
        public int Key { get; set; }
        public int Value { get; set; }
 
        public Element(int Key, int Value)
        {
            if (string.IsNullOrEmpty(Key))
            {
                throw new ArgumentNullException(nameof(Key));
            }
 
            if (string.IsNullOrEmpty(Value))
            {
                throw new ArgumentNullException(nameof(Value));
            }
 
            this.Key = Key;
            this.Value = Value;
        }
    }
 
    class HashTable
    {
        int size;
        Element[] HTable;
        public HashTable(int size)
        {
            this.size = size;
            HTable = new Element[size];
        }
        int hash(int key)
        {
            return key % size;
        }
 
        public void Print()
        {
            for (int i = 0; i < HTable.Length; i++)
            {
                if (HTable[i]!= null)
                    Console.WriteLine("{0} - {1}", HTable[i].Value, HTable[i].Key);
                else
                    Console.WriteLine("null"); 
            }
        }
 
        public void Add(int value, int key)
        {
            int hashNumber = hash(key);
            HTable[hashNumber] = new Element(key, value);
            for (int i = 0; i < HTable.Length; i++)
            {
                Console.WriteLine("Введите значение: ");
                int val = Convert.ToInt32(Console.ReadLine());
                Console.WriteLine("Введите ключ: ");
                int anotherKey = Convert.ToInt32(Console.ReadLine());
            }
        }
 
        public void Delete(int key)
        {
            HTable[hash(key)] = null;
        }
 
        public void Find(int key)
        {
            for (int i = 0; i < HTable.Length; i++)
                if (HTable[i].Key == key)
                {
                    Console.WriteLine("Ваш элемент: {0} - {1}", HTable[i].Value, HTable[i].Key);
                    return;
                }
            Console.WriteLine("Элемент не найден");
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Введите количество элементов: ");
            int Size = Convert.ToInt32(Console.ReadLine());
            HashTable h = new HashTable(Size);
            bool flag = true;
            while (flag)
            {
                Console.WriteLine("\n Пожалуйста, введите цифру - выберите действие ");
                Console.WriteLine("1 - добавить элемент");
                Console.WriteLine("2 - удалить элемент");
                Console.WriteLine("3 - поиск элемента по ключу");
                Console.WriteLine("4 - показать таблицу");
                Console.WriteLine("5 - выйти из меню");
                int n = Convert.ToInt32(Console.ReadLine());
                switch (n)
                {
                    case 1:
                        for (int i = 0; i < Size; i++)
                        {
                            Console.WriteLine("Введите значение: ");
                            int val = Convert.ToInt32(Console.ReadLine());
                            Console.WriteLine("Введите ключ: ");
                            int anotherKey = Convert.ToInt32(Console.ReadLine());
                            h.Add(val, anotherKey);
                        }
                        break;
 
                    case 2:
                        Console.WriteLine("Введите ключ: ");
                        int yourKey = Convert.ToInt32(Console.ReadLine());
                        h.Delete(yourKey);
                        break;
 
                    case 3:
                        Console.WriteLine("Введите ключ");
                        int keey = Convert.ToInt32(Console.ReadLine());
                        h.Find(keey);
                        break;
 
                    case 4:
                        Console.WriteLine("Хеш-таблица:");
                        h.Print();
                        break;
 
                    case 5:
                        flag = false;
                        break;
 
                    default:
                        Console.WriteLine("Ошибка! ");
                        break;
 
                }
            }
            Console.ReadKey();
        }
    }
}
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2019, 01:03
Ответы с готовыми решениями:

Хеш-таблицы
Здраствуйте, уважаемые программисты. Обьясните чайнику какая разница между хеш-таблицой к примеру и...

16

Usaga
Эксперт .NET
6172 / 4384 / 767
Регистрация: 21.01.2016
Сообщений: 17,127
Завершенные тесты: 2
11.11.2019, 04:05 2
Цитата Сообщение от kira00 Посмотреть сообщение
Буду очень благодарна, если подскажете, что я сделала не так
Не используете отладчик (debugger). Или условиями лабораторной явно было запрещено отлаживать свою программу?
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
11.11.2019, 18:50 3
kira00, если сильно не придираться к коду, то
1) метод hash() делает полную ерунду. все проблемы из за него
2) действие 1 - добавить элемент, а по факту заполняете всю хеш-таблицу, учитывайте тот факт что данные могут перезаписываться. Ключ будет тот же, значение изменится
3) Цикл в методе Add() - трата вашего времени
0
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
11.11.2019, 19:54  [ТС] 4
Насчёт Add() я сегодня уже всё переделала, потому что мне объяснили, что так делать - очень тупо.
А что не так с hash()? Обычная, примитивная хеш-функция. Что не так она делает?
0
11.11.2019, 19:54
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
11.11.2019, 20:01 5
Цитата Сообщение от kira00 Посмотреть сообщение
А что не так с hash()
что он вообще делает?
Вот на данный момент данный метод берет остаток от деления (смысл от этого ?) от ключа, который является типов int. А если ключом будет тип string ? char ? какой нибудь класс ? Данный метод рушит всю суть хеш-таблицы, если не учитывать того факта, что он даже неверную логику выдает.
0
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
11.11.2019, 20:06  [ТС] 6
Суть в том и состоит, что я сделала "примитивную" хеш-таблицу integer и сейчас работаю над разрешением коллизий разными способами, чтобы лучше понять смысл.
Ну, а в функции мы делим ключ на количество элементов, чтобы использовать остаток от деления как индекс в таблице.
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
11.11.2019, 20:21 7
Цитата Сообщение от kira00 Посмотреть сообщение
использовать остаток от деления как индекс в таблице
Без кода попробую объяснить
Длина массива HTable равна 10;
Код
Хэш.Добавить (ключ - 10, значение 111);
    ключ 10 % длина массива 10 = 0.
    массив[индекс 0] = <ключ 10, значение 111>
Хэш.Добавить (ключ - 20, значение 222);
    ключ 20 % длина массива 10 = 0.
    массив[индекс 0] = <ключ 20, значение 222> // значение перезаписали
Хэш.Добавить (ключ - 30, значение 333);
    ключ 30 % длина массива 10 = 0.
    массив[индекс 0] = <ключ 30, значение 333> // значение перезаписали
Вывод?
Кстати почему отказались от списка List что я дал вам в предыдущий раз ?
0
QuestionAnd
58 / 43 / 17
Регистрация: 12.08.2019
Сообщений: 161
11.11.2019, 20:44 8
Цитата Сообщение от Enifan Посмотреть сообщение
Данный метод рушит всю суть хеш-таблицы,
Enifan, с функцией там нормально, для начала пойдет.
Цитата Сообщение от Enifan Посмотреть сообщение
почему отказались от списка List
нужна хэш-таблица , а не просто таблица
поиск, вставка, удаление элементов за O(1)
а у Вас за O(N)
1
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
11.11.2019, 21:43  [ТС] 9
Да, там суть в том была, чтобы всё-всё сделать самому, без словарей/списков, обязательно с массивом.
А для решения коллизий в этой лабораторной нужно использовать 2 способа - метод цепочек и открытую адресацию, получается, что для метода цепочек мне нужно создать связный список?
То есть, каждая ячейка массива является указателем на связный список пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Как это можно реализовать?
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
11.11.2019, 22:22 10
Цитата Сообщение от QuestionAnd Посмотреть сообщение
поиск, вставка, удаление элементов за O(1)
kira00, в таком случаи избавляемся от методов Add() и Find()
Как справитесь - подумайте над альтернативой hash(). Сможете это реализовать - Хэш-таблица через массив будет готова полностью.
Потом уже методом цепочек.
Если завтра будет время, скину 2 таблицы (массив и цепочки)
0
jester
198 / 121 / 48
Регистрация: 18.03.2016
Сообщений: 617
Завершенные тесты: 4
11.11.2019, 23:24 11
Enifan,
Цитата Сообщение от Enifan Посмотреть сообщение
в таком случаи избавляемся от методов Add() и Find()
Как справитесь - подумайте над альтернативой hash(). Сможете это реализовать - Хэш-таблица через массив будет готова полностью.


kira00,
Хеш-таблица
http://algolist.ru/ds/s_has.php
Хеш-таблица с открытой адресацией
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
11.11.2019, 23:32 12
jester, жду реализации поиска элемента за O(1), как желают ув. коллеги данного сайта
0
jester
198 / 121 / 48
Регистрация: 18.03.2016
Сообщений: 617
Завершенные тесты: 4
12.11.2019, 00:58 13
Enifan, https://neerc.ifmo.ru/wiki/index.php...BD.D0.B8.D1.8F

Хеш-таблицу делать не так интересно как кучу?
0
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
12.11.2019, 01:04  [ТС] 14
Кто-нибудь может здесь объяснить, как решать коллизии обоими способами? Я запуталась
Я так поняла, для открытой адресации создаём связный список, функция Add теперь будет добавлять элемент в начало списка
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
13.11.2019, 14:17 15
Лучший ответ Сообщение было отмечено kira00 как решение

Решение

Самой просто реализацией хеш таблицы является массив + метод Hash()
Плюсы:
+ Поиск, удаление, вставка элемента происходит за O(1)
Минусы:
- Проблемы с коллизией
- Ограниченный размер данных
Кликните здесь для просмотра всего текста
C#
1
int?[] a = new int?[10];


kira00, Почему я грешил на ваши методы Hash(), Add(), Find(). Потому что они скорее портили код, чем делали пользу. Они конечно нужны, но не в такой реализации. Весь ваш код, за исключением меню, можно организовать за пару строк, польза будет таже. Вы просто перезаписываете значение, потому и вывод таблицы идет не так, как вы планировали.
Кликните здесь для просмотра всего текста
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
using System;
using System.Collections.Generic;
 
class Program
{
    static int LENGTH = 10;
 
    static int Hash(int key)
    {
        return key % LENGTH;
    }
 
    static void Main()
    {
        KeyValuePair<int, int>[] arr = new KeyValuePair<int, int>[LENGTH];
 
        KeyValuePair<int, int> kvp1 = new KeyValuePair<int, int>(1, 111);
        KeyValuePair<int, int> kvp2 = new KeyValuePair<int, int>(11, 222);
        KeyValuePair<int, int> kvp3 = new KeyValuePair<int, int>(21, 333);
 
        arr[Hash(kvp1.Key)] = kvp1;
        arr[Hash(kvp2.Key)] = kvp2;
        arr[Hash(kvp3.Key)] = kvp3;
 
        arr[Hash(1)] = new KeyValuePair<int, int>(0, 0); // почти null
 
        foreach (var kvp in arr)
            Console.WriteLine(kvp.Key + " " + kvp.Value);
 
        int?[] a = new int?[10];
 
        Console.ReadKey();
    }
}


Открытое хеширование (метод цепочек)
Плюсы:
+ Добавление элементов за O(1)
+ Поиск и удаление элементов от O(1) до O(N), где N - хеш-код / хеш-индекс
+ Неограниченное кол-во добавления элементов
Минусы:
- При проверке одинаковых ключей добавление элементов будет происходить до O(N + 1)
Реализаций может быть много, вот отдельный пример
Кликните здесь для просмотра всего текста
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
using System;
 
class ElementRef
{
    public Element Next;
 
    public ElementRef()
    {
        Next = null;
    }
}
 
class Element : ElementRef
{
    public readonly int Key;
    public readonly string Value;
 
    public Element(int key, string value)
    {
        Key = key;
        Value = value;
    }
 
    public override string ToString()
    {
        return $"[{Key}: {Value}]";
    }
}
 
// Открытое хеширование (метод цепочек)
class HashTable
{
    ElementRef[] arr;
 
    public HashTable(int length)
    {
        arr = new ElementRef[length];
        for (int i = 0; i < arr.Length; i++)
            arr[i] = new ElementRef();
    }
 
    public void Insert(int key, string value)
    {
        Insert(new Element(key, value));
    }
 
    public void Insert(Element element)
    {
        int index = Hash(element.Key);
        element.Next = arr[index].Next;
        arr[index].Next = element;
    }
 
    public Element Find(int key)
    {
        for (Element el = arr[Hash(key)].Next; el != null; el = el.Next)
        {
            if (el.Key == key)
                return el;
        }
        return null;
    }
 
    public bool Delete(int key)
    {
        ElementRef prev = arr[Hash(key)];
        for (Element el = arr[Hash(key)].Next; el != null; el = el.Next, prev = prev.Next)
        {
            if (el.Key == key)
            {
                prev = el.Next;
                return true;
            }
        }
        return false;
    }
 
    int Hash(int key)
    {
        return key % arr.Length;
    }
 
    public void PrintHash()
    {
        Console.WriteLine("\tХеш-таблица");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write($"{i,-2} хеш-индекс: ");
            PrintHashNumber(i);
            Console.WriteLine();
        }
    }
 
    void PrintHashNumber(int index)
    {
        for (Element el = arr[index].Next; el != null; el = el.Next)
            Console.Write(el.ToString() + " ");
    }
}
 
class Program
{
    static void Main()
    {
        HashTable hash = new HashTable(10);
        hash.Insert(new Element(5, "пять"));
        hash.Insert(new Element(15, "пятнадцать"));
        hash.Insert(new Element(25, "двадцать пять"));
        hash.Insert(new Element(25, "опять двадцать пять"));
        hash.Insert(6, "шесть");
        hash.PrintHash();
 
        hash.Delete(5);
        hash.Delete(25);
        if (hash.Delete(99) == false)
            Console.WriteLine($"Ключа {99} не существет, удаление невозможно");
        hash.PrintHash();
 
        Element element = hash.Find(15);
        if (element != null)
            Console.WriteLine("Элемент: " + element.ToString());
 
        Console.ReadKey();
    }
}


Закрытое хеширование сможете организовать?
0
kira00
0 / 0 / 0
Регистрация: 12.05.2019
Сообщений: 28
13.11.2019, 15:13  [ТС] 16
Добрый день) Спасибо Вам огромное, буду изучать код.
Уже в университете смогла с помощью друга написать и понять, что и как.
Насчёт закрытого хеширования пока не знаю, сделали метод Add().
C#
1
2
3
4
5
6
7
8
9
10
11
12
 void Add(int key, int value)
        {
            int hashnumber = hash(key);
            for (int i = 0; i < ClosedHTable.Length; i++)
            {
                ClosedNode tmp = ClosedHTable[(i + hashnumber) % ClosedHTable.Length];
                if (tmp == null || tmp.isDeleted)
                {
                    ClosedHTable[(i + hashnumber) % ClosedHTable.Length] = new ClosedNode(key, value);
                    break;
                }
            }
Буду думать над Find(), Delete() и Print().
0
Enifan
175 / 117 / 60
Регистрация: 14.10.2018
Сообщений: 434
Завершенные тесты: 1
13.11.2019, 15:15 17
kira00, прежде чем думать над методом Add(), определитесь, будут ли у вас храниться одинаковые ключи элементов. От этого реализация метода может отличаться
0
13.11.2019, 15:15
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2019, 15:15

Отрицательный хеш-код в реализации таблицы
Здравствуйте. Ковыряюсь в структурах данных и наткнулся на такую проблему. Так как для поиска...

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

Или воспользуйтесь поиском по форуму:

17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.