Хеш-таблица

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

На пальцах :) Допустим вам надо очень быстро определять по номеру телефона фамилию человека. Для этого у вас есть блокнотик на 100 страниц, и вы туда постоянно дописываете новых людей с их тел. номерами. Вначале вы пытались записывать номера так, чтобы первые 2 цифры номера совпадали с номером страницы, но быстро обломились, т.к. выяснилось что в вашем городе все номера начинаются с цифр 58-, 76- или 77. Т.о. вам пришлось бы впихнуть все номера на 3 страницы блокнота, а остальные остались бы пустыми. Поэтому, вы придумали способ похитрее. Вы суммируете номер по две цифры, и получаете номер страницы, на которую вам нужно записать этот номер. Например номер 76-35-32 суммируем 76+35+32=143 (сотню отбрасываем т.к. в блокноте всего 100 стр) получаем 43. Итак, этот номер и фамилию человека записываем на 43 страницу. Теперь номера распределились по блокноту более равномерно, поэтому нет (ну почти нет) ни переполненных страниц ни пустых. Когда вам нужно быстро найти фамилию по номеру, вы делаете тоже самое складываете по две цифры и получаете страницу где этот номер записан. Вот и получилась закрытая хеш таблица размером 100 с хеш ф-ей = (x+y+z)%100, где x,y,z - номер телефона разбитый на 3 числа по 2 цифры.

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home