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

Ключ в хэш-таблице - C++

Восстановить пароль Регистрация
 
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
19.01.2013, 18:29     Ключ в хэш-таблице #1
Здравствуйте !
Помогите решить две задачи:
1. Поиск ключа в хэш-таблице с цепочками
2. Вставка ключа в хэш-таблицу с цепочками
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2013, 18:29     Ключ в хэш-таблице
Посмотрите здесь:

C++ Хэш таблица
Хэш функции C++
C++ хэш-функция
C++ Хэш-функция
Хэш-таблица C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.01.2013, 18:42     Ключ в хэш-таблице #2
1. Поиск ключа в хеш-таблице с цепочками.
1.1. Вычисляем хеш ключа, находим соответствующую ячейку. Для открытого хеширования ячейка это указатель на (односвязный) список пар "ключ — значение". Ячеек в массиве столько, сколько значений выдаёт хеш-функция.
1.2. Проходим по списку в поисках элемента с совпадающим ключом.
1.3. Нашли — элемент есть. Прошли весь список и не нашли — такого ключа в хеше нет.

2. Вставка ключа в хеш-таблицу с цепочками.
2.1. Проверяем наличие ключа в таблице как в пункте 1.
2.2. Если ключа нет, то приписываем новый элемент в начало списка соответствующей ячейки. Если ключ есть, то варианты: 1) ругаемся; 2) записываем в элемент новое значение.
Igor3D
793 / 410 / 33
Регистрация: 01.10.2012
Сообщений: 2,071
19.01.2013, 19:07     Ключ в хэш-таблице #3
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
1.2. Проходим по списку в поисках элемента с совпадающим ключом.
Совпадающим значением ключа (оператор ==), хеш-значение не уникально (напр остаток от деления)

Вставка: спрыгнули на ячейку. Теперь варианты

a) ячейка пуста - записали в нее новое значение

б) не пуста и хеш-значение совпадает с данным - берем свободную ячейку из списка свободных. Если список пуст - увеличиваем размер хеша. Пишем в ячейку (хотя она и соответствует др ключу) и линкуем ее в хвост

в) не пуста и хеш-значение не совпадает. Переносим текущую ячейку в свободную (подобно "б") и заполняем освободившуюся
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
19.01.2013, 22:37  [ТС]     Ключ в хэш-таблице #4
А можно код к этому на С/C++ , заранее спасибо)
Igor3D
793 / 410 / 33
Регистрация: 01.10.2012
Сообщений: 2,071
20.01.2013, 11:04     Ключ в хэш-таблице #5
Цитата Сообщение от Saltillo Посмотреть сообщение
А можно код к этому на С/C++ , заранее спасибо)
Ну весь код - там много, а вот классы набросаю

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Key, class Val>
struct Cell {
 Cell * mNext. * mPrev; // каждая ячейка в двусвязном списке
 unsigned int mHash;      // хеш-значение
 bool mEmpty;               // флаг ячейка пуста
 Key mKey;                    // ключ
 Val mVal;                      // значение
};
 
template <class Key, class Val>
struct HashTable {
 ... // методы
 size_t mCount;
 Cell<Key, Val> * mCell;   // здесь лучше C массив (а не контейнер std)
 Cell<Key, Val> * mFreeList;   // список свободных ячеек
};
Для класса/типа Key должна быть определена ф-ция
C++
1
2
3
unsigned int Hash( const Key & key);
// напр
unsigned int Hash( const int & key) { return key; }
Конструктор HashTable выделяет какое-то число свободных ячеек (напр 16) и связывает их в mFreeList. Далее как обсуждалось выше
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
20.01.2013, 12:44  [ТС]     Ключ в хэш-таблице #6
Igor3D ~OhMyGodSoLong~ спасибо)
Yandex
Объявления
20.01.2013, 12:44     Ключ в хэш-таблице
Ответ Создать тему
Опции темы

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