Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 49, средняя оценка - 4.84
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
#1

Хеш функция - C++

18.10.2012, 22:42. Просмотров 7576. Ответов 30
Метки нет (Все метки)

Здравствуйте. Помогите с задачей.

Таблица строиться по методу цепочек с использованием хэш-функции, возращающий код первой буквы идентификатора. При выполнений программы подсчитывается число коллизий.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2012, 22:42     Хеш функция
Посмотрите здесь:

Хеш функция - C++
Всем добрый день! В общем, нужно подсчитать кол-во коллизий. За это отвечает функция size_t collisions_count(), но почему-то не...

Шаблоны. Хеш-функция - C++
Добрые день. Есть задание сделать телефонную книгу. Поиск в базе сделать через хеш-функцию. name - фамилия абонента. num - номер...

Хеш-функция, двойное хеширование - C++
Всем привет! Пишу курсач, нужна хеш-функция, которая принимала бы строку и возвращала некий индекс. Написал нечто вроде unsigned...

Объясните как работает хеш-функция - C++
int Hash_Function1(DrugStore object) { int result = 0; for (int i = 0; i < SSize+1; i++) result = result +...

Нужна хеш-функция для программы на языке С++ - C++
К моей программе необходимо прикрутить функцию для вычисления хеша. Подскажите, пожалуйста, работоспособный исходник хеш-функции для...

Метод открытого хеширования и хеш-функция, основанная на методе деления с остатком - C++
Ещё раз здравствуйте! Есть такое задание: Написать программу, которая реализует метод открытого хеширования и хеш-функцией,...

Каким образом unordered_map выдает правильное значение для ключа, если его хеш функция допускает коллизии? - C++
Читаю книгу джосаттис стандартная библиотека c++, там в разделе про unordered_map есть описание данного контейнера Раз уж каждый...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexcoder
1462 / 676 / 88
Регистрация: 03.06.2009
Сообщений: 3,506
Завершенные тесты: 1
19.10.2012, 08:56     Хеш функция #2
в гугле забанили?
Хэш-таблица. Метод цепочек. C++
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
19.10.2012, 18:03  [ТС]     Хеш функция #3
Спасибо, но там задание сумму первых 2 букв, а у меня код первой буквы идентификатора
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.10.2012, 10:33     Хеш функция #4
MerlinLegend, да, разница настолько велика, что одним постом и не охватить...
Замените функцию hash на такую:
C++
1
2
3
4
size_t hash(const Identifier& id)
{
    return size_t(id.name()[0]);
}
Для подсчёта числа коллизий можно вставить в класс HashTable такой метод:
C++
1
2
3
4
5
6
7
8
9
10
size_t collisions_count() const
{
    size_t result = 0;
    
    for (size_t i = 0; i < hasn_table_size; ++i)
        if (m_hash_table[i].size() > 1)
            ++result;
    
    return result;
}
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
24.10.2012, 19:17  [ТС]     Хеш функция #5
Спасибо за помощь, но одна проблема

у меня не объявлены переменные я их объявил, но все равно ничего не получается
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 11:47     Хеш функция #6
MerlinLegend, очень информативно. А теперь представьте, что вы не видели код своей программы, и прочтите ваше сообщение. Вы что-нибудь можете из него вынести? Что-нибудь, что могло бы натолкнуть вас на идею, в чём же проблема?
Если не поняли, то вот прямым текстом: как было, что сделали, как стало? Что значит "ничего не получается"? Не включается компьютер? Или музыка играть не начинает? Или всё-таки программа не компилируется или падает в процессе выполнения? И если не компилируется, то что говорит компилятор?
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 12:36  [ТС]     Хеш функция #7
Да вы правы. Ошибка на переменные которые не объявлены.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 12:36     Хеш функция #8
MerlinLegend, видимо, недостаточно прав. Код показывайте.
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 14:04  [ТС]     Хеш функция #9
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
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
 
// Класс "Идентификатор"
// Поскольку это только пример, то в данном случае является просто обёрткой над
// строкой. В реалиности может содержать много дополнительной информации, такой,
// как тип переменной, признак используемости, уровень вложенности и так далее.
class Identifier
{
public:
    // Задаётся имя переменной при создании
    Identifier(const std::string &name):
    m_name(name)
    {
    }
 
public:
    // Получается имя переменной
    std::string name() const
    {
        return m_name;
    }
    
private:
    std::string m_name;
};
 
// Необходимо для поиска переменной по имени
bool operator==(const Identifier &left, const Identifier &right)
{
    return left.name() == right.name();
}
 
// Функция, вычисляющая хэш
// Принимает идентификатор, хэш которого надо посчитать
// Возвращает вычисленный хэш
size_t hash(const Identifier& id)
{
    return size_t(id.name()[0]);
}
// Класс исключение "Идентификатор не найден"
// Нужен для выдачи сообщения о том, что идентификатор не найден в таблице,
// наружу функции поиска идентификатора
class IDNotFoundException : std::exception
{
public:
    IDNotFoundException(const std::string id_name):
    m_what(std::string("Identifier \'") + id_name + "\' not found!")
    {
    }
    
    virtual ~IDNotFoundException() throw()
    {
    }
    
public:
    const char *what() const throw()
    {
        return m_what.c_str();
    }
    
private:
    std::string m_what;
};
 
// Класс "Хэш-таблица", основанная на методе цепочек
// Метод цепочек заключается в следующем: таблица представляет собой массив
// связных списков фиксированного размера. Вычисленный хэш-функцией хэш является
// индексом в этом массиве списков. Известно, что список по этому индексу будет
// содержать все идентификаторы, для которых функция вернула одинаовый хэш.
// Осталось только найти идентификатор в данном списке и возвратить ссылку на
// него.
class HashTable
{
public:
   size_t collisions_count() const
{
    size_t result = 0;
    
    for (size_t i = 0; i < hasn_table_size; ++i)
        if (m_hash_table[i].size() > 1)
            ++result;
    
    return result;
}
public:
    // Добавление идентификатора в хэш-таблицу
    void add(const Identifier &id)
    {
        // Добавление идентификатора в список, расположенный в таблице по
        // индексу, вычисленному хэш-функцией (с учётом смещения)
        m_hash_table[hash(id) - min_hash_value].push_back(id);
    }
    
    // Поиск идентификатора в таблице по имени
    Identifier &get(const std::string &id_name)
    {
        // Сохраняется ссылка на список, в котором потенциально будет
        // расположен идентификатор (для простоты)
        std::list<Identifier>& line = m_hash_table[hash(id_name) - min_hash_value];
        
        // Поиск идентификаторы в списке по имени
        std::list<Identifier>::iterator it =
            std::find(line.begin(), line.end(), id_name);
        
        // Если при поиске были просмотренны все элементы списка,и ни один не
        // подошёл - сообщаем о том, что идентификатор не найден, посредством
        // исключения
        if (it == line.end())
            throw IDNotFoundException(id_name);
        
        // Если идентификатор найден - возвращаем ссылку на него
        return *it;
    }
    
private:
    // Хэш-таблица - массив связных списков идентификаторов
    std::list<Identifier> m_hash_table[hash_table_size];
};
 
int main()
{
    // Создаём хэш-таблицу
    HashTable ht;
    
    // Добавляем в неё различные идентификаторы
    ht.add(Identifier("a"));
    ht.add(Identifier("aa"));
    ht.add(Identifier("if"));
    ht.add(Identifier("fi"));
    
    // На случай, если идентификатор не будет найден, заворачиваем код поиска
    // идентификаторов в блок try/catch
    try
    {
        // Выводим на экран информацию о различных идентификаторах
        std::cout << ht.get("a").name() << std::endl;
        std::cout << ht.get("aa").name() << std::endl;
        std::cout << ht.get("if").name() << std::endl;
        std::cout << ht.get("fi").name() << std::endl;
        // Проверяем случай, когда идентификатор не должен быть найден
        std::cout << ht.get("hello").name() << std::endl;
    }
    catch (const IDNotFoundException &ex)
    {
        // Если идентификатор не найден - сообщаем об этом
        std::cerr << ex.what() << std::endl;
    }
    
    return 0;
}
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 14:07     Хеш функция #10
MerlinLegend, е-моё... Так это программа сама ругается на необъявленный идентификатор? Так и должно быть, я специально показал её реакцию на попытку поиска в таблице отсутствующей записи. Вы пробовали разбираться в коде вообще? Вы понимаете, чего от вас хотят в задании?

Добавлено через 52 секунды
Я же даже комментарий написал специально для... А, ладно...
Строка 143-144:
C++
1
2
// Проверяем случай, когда идентификатор не должен быть найден
std::cout << ht.get("hello").name() << std::endl;
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 17:17  [ТС]     Хеш функция #11
и что в этой строке не так?
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 17:20     Хеш функция #12
MerlinLegend, в этой строке сказано, что специально проверяется случай поиска идентификатора в таблице в то время, когда такого идентификатора там нет. Или у вас всё-таки компилятор ругается на необъявленные переменные? Вообще, почему мне приходится на протяжении 5 сообщений вытягивать из вас информацию? Кому из нас двоих нужна помощь?
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 18:19  [ТС]     Хеш функция #13
Мне нужна помощь. компилятор ругается на необъявленные переменные
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 18:37     Хеш функция #14
MerlinLegend, вы читать умеете?
Цитата Сообщение от silent_1991 Посмотреть сообщение
И если не компилируется, то что говорит компилятор?
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6423 / 3062 / 304
Регистрация: 04.12.2011
Сообщений: 8,351
Записей в блоге: 3
25.10.2012, 18:46     Хеш функция #15
Цитата Сообщение от MerlinLegend Посмотреть сообщение
Мне нужна помощь. компилятор ругается на необъявленные переменные
MerlinLegend, это Ваш вывод о том, что выводит компилятор. А Вы возьмите и скопируйте содержимое output window debugera, а потом выкладывайте его сюда. Съэкономите время.
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 18:52  [ТС]     Хеш функция #16
(121): error C2065: hash_table_size: необъявленный идентификатор
(83): error C2065: hasn_table_size: необъявленный идентификатор
(95): error C2065: min_hash_value: необъявленный идентификатор
(95): error C2228: выражение слева от ".push_back" должно представлять класс, структуру или объединение
(103): error C2065: min_hash_value: необъявленный идентификатор
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 18:58     Хеш функция #17
MerlinLegend, а, ну ё-моё, правильно. Вы зачем из кода что-то удаляли?

Добавлено через 49 секунд
Я же не говорил "замените объявление трёх полей класса на метод collisions_count". Я сказал "добавить в класс метод".

Добавлено через 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
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
 
class Identifier
{
public:
    Identifier(const std::string& name):
    m_name(name)
    {
    }
    
public:
    std::string name() const
    {
        return m_name;
    }
    
private:
    std::string m_name;
};
 
bool operator==(const Identifier& left, const Identifier& right)
{
    return left.name() == right.name();
}
 
size_t hash(const Identifier& id)
{
    return size_t(id.name()[0]);
}
 
class IDNotFoundException : std::exception
{
public:
    IDNotFoundException(const std::string id_name):
    m_what(std::string("Identifier \'") + id_name + "\' not found!")
    {
    }
    
    virtual ~IDNotFoundException() throw()
    {
    }
    
public:
    const char *what() const throw()
    {
        return m_what.c_str();
    }
    
private:
    std::string m_what;
};
 
class HashTable
{
public:
    static const size_t min_hash_value = int('A') + int('0');
    static const size_t max_hash_value = int('z') + int('z');
    static const size_t hash_table_size = max_hash_value - min_hash_value;
    
public:
    void add(const Identifier& id)
    {
        m_hash_table[hash(id) - min_hash_value].push_back(id);
    }
    
    Identifier& get(const std::string& id_name)
    {
        std::list<Identifier>& line = m_hash_table[hash(id_name) - min_hash_value];
        
        std::list<Identifier>::iterator it =
            std::find(line.begin(), line.end(), id_name);
        
        if (it == line.end())
            throw IDNotFoundException(id_name);
        
        return *it;
    }
    
    size_t collisions_count() const
    {
        size_t result = 0;
        
        for (size_t i = 0; i < hasn_table_size; ++i)
            if (m_hash_table[i].size() > 1)
                ++result;
        
        return result;
    }
    
private:
    std::list<Identifier> m_hash_table[hash_table_size];
};
 
int main()
{
    HashTable ht;
    
    ht.add(Identifier("a"));
    ht.add(Identifier("aa"));
    ht.add(Identifier("if"));
    ht.add(Identifier("fi"));
    
    try
    {
        std::cout << ht.get("a").name() << std::endl;
        std::cout << ht.get("aa").name() << std::endl;
        std::cout << ht.get("if").name() << std::endl;
        std::cout << ht.get("fi").name() << std::endl;
        std::cout << ht.get("hello").name() << std::endl;
    }
    catch (const IDNotFoundException& ex)
    {
        std::cerr << ex.what() << std::endl;
    }
    
    return 0;
}
Наслаждайтесь.

Добавлено через 1 минуту
М, вот ещё что. Размер хэш-таблицы тоже поменялся. Поэтому строки 59-60 надо заменить на такие:
C++
1
2
    static const size_t min_hash_value = int('0');
    static const size_t max_hash_value = int('z');
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:12  [ТС]     Хеш функция #18
Спасибо за помощь. Но у меня снова ошибка (87): error C2065: hasn_table_size: необъявленный идентификатор
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 19:14     Хеш функция #19
MerlinLegend, ну как он может быть необъявленным, если он объявляется в 61 строке? Вы опять что-то лишнее удалили?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2012, 19:16     Хеш функция
Еще ссылки по теме:

Хеш таблица - C++
Нужно написать прогу которая подсчитает количество слов, с помощью хеш таблицы. Но хотоелось бы посмотреть на примеры программ их...

Хеш таблицы - C++
Начал изучать хеш таблицы. Подскажите насчёт хеш таблиц с открытимы адрессами: - Должны ли мы инициализировать значение ключа...

Хеш таблица - C++
Скажите, в чём польза от хеш-таблицы? Только в скорости поиска?

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

хеш-таблицы - C++
Реализовать ассоциативный массив в виде хеш-таблицы с операциями добавления, поиска . Ключом массива должна быть строка, значением – целое...


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

Или воспользуйтесь поиском по форуму:
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:16  [ТС]     Хеш функция #20
Нет, все как вы вы говорили
Yandex
Объявления
25.10.2012, 19:16     Хеш функция
Ответ Создать тему
Опции темы

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