Количество различных последовательностей вставки значений Key в хеш-таблицу - PullRequest
Новая
       25

Количество различных последовательностей вставки значений Key в хеш-таблицу

0 голосов
/ 16 января 2019

Хеш-таблица длиной 10 использует открытую адресацию с хеш-функцией h (k) = k mod 10 и линейное зондирование. После вставки 8 значений в пустую хеш-таблицу таблица выглядит так: 

0 |
1 | 91
2 | 2
3 | 13
4 | 24
5 | 12
6 | 62
7 | 77
8 | 82
9 |

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

ОТВЕТ - 128.

Я знаю для 91,2,13,24,77 его 5! = 120, но я не могу понять, какие еще 8 комбинаций?

1 Ответ

0 голосов
/ 19 января 2019

Дан неправильный ответ. На самом деле это был насмешливый тест, а ответ, предоставленный источником, неверен.Реальный ответ - 168.

Это можно сделать двумя способами -

1) 91,2,13,24,12,62,77,82 - здесь, если вы видите и фильтруетеout out 

  _,91,_,2_,13,_,24,_,12,_,62,_,82

Во всех доступных пробелах, которые мы могли заполнить 77, это всегда приведет к 7-му слоту, так что общее количество путей 77 может прийти - любое из 7 мест, т.е. 7.

Сейчас91,2,13,24 могут прийти в любом порядке и могут быть расположены как указано выше, так что всего - 4!и для каждого из 4!аранжировки 77 могут прийти в любом из 7 мест, поэтому ответ - 4! * 7 = 168.

2) Второй способ - есть только 3 возможных последовательности

i) 91,213,24,77,12,62,82 

 Here 91,2,13,24,77 can come in any order, They will get there respective 
 slots so total 5! ways.

ii) 91,2,13,24,12,77,62,82 

  Here 91,2,13,24 can come in any order and we have fixed 77 after 12 so total 
  4! ways.

iii) 91, 2,13,24,12,62,77,82 

   same here with 4! ways 91,2,13,and 24 can come and 77 is fixed after 62.

, итого 5! +4! +4! = 168.

...