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

@nexen · Регистрация: 27.01.2012

Author24 — интернет-сервис помощи студентам

До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида:

C++

1	printf("%d\n", myAssociativeMassive_String_and_Integer["oh..I need second elements"]);

реализованы при помощи сбалансированных двоичных деревьев, но потом прочитал, что оно, всё же, реализовано при помощи хэш-массивов. Тогда этому значения не придал, но сейчас подумал, а как так? Хэш, хоть и редко, но все же имеет плохую особенность - коллизию. Так что же будет с таким деревом при коллизии? Или я что-то напутал? Даже если напутал, то, помнится, есть структура hashmap или как-то так в stl. Как же тогда она работает?

@gray_fox · 01.12.2013, 21:15

Сообщение от nexen

До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида:
Код C++
1
printf("%d\n", myAssociativeMassive_String_and_Integer["oh..I need second elements"]);
реализованы при помощи сбалансированных двоичных деревьев, но потом прочитал, что оно, всё же, реализовано при помощи хэш-массивов.

Сбалансированное двоичное дерево реализовано посредством хэш-таблицы

Явно что-то не то прочитали...

Добавлено через 2 минуты

Сообщение от nexen

помнится, есть структура hashmap или как-то так в stl

unordered_map есть, hashmap нестандартная реализация.

@nexen · 01.12.2013, 21:19 **[ТС]**

gray_fox, вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).
Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут? Понятно, что могут ячейки хранить сразу несколько элементов, но конкретизации не будет ведь, т.е., до самого элемента достучаться по хэшу не удастся

@MrCold · 01.12.2013, 21:21

красно-черное и авл деревья
.... и hashmap это массив связных списков

@gray_fox · 01.12.2013, 21:25

Сообщение от nexen

вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал).

А это не одно и тоже?)

Сообщение от nexen

Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут?

Время доступа к элементу будет больше.

Добавлено через 2 минуты
Ну к примеру если хэш-таблица у нас устроена так (ИМХО самое простое): массив связных списков, хэш элемента - это индекс в этом массиве. Если у всех элементов один результат хэш-функции, то, вуаля, у нас уже связный список)

@nexen · 01.12.2013, 21:48 **[ТС]**

gray_fox, а, и правда, одно и то же.
Ну это понятно (насчет связных списков), но дело вот в чем. Предположим, есть строчки str1 и str2, и они были добавлены в таблицу. Их хэш равен 123. Допустим, есть метод find, принимающий строку или хэш сразу (не важно):

C++

1	myHashTable.find("str2");

Оп-па, был найден элемент, точнее указатель, на связный список, первый элемент которого str1, ведь он был первее добавлен! И как теперь узнать, который из них (в связном списке) наш элемент? Ну допустим, если поиск идет по строке, можно теперь использовать strcmp, но если поиск идет по хэшу?..

@gray_fox · 01.12.2013, 21:56

nexen, ищем "ячёку" по хэшу, дальше по обычному сравнению.

@nexen · 01.12.2013, 22:05 **[ТС]**

gray_fox, но тогда почему авл и КЧ-деревья имеют log(N) сложность на все операции в худшем случае? Ведь в оном может так случиться, что все N, внезапно, попадут под коллизию, а значит что при связных списках, что при циклической адресации придется перебирать все N элементов обычным сравнением.. ?

@gray_fox · 01.12.2013, 22:15

nexen, в сбалансированных деревьях нет никаких коллизий; гарантии сложности операций имеются за счёт поддержания структуры, высоты дерева в определённых пределах...

@Dani · 01.12.2013, 22:16

nexen, что то я не понимаю. Если у вас ключами в АВЛ дереве являются строки, то их можно и посимвольно сравнивать. Если долго (а долго будет только в случае если префиксы большой длины у строк равны) - пожалуйста, пишите хеши. Только потом решайте вопрос коллизии списками. А хеши то разные бывают, откуда может получиться, что тяжело будет подобрать 2 строки с одинаковым хешом, или легко.

@nexen · 02.12.2013, 09:38 **[ТС]**

gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

И, если это так, то остался последний вопрос, который меня мучает в любых хеш-таблицах.. Чтобы адресация была за О(1), нужен обычный массив и индекс. Индексом может служить хэш. Однако, хэш, обычно, принимает довоьно широкие пределы, допустим, 8 знаков (да и частенько он выражается не только в числовой форме 10ой записи, а в 16ой), тогда как же выделять массив для этих нужд? Пример:

C++

HTable ht; //допустим, изначальный размер 0
string s = "str1"; //допустим, hash(s) == 21389142
ht.insert("str1"); //размер ht-массива стал 21389142 ? О_о
string foundedString = ht.find("str1"); //иначе мы не можем за О(1) обратится, ведь ищем именно по индексу 21389142

Или что я опять не понимаю?

(А ну и что делают с хэшами 0x? Или их не применяют для такого, только 10ые?)

@OhMyGodSoLong · 02.12.2013, 10:41

Сообщение от nexen

gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

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

Сообщение от nexen

И, если это так, то остался последний вопрос, который меня мучает в любых хеш-таблицах.. Чтобы адресация была за О(1), нужен обычный массив и индекс. Индексом может служить хэш. Однако, хэш, обычно, принимает довоьно широкие пределы, допустим, 8 знаков (да и частенько он выражается не только в числовой форме 10ой записи, а в 16ой), тогда как же выделять массив для этих нужд?

Размер массива обычно берут степенью двойки, а хеш-функцию выбирают (или обрабатывают) так, что она выдавала хеши с конкретным количеством битов. Если свободное место в хеш-таблице начинает заканчиваться, то можно увеличить её в два раза, взять новую расширенную функцию, пересчитать хеши для элементов и перераспределить их по новой таблице.

@nexen · 02.12.2013, 10:51 **[ТС]**

OhMyGodSoLong,

Сообщение от OhMyGodSoLong

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

тогда опять не понимаю, откуда О(log(N)).. При худшем случае со связными списками O(N) и не иначе.

А читал я, что авл и КЧ делаются деревьями здесь: http://algolist.manual.ru/ds/rbtree.php
Поэтому и разрывает мне шаблон то, что они, на самом деле, хэш-таблицами делаются. Вот никак и не могу связать эти два факта (чем же они делаются)..

@OhMyGodSoLong · 02.12.2013, 11:46

Сообщение от nexen

А читал я, что авл и КЧ делаются деревьями здесь: http://algolist.manual.ru/ds/rbtree.php
Поэтому и разрывает мне шаблон то, что они, на самом деле, хэш-таблицами делаются. Вот никак и не могу связать эти два факта (чем же они делаются)..

Господи... АВЛ-дерево. Красно-чёрное дерево. Это деревья. Там нет хешей. Это бинарные деревья. В них поиск, вставка, удаление делаются за примерно O(log N) операций.

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

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

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

Ассоциативный массив — обобщённое название *map-структур.

@ya_noob · 02.12.2013, 11:47

Сообщение от nexen

они, на самом деле, хэш-таблицами делаются

откуда вы это взяли?
АВЛ и КЧД строятся на связных структурах (не списках) - узлах, имеющих некоторую полезную информацию и несколько связей с потомками (и может быть и с предком). ни связные списки, ни хэш-таблицы здесь не нужны. поиск за log(N).

в хэш-таблицах поиск осуществляется за амортизированную константу, причем обычно используются не таблицы на основе цепочек переполнения, за которые вы уцепились, а на основе, например, динамических хеш-таблиц с открытой адресацией.

@gray_fox · 02.12.2013, 13:07

Сообщение от nexen

gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево?

Ну можно и так конечно коллизии разрешать, но это всё равно будет хэш-таблица, деревья тут не причём.

@salam · 02.12.2013, 14:14

я понятия не имею, как реализована stl, но ваша дискуссия на пустом месте развернулась. существует не один способ разрешения коллизий. я уверен, что в хэш-таблицах они исключены.
я основываюсь на (кажущейся вполне очевидной) гипотезе, что можно подобрать два таких модуля, чтобы двойное хэширование не допускало коллизий в том смысле, что мы хэшим всегда натуральные числа (коды символов).

@ya_noob · 02.12.2013, 14:27

Сообщение от salam

я уверен, что в хэш-таблицах они исключены.

очень в этом сомневаюсь. по вашему для каждого элемента есть своя ячейка в хэш-таблице, которую никто кроме него не может занять. но если в таблицу положить несколько одинаковых элементов, то в некоторый момент кому-то не достанется его ячейки и он займет чужую. всё, коллизии обеспечены.

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	02.12.2013, 14:14	17
	я понятия не имею, как реализована stl, но ваша дискуссия на пустом месте развернулась. существует не один способ разрешения коллизий. я уверен, что в хэш-таблицах они исключены. я основываюсь на (кажущейся вполне очевидной) гипотезе, что можно подобрать два таких модуля, чтобы двойное хэширование не допускало коллизий в том смысле, что мы хэшим всегда натуральные числа (коды символов). 0

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	02.12.2013, 14:27	18
	Сообщение от salam я уверен, что в хэш-таблицах они исключены. очень в этом сомневаюсь. по вашему для каждого элемента есть своя ячейка в хэш-таблице, которую никто кроме него не может занять. но если в таблицу положить несколько одинаковых элементов, то в некоторый момент кому-то не достанется его ячейки и он займет чужую. всё, коллизии обеспечены. 1

@gray_fox What a waste! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	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 873 / 771 / 173 Регистрация: 11.01.2012 Сообщений: 1,942
	01.12.2013, 21:21	4
	красно-черное и авл деревья .... и hashmap это массив связных списков 1

@gray_fox What a waste! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	01.12.2013, 21:25	5
	Сообщение от nexen вопрос на миллион, а чем хэш-таблица отличается от хэш-массива? (вики читал). А это не одно и тоже?) Сообщение от nexen Да и, если все-таки хэш-таблица, то опять-таки, коллизии возможны и что будет, если они произойдут? Время доступа к элементу будет больше. Добавлено через 2 минуты Ну к примеру если хэш-таблица у нас устроена так (ИМХО самое простое): массив связных списков, хэш элемента - это индекс в этом массиве. Если у всех элементов один результат хэш-функции, то, вуаля, у нас уже связный список) 1

@gray_fox What a waste! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	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! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	01.12.2013, 22:15	9
	nexen, в сбалансированных деревьях нет никаких коллизий; гарантии сложности операций имеются за счёт поддержания структуры, высоты дерева в определённых пределах... 1

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	01.12.2013, 22:16	10
	nexen, что то я не понимаю. Если у вас ключами в АВЛ дереве являются строки, то их можно и посимвольно сравнивать. Если долго (а долго будет только в случае если префиксы большой длины у строк равны) - пожалуйста, пишите хеши. Только потом решайте вопрос коллизии списками. А хеши то разные бывают, откуда может получиться, что тяжело будет подобрать 2 строки с одинаковым хешом, или легко. 1

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 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 ~ Эврика! ~ 1256 / 1005 / 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 _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	02.12.2013, 11:47	15
	Сообщение от nexen они, на самом деле, хэш-таблицами делаются откуда вы это взяли? АВЛ и КЧД строятся на связных структурах (не списках) - узлах, имеющих некоторую полезную информацию и несколько связей с потомками (и может быть и с предком). ни связные списки, ни хэш-таблицы здесь не нужны. поиск за log(N). в хэш-таблицах поиск осуществляется за амортизированную константу, причем обычно используются не таблицы на основе цепочек переполнения, за которые вы уцепились, а на основе, например, динамических хеш-таблиц с открытой адресацией. 1

@gray_fox What a waste! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	02.12.2013, 13:07	16
	Сообщение от nexen gray_fox, кажись, наконец-то, дошло. Сначала ищем по хешу, затем попадаем на нужную ячейку и там лежит не просто связный список, как обсуждалось ранее, а сбалансированное двоичное дерево? Ну можно и так конечно коллизии разрешать, но это всё равно будет хэш-таблица, деревья тут не причём. 1