Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
nexen
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

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

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

АВЛ-дерево
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти...

Коллизия хеш и контейнеры
Здравствуйте! Продолжая изучать STL узнал, что различные контейнеры обладают...

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

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

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

17
gray_fox
What a waste!
1552 / 1257 / 165
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 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 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
01.12.2013, 21:19  [ТС] #3
gray_fox, вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).
Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут? Понятно, что могут ячейки хранить сразу несколько элементов, но конкретизации не будет ведь, т.е., до самого элемента достучаться по хэшу не удастся
0
MrCold
859 / 757 / 174
Регистрация: 11.01.2012
Сообщений: 1,942
01.12.2013, 21:21 #4
красно-черное и авл деревья
.... и hashmap это массив связных списков
1
gray_fox
What a waste!
1552 / 1257 / 165
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 3
01.12.2013, 21:25 #5
Цитата Сообщение от nexen Посмотреть сообщение
вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).
А это не одно и тоже?)
Цитата Сообщение от nexen Посмотреть сообщение
Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут?
Время доступа к элементу будет больше.

Добавлено через 2 минуты
Ну к примеру если хэш-таблица у нас устроена так (ИМХО самое простое): массив связных списков, хэш элемента - это индекс в этом массиве. Если у всех элементов один результат хэш-функции, то, вуаля, у нас уже связный список)
1
nexen
187 / 180 / 25
Регистрация: 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!
1552 / 1257 / 165
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 3
01.12.2013, 21:56 #7
nexen, ищем "ячёку" по хэшу, дальше по обычному сравнению.
1
nexen
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
01.12.2013, 22:05  [ТС] #8
gray_fox, но тогда почему авл и КЧ-деревья имеют log(N) сложность на все операции в худшем случае? Ведь в оном может так случиться, что все N, внезапно, попадут под коллизию, а значит что при связных списках, что при циклической адресации придется перебирать все N элементов обычным сравнением.. ?
0
gray_fox
What a waste!
1552 / 1257 / 165
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 3
01.12.2013, 22:15 #9
nexen, в сбалансированных деревьях нет никаких коллизий; гарантии сложности операций имеются за счёт поддержания структуры, высоты дерева в определённых пределах...
1
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
01.12.2013, 22:16 #10
nexen, что то я не понимаю. Если у вас ключами в АВЛ дереве являются строки, то их можно и посимвольно сравнивать. Если долго (а долго будет только в случае если префиксы большой длины у строк равны) - пожалуйста, пишите хеши. Только потом решайте вопрос коллизии списками. А хеши то разные бывают, откуда может получиться, что тяжело будет подобрать 2 строки с одинаковым хешом, или легко.
1
nexen
187 / 180 / 25
Регистрация: 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
~ Эврика! ~
1245 / 994 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
02.12.2013, 10:41 #12
Цитата Сообщение от nexen Посмотреть сообщение
gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

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

Цитата Сообщение от nexen Посмотреть сообщение
И, если это так, то остался последний вопрос, который меня мучает в любых хеш-таблицах.. Чтобы адресация была за О(1), нужен обычный массив и индекс. Индексом может служить хэш. Однако, хэш, обычно, принимает довоьно широкие пределы, допустим, 8 знаков (да и частенько он выражается не только в числовой форме 10ой записи, а в 16ой), тогда как же выделять массив для этих нужд?
Размер массива обычно берут степенью двойки, а хеш-функцию выбирают (или обрабатывают) так, что она выдавала хеши с конкретным количеством битов. Если свободное место в хеш-таблице начинает заканчиваться, то можно увеличить её в два раза, взять новую расширенную функцию, пересчитать хеши для элементов и перераспределить их по новой таблице.
1
nexen
187 / 180 / 25
Регистрация: 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
~ Эврика! ~
1245 / 994 / 74
Регистрация: 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
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 11:47 #15
Цитата Сообщение от nexen Посмотреть сообщение
они, на самом деле, хэш-таблицами делаются
откуда вы это взяли?
АВЛ и КЧД строятся на связных структурах (не списках) - узлах, имеющих некоторую полезную информацию и несколько связей с потомками (и может быть и с предком). ни связные списки, ни хэш-таблицы здесь не нужны. поиск за log(N).

в хэш-таблицах поиск осуществляется за амортизированную константу, причем обычно используются не таблицы на основе цепочек переполнения, за которые вы уцепились, а на основе, например, динамических хеш-таблиц с открытой адресацией.
1
gray_fox
What a waste!
1552 / 1257 / 165
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 3
02.12.2013, 13:07 #16
Цитата Сообщение от nexen Посмотреть сообщение
gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?
Ну можно и так конечно коллизии разрешать, но это всё равно будет хэш-таблица, деревья тут не причём.
1
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
02.12.2013, 14:14 #17
я понятия не имею, как реализована stl, но ваша дискуссия на пустом месте развернулась. существует не один способ разрешения коллизий. я уверен, что в хэш-таблицах они исключены.
я основываюсь на (кажущейся вполне очевидной) гипотезе, что можно подобрать два таких модуля, чтобы двойное хэширование не допускало коллизий в том смысле, что мы хэшим всегда натуральные числа (коды символов).
0
ya_noob
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 14:27 #18
Цитата Сообщение от salam Посмотреть сообщение
я уверен, что в хэш-таблицах они исключены.
очень в этом сомневаюсь. по вашему для каждого элемента есть своя ячейка в хэш-таблице, которую никто кроме него не может занять. но если в таблицу положить несколько одинаковых элементов, то в некоторый момент кому-то не достанется его ячейки и он займет чужую. всё, коллизии обеспечены.
1
02.12.2013, 14:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 14:27
Привет! Вот еще темы с решениями:

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

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

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка...

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


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

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

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