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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 119, средняя оценка - 4.69
PlayaRC
5 / 5 / 0
Регистрация: 10.03.2012
Сообщений: 121
#1

Хэш-таблица. Метод цепочек. C++ - C++

10.03.2012, 19:32. Просмотров 18305. Ответов 10
Метки нет (Все метки)

Уважаемые, программисты, задание звучит так: "Таблица строится по методу цепочек с использованием хеш-функции, возвращающей сумму двух первых букв идентификатора."
Судя из задания созрело несколько вопросов:
1) "...возвращающей сумму двух первых букв идентификатора". Сумма первых двух букв идентификатора - это сумма АСКИ-кодов этих букв, так?
2) Напишите, пожалуйста, очень простой пример работы с хеш-таблицей по методу цепочек, буквально вообще примитивный, чтобы понять работу алгоритма!
Заранее спасибо за ответы!
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.03.2012, 19:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Хэш-таблица. Метод цепочек. C++ (C++):

Хэш-таблица (метод цепочек) - C++
Пишу частотный словарь текста: Массив списков узлов. В узле значение и частота слова. При написании функции void add столкнулся с...

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

Хеш-таблица (метод цепочек) - C++
Дано: файл на 1ккк больших чисел. Задача: 1. Построить хеш-таблицу любым методом. 2. Обчислить количество возможных разных значений...

Хеш таблица с функцией (метод цепочек) - C++
1) Не смотрите на хеш функцию, она наитупейшая, я еще над ней не работал. 2)Метод цепочек заключается в том, если в ячейке массива есть...

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию - C++
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include <iostream> #include <vector> #include <list> #include...

Хэш-таблица - C++
Ребят, помогите, пожалуйста, решить задачу: Хэш-функция определена как h(k) = k mod 11. Вводится последовательность N натуральных...

10
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
10.03.2012, 20:40 #2
1) Да, сумма ASCII-кодов символов.
2) Простой и примитивный не получится. Либо полностью реализовать задание, либо описать только алгоритм. Однако чтобы понять алгоритм, можно использовать классы стандартной библиотеки и стандартные алгоритмы. Если у вас нет ограничений на используемые инструменты - берите нижеследующий код и пользуйтесь. Если надо всё написать вручную, что ж... Пишите собственные упрощённые реализации используемых классов и алгоритмов и, опять же, пользуйтесь))
Код:
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
#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)
{
    if (id.name().length() == 1)
        return 2 * size_t(id.name()[0]);
    
    return size_t(id.name()[0]) + size_t(id.name()[1]);
}
 
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;
    }
    
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;
}
2
PlayaRC
5 / 5 / 0
Регистрация: 10.03.2012
Сообщений: 121
11.03.2012, 12:10  [ТС] #3
Однако чтобы понять алгоритм, можно использовать классы стандартной библиотеки и стандартные алгоритмы. Если у вас нет ограничений на используемые инструменты - берите нижеследующий код и пользуйтесь. Если надо всё написать вручную, что ж... Пишите собственные упрощённые реализации используемых классов и алгоритмов и, опять же, пользуйтесь))
silent_1991, спасибо большое, код хорошо работает!
Просто в классах трудно разобраться, тем более в алгоритме. Может у кого-то есть код без классов? Если да, то скиньте или дайте ссылку, заранее спасибо!
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
11.03.2012, 12:29 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Может так будет понятнее:
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
#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)
{
    // Если имя переменной составляет один символ - возвращается его код,
    // умноженный на два
    if (id.name().length() == 1)
        return 2 * size_t(id.name()[0]);
    
    // Иначе возвращается сумма кодов первых двух символов
    return size_t(id.name()[0]) + size_t(id.name()[1]);
}
 
// Класс исключение "Идентификатор не найден"
// Нужен для выдачи сообщения о том, что идентификатор не найден в таблице,
// наружу функции поиска идентификатора
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;
    }
    
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;
}
7
PlayaRC
5 / 5 / 0
Регистрация: 10.03.2012
Сообщений: 121
11.03.2012, 13:16  [ТС] #5
спасибо большое, так понятнее)
0
77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
27.04.2012, 20:35 #6
silent_1991, а если нужно подсчитать среднее количество сравнений и коллизий, выполняемых при поиске идентификатора в таблице, то get уже не подходит? нужно как-то иначе организовать поиск?
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.04.2012, 17:04 #7
77Bender77, да нет, всё также. Количество сравнений можно получить, вставив подсчёт в перегруженный оператор ==. Количество коллизий тоже легко посчитать, в данном случае это количество элементов в таблице минус размер таблицы.
1
77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
15.05.2012, 22:00 #8
Цитата Сообщение от silent_1991 Посмотреть сообщение
77Bender77, да нет, всё также. Количество сравнений можно получить, вставив подсчёт в перегруженный оператор ==. Количество коллизий тоже легко посчитать, в данном случае это количество элементов в таблице минус размер таблицы.
если вставлять подсчет сравнений в перегруженный оператор ==, то он будет считать только кол-во сравнений в связаном списке (т.е. если коллизий нет, то результат =1, если есть, то результат = номеру идентификатора из всех коллизий). пробовал изменить стандартную библиотеку algorithm.сс, вставляя подсчет в функцию std::find, но получалось еще кривее(
есть идеи по этому поводу?
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.05.2012, 11:27 #9
77Bender77, погодите, а какие ещё сравнения вам нужны? Список, в котором надо искать, вычисляется сразу (за счёт известного размера хеш-таблицы и вычисления нужного индекса через хеш-функцию). А затем алгоритм std::find, применяя перегруженный вами оператор сравнения, ищет элемент.

Цитата Сообщение от 77Bender77 Посмотреть сообщение
пробовал изменить стандартную библиотеку algorithm.сс, вставляя подсчет в функцию std::find
А-та-та, вот по рукам за такое.
0
77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
16.05.2012, 17:16 #10
silent_1991,
да, вы правы, то я не понял сначала принцип поиска, но потом уже вечером разобрался)
0
MrGluck
Модератор
Эксперт CЭксперт С++
7423 / 4538 / 673
Регистрация: 29.11.2010
Сообщений: 12,319
16.05.2012, 17:20 #11
Цитата Сообщение от 77Bender77 Посмотреть сообщение
пробовал изменить стандартную библиотеку algorithm.сс, вставляя подсчет в функцию std::find, но получалось еще кривее(
есть идеи по этому поводу?
std::find_if
0
16.05.2012, 17:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2012, 17:20
Привет! Вот еще темы с ответами:

Хэш-таблица - C++
Задание реализовать динамическую хеш-таблицу с открытой адресацией для хранения строк (операции вставки и поиска). Таблица должна...

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

Хэш таблица - C++
Как работает метод цепочек, для разрешения коллизий в хэш таблице?

Хэш таблица - C++
Подскажите, пожалуйста, как сделать хэш-таблицу в которой у каждого элемента есть шесть полей.(например Имя фамилия возраст...). Что бы...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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