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

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

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

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

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

C++ Хеш таблица с функцией (метод цепочек)
C++ Хэш таблица
Хэш - таблица методом цепочек C++

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,426
16.05.2012, 17:20     Хэш-таблица. Метод цепочек. C++ #11
Цитата Сообщение от 77Bender77 Посмотреть сообщение
пробовал изменить стандартную библиотеку algorithm.сс, вставляя подсчет в функцию std::find, но получалось еще кривее(
есть идеи по этому поводу?
std::find_if
Yandex
Объявления
16.05.2012, 17:20     Хэш-таблица. Метод цепочек. C++
Ответ Создать тему
Опции темы

Текущее время: 15:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru