Теоретический Вопрос о поиске

[diliana]

Привет

Теоретический Вопрос

Сколько сравнений требуется для поиска ключа 37 в 10-элементной хеш-таблице вида 70, 51, 22, 13, 94, 25, 0, 37, 0, 89, построенной с помощью простейшей хеш-функции?

1. одно
2. восемь
3. три
4. 10

Я думаю, что ответ№ 2. Это правильно?

[Sazary]

Вроде, восемь. Но если идти от конца, то три. Как-то неоднозначно получается. Хотя в хеш-таблицах, насколько я знаю, поиск от начала.

[diliana]

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

Вроде, восемь. Но если идти от конца, то три. Как-то неоднозначно получается. Хотя в хеш-таблицах, насколько я знаю, поиск от начала.

а я вот как думаю
эти ключи надо разместить в массиве из 10 ячеек с помощью хеш-функции

для этого делим ключи нацело на 10
остаток - индекс в массиве
получилась такая хеш-таблица
___________________________
1_2_3__4__5__6__7__8__9__10
0_0_70_51_22_13_94_25_37_89


ищем 37 - 37 делим на 10, берем остаток 7, заходим в ячейку 7, но там 94, значит начинаем идти с начала и сравниваем

итого 8 сравнений. пока не доберемся до 37

вроде как-то так.... Это правильно?

[Sazary]

Не о том подумал
Мало я знаю о хеш-таблицах... Вроде, все логично.
Но если в качестве элементов таблицы использовать списки, то, по идее, мы найдем нужное значение за 1 сравнение, т.к. 37 будет в ячейке 7.
Разве нет?

То есть таблица будет представлять из себя что-то вроде этого:

0 1   2   3   4    5   7    9
0 51 22 13 94 25 37  89
0
70

И еще вот добавлю:

ищем 37 - 37 делим на 10, берем остаток 7, заходим в ячейку 7, но там 94, значит начинаем идти с начала и сравниваем

почему сначала? Мы ведь знаем, что 37 будет после 94. Поэтому можно идти от 7-й ячейки.
Тогда уже получится 3 сравнения.. Хм..

[diliana]

Мало я знаю о хеш-таблицах... Вроде, все логично.

Я тоже

Но если в качестве элементов таблицы использовать списки, то, по идее, мы найдем нужное значение за 1 сравнение, т.к. 37 будет в ячейке 7.
Разве нет?

нет, речь только о массиве

хеш-таблицей называется массив заполненный элементами в порядке определяемом хеш-функцией

То есть таблица будет представлять из себя что-то вроде этого:

Код:

0 1   2   3   4    5   7    9
0 51 22 13 94 25 37  89
0
70

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

[Sazary]

Я не изобретал Это уже придумано до меня ) И называется "внешнее хеширование", или "метод цепочек"
http://wwwcdl.bmstu.ru/iu7/stage8.htm

Если речь конкретно о массиве, то да, число вариантов сокращается до 2-х. Т.к. я по-прежнему считаю, что можно идти сразу от 7-й ячейки, а не от начала.

[diliana]

Я не изобретал Это уже придумано до меня ) И называется "внешнее хеширование", или "метод цепочек"
http://wwwcdl.bmstu.ru/iu7/stage8.htm

да есть такое, вот только что в лекции прочитала

Если речь конкретно о массиве, то да, число вариантов сокращается до 2-х. Т.к. я по-прежнему считаю, что можно идти сразу от 7-й ячейки, а не от начала.

Но все же Sazary давайте придем к какому-то выводу

Так как варианта ответа «2 сравнения» нет, то остается или вариат «1 сравнение» или «3 сравнение»

Если принять во внимание открытое хеширование+гадание на филосовском камне,то значит побеждает вариант «1 сравнение»
Это правильно?

[Sazary]

Так как варианта ответа «2 сравнения» нет, то остается или вариат «1 сравнение» или «3 сравнение»

Эм..Почему "2 сравнения"?
Проверяем 7-ю ячейку - там 94. Это раз.
Проверяем 8-ю - там 25. Это два.
Проверяем 9-ю - там 37. То, что надо. Итого - 3 сравнения.

Я лично больше склоняюсь именно к варианту 3 (если не брать во внимание открытое хеширование).

А вообще, ведь тут от реализации зависит. Можно сделать и так, чтобы поиск шел от начала (тогда будет 8 сравнений). Но это как-то неэффективно. Ведь мы знаем, что не спроста в 7-й ячейке число, которое дает при делении на 10 в остатке 4. То есть мы знаем, что 37 будет правее 94.

[diliana]

Эм..Почему "2 сравнения"?

Проверяем 7-ю ячейку - там 94. Это раз.

Проверяем 8-ю - там 25. Это два.

Проверяем 9-ю - там 37. То, что надо. Итого - 3 сравнения.

Я лично больше склоняюсь именно к варианту 3 (если не брать во внимание открытое хеширование).

А вообще, ведь тут от реализации зависит. Можно сделать и так, чтобы поиск шел от начала (тогда будет 8 сравнений). Но это как-то неэффективно. Ведь мы знаем, что не спроста в 7-й ячейке число, которое дает при делении на 10 в остатке 4. То есть мы знаем, что 37 будет правее 94.

Полностью с вами согласна! Все очень логично!
Также еще раз общалась с философским камнем, он тоже это подтвердил!

Sazary большое спасибо за внимание!!!

[Sazary]

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

Также еще раз общалась с философским камнем, он тоже это подтвердил!

Какой разговорчивый камешек

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