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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

АВЛ дерево и коллизия хэша - C++

01.12.2013, 20:30. Просмотров 1333. Ответов 17
Метки нет (Все метки)

До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида:
C++
1
printf("%d\n", myAssociativeMassive_String_and_Integer["oh..I need second elements"]);
реализованы при помощи сбалансированных двоичных деревьев, но потом прочитал, что оно, всё же, реализовано при помощи хэш-массивов. Тогда этому значения не придал, но сейчас подумал, а как так? Хэш, хоть и редко, но все же имеет плохую особенность - коллизию. Так что же будет с таким деревом при коллизии? Или я что-то напутал? Даже если напутал, то, помнится, есть структура hashmap или как-то так в stl. Как же тогда она работает?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 20:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос АВЛ дерево и коллизия хэша (C++):

АВЛ-дерево - C++
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти в нем узел, относительно которого будет максимальная...

АВЛ дерево - C++
Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев и попробовала забить этот код, но к...

Высота авл дерева - как считать? - C++
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр - высота лев. А как посчитать высоту авл дерева с...

Комменты к реализации Красно-черного и АВЛ дерева - C++
Люди добрые помогите разобрать и по возможности написать комментарии к этим 2м кодам .. Это коды Реализации Красно-черного и АВЛ дереве и...

Преобразование хэша в целое число и работа с хэшем (SHA 256) - C++
Возникла проблемма при написании курсовой...Пишу программу Электронная подпись Эль Гамаля.Столкнулся с такой проблемой ,что ,когда я делаю...

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? - C++
Доброго времени суток. Нужна помощь. В АВЛ-дереве надо найти самую короткую ветвь и удалить ее. Я могу удалить только узел по ключу (ну...

17
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
01.12.2013, 21:15 #2
Цитата Сообщение от nexen Посмотреть сообщение
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида:
Код C++
1
printf("%d\n", myAssociativeMassive_String_and_Integer["oh..I need second elements"]);
реализованы при помощи сбалансированных двоичных деревьев, но потом прочитал, что оно, всё же, реализовано при помощи хэш-массивов.
Сбалансированное двоичное дерево реализовано посредством хэш-таблицы
Явно что-то не то прочитали...

Добавлено через 2 минуты
Цитата Сообщение от nexen Посмотреть сообщение
помнится, есть структура hashmap или как-то так в stl
unordered_map есть, hashmap нестандартная реализация.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
01.12.2013, 21:19  [ТС] #3
gray_fox, вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).
Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут? Понятно, что могут ячейки хранить сразу несколько элементов, но конкретизации не будет ведь, т.е., до самого элемента достучаться по хэшу не удастся
0
MrCold
855 / 753 / 71
Регистрация: 11.01.2012
Сообщений: 1,942
01.12.2013, 21:21 #4
красно-черное и авл деревья
.... и hashmap это массив связных списков
1
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
01.12.2013, 21:25 #5
Цитата Сообщение от nexen Посмотреть сообщение
вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).
А это не одно и тоже?)
Цитата Сообщение от nexen Посмотреть сообщение
Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут?
Время доступа к элементу будет больше.

Добавлено через 2 минуты
Ну к примеру если хэш-таблица у нас устроена так (ИМХО самое простое): массив связных списков, хэш элемента - это индекс в этом массиве. Если у всех элементов один результат хэш-функции, то, вуаля, у нас уже связный список)
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
01.12.2013, 21:48  [ТС] #6
gray_fox, а, и правда, одно и то же.
Ну это понятно (насчет связных списков), но дело вот в чем. Предположим, есть строчки str1 и str2, и они были добавлены в таблицу. Их хэш равен 123. Допустим, есть метод find, принимающий строку или хэш сразу (не важно):
C++
1
myHashTable.find("str2");
Оп-па, был найден элемент, точнее указатель, на связный список, первый элемент которого str1, ведь он был первее добавлен! И как теперь узнать, который из них (в связном списке) наш элемент? Ну допустим, если поиск идет по строке, можно теперь использовать strcmp, но если поиск идет по хэшу?..
0
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
01.12.2013, 21:56 #7
nexen, ищем "ячёку" по хэшу, дальше по обычному сравнению.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
01.12.2013, 22:05  [ТС] #8
gray_fox, но тогда почему авл и КЧ-деревья имеют log(N) сложность на все операции в худшем случае? Ведь в оном может так случиться, что все N, внезапно, попадут под коллизию, а значит что при связных списках, что при циклической адресации придется перебирать все N элементов обычным сравнением.. ?
0
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
01.12.2013, 22:15 #9
nexen, в сбалансированных деревьях нет никаких коллизий; гарантии сложности операций имеются за счёт поддержания структуры, высоты дерева в определённых пределах...
1
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,284
Записей в блоге: 2
Завершенные тесты: 1
01.12.2013, 22:16 #10
nexen, что то я не понимаю. Если у вас ключами в АВЛ дереве являются строки, то их можно и посимвольно сравнивать. Если долго (а долго будет только в случае если префиксы большой длины у строк равны) - пожалуйста, пишите хеши. Только потом решайте вопрос коллизии списками. А хеши то разные бывают, откуда может получиться, что тяжело будет подобрать 2 строки с одинаковым хешом, или легко.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
02.12.2013, 09:38  [ТС] #11
gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

И, если это так, то остался последний вопрос, который меня мучает в любых хеш-таблицах.. Чтобы адресация была за О(1), нужен обычный массив и индекс. Индексом может служить хэш. Однако, хэш, обычно, принимает довоьно широкие пределы, допустим, 8 знаков (да и частенько он выражается не только в числовой форме 10ой записи, а в 16ой), тогда как же выделять массив для этих нужд? Пример:
C++
1
2
3
4
HTable ht; //допустим, изначальный размер 0
string s = "str1"; //допустим, hash(s) == 21389142
ht.insert("str1"); //размер ht-массива стал 21389142 ? О_о
string foundedString = ht.find("str1"); //иначе мы не можем за О(1) обратится, ведь ищем именно по индексу 21389142
Или что я опять не понимаю?
(А ну и что делают с хэшами 0x? Или их не применяют для такого, только 10ые?)
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.12.2013, 10:41 #12
Цитата Сообщение от nexen Посмотреть сообщение
gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

Бинарное дерево — это бинарное дерево. Оно не имеет никакого отношения к хешу. Выкинтье эту чушь из головы, сожгите то, где вы это прочитали, и передайте это тому, кто вам посоветовал этот источник.

Цитата Сообщение от nexen Посмотреть сообщение
И, если это так, то остался последний вопрос, который меня мучает в любых хеш-таблицах.. Чтобы адресация была за О(1), нужен обычный массив и индекс. Индексом может служить хэш. Однако, хэш, обычно, принимает довоьно широкие пределы, допустим, 8 знаков (да и частенько он выражается не только в числовой форме 10ой записи, а в 16ой), тогда как же выделять массив для этих нужд?
Размер массива обычно берут степенью двойки, а хеш-функцию выбирают (или обрабатывают) так, что она выдавала хеши с конкретным количеством битов. Если свободное место в хеш-таблице начинает заканчиваться, то можно увеличить её в два раза, взять новую расширенную функцию, пересчитать хеши для элементов и перераспределить их по новой таблице.
1
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
02.12.2013, 10:51  [ТС] #13
OhMyGodSoLong,
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
Бинарное дерево — это бинарное дерево. Оно не имеет никакого отношения к хешу. Выкинтье эту чушь из головы, сожгите то, где вы это прочитали, и передайте это тому, кто вам посоветовал этот источник.
тогда опять не понимаю, откуда О(log(N)).. При худшем случае со связными списками O(N) и не иначе.

А читал я, что авл и КЧ делаются деревьями здесь: http://algolist.manual.ru/ds/rbtree.php
Поэтому и разрывает мне шаблон то, что они, на самом деле, хэш-таблицами делаются. Вот никак и не могу связать эти два факта (чем же они делаются)..
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.12.2013, 11:46 #14
Цитата Сообщение от nexen Посмотреть сообщение
А читал я, что авл и КЧ делаются деревьями здесь: http://algolist.manual.ru/ds/rbtree.php
Поэтому и разрывает мне шаблон то, что они, на самом деле, хэш-таблицами делаются. Вот никак и не могу связать эти два факта (чем же они делаются)..
Господи... АВЛ-дерево. Красно-чёрное дерево. Это деревья. Там нет хешей. Это бинарные деревья. В них поиск, вставка, удаление делаются за примерно O(log N) операций.

У хеш-таблиц операции занимают амортизированно O(1) и в худшем случае O(N). То есть большую часть времени при хороших условиях там O(1), иногда тормозит.

но... Отдельной строкой:

Деревья — не хеши. АВЛ-дерево не хеш. std::map на деревьях. std::unordered_map на хешах.

Ассоциативный массив — обобщённое название *map-структур.
1
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 11:47 #15
Цитата Сообщение от nexen Посмотреть сообщение
они, на самом деле, хэш-таблицами делаются
откуда вы это взяли?
АВЛ и КЧД строятся на связных структурах (не списках) - узлах, имеющих некоторую полезную информацию и несколько связей с потомками (и может быть и с предком). ни связные списки, ни хэш-таблицы здесь не нужны. поиск за log(N).

в хэш-таблицах поиск осуществляется за амортизированную константу, причем обычно используются не таблицы на основе цепочек переполнения, за которые вы уцепились, а на основе, например, динамических хеш-таблиц с открытой адресацией.
1
02.12.2013, 11:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 11:47
Привет! Вот еще темы с ответами:

Не возникает ли коллизия имен, если использовать два пространства имен, и в каждом из них будут одноименные? - C++
Вот например namespace nms1 { int gh; } namespace nms2 { int gh;

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить - C++
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка на статью http://habrahabr.ru/post/150732/ Не могли бы Вы...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.


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

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

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