Пример поиска с использованием хэш-таблиц
Пример 1. Хэширование методом деления с обработкой коллизий методом цепочек.
Задано множество ключей 
, состоящее из 
элементов:
Требуется найти в множестве элементы с ключами 
, 
и 
.
Составим хэш-таблицу размерностью 
. Для этого найдем индексы исходных элементов в таблице по формуле 
Заполним хэш-таблицу согласно рассчитанным индексам. Здесь при каждом обращении к полю таблицы создается (при первичном обращении) или дополняется связанный список.
| i | Адрес списка |
|
| ||||||||
| 0 |
|
| |||||||||
| 1 |
| 52 | 69 |
| |||||||
| 2 |
| 19 |
| ||||||||
| 3 |
| 20 |
| ||||||||
| 4 |
| 55 |
| ||||||||
| 5 |
| 5 |
| ||||||||
| 6 |
|
|
| ||||||||
| 7 |
| 24 | 75 |
| |||||||
| 8 |
| 42 |
| ||||||||
| 9 |
| 9 | 43 |
| |||||||
| 10 |
| 27 | 44 |
| |||||||
| 11 |
| 62 |
| ||||||||
| 12 |
| 46 |
| ||||||||
| 13 |
|
|
| ||||||||
| 14 |
|
|
| ||||||||
| 15 |
|
|
| ||||||||
| 16 |
|
|
| ||||||||
|
|
|
Для поиска элемента с ключом 
рассчитаем соответствующее ему значение хэш-функции
Обращаясь к ячейке строки 12 хэш-таблицы переходим по хранящемуся в ней адресу связанного списка и находим в нем искомое значение ключа . Элемент найден.
Для поиска элемента с ключом 
рассчитаем соответствующее ему значение хэш-функции
Обращаясь к ячейке строки 14 хэш-таблицы обнаруживаем пустое поле, следовательно элемента с ключом 
нет в исходном массиве.
Для поиска элемента с ключом 
рассчитаем соответствующее ему значение хэш-функции
Обращаясь к ячейке строки 7 хэш-таблицы переходим по хранящемуся в ней адресу связанного списка. Сравниваем значения всех ключей списка с ключом . Элемент не найден.
Обращаясь к ячейке строки 14 хэш-таблицы обнаруживаем пустое поле, следовательно элемента с ключом нет в исходном массиве.
Пример 2. Хэширование методом умножения с обработкой коллизий методом линейного опробывания.
Задано множество ключей , состоящее из элементов:
Требуется найти в множестве элементы с ключами 
, 
и 
.
Составим хэш-таблицу размерностью . Для этого найдем индексы исходных элементов в таблице по формуле 
. Примем 
.
|
|
|
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
L AQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBl c10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxz Ly5yZWxzUEsBAi0AFAAGAAgAAAAhAIuAWCsnAgAAWQQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9l Mm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhALYr5wDhAAAACwEAAA8AAAAAAAAAAAAAAAAAgQQAAGRy cy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAACPBQAAAAA= " adj="139906" strokecolor="#4f81bd [3204]" strokeweight="2pt"> Заполним хэш-таблицу согласно рассчитанным индексам. Заполнение будем производить в порядке вычисления индексов i.
| i | Ключ k | |
| 0 | 42 | |
| 1 | 5 55 | |
| 2 | 55 | |
| 3 | ||
| 4 | 44 52 | |
| 5 | 52 | |
| 6 | 20 | |
| 7 | 62 | |
| 8 | 46 75 | |
| 9 | 9 | |
| 10 | 75 | |
| 11 | 43 | |
| 12 | 27 | |
| 13 | 19 69 | |
| 14 | 24 | |
| 15 | 69 | |
| 16 |
Первая возникшая при заполнении хэш-таблицы коллизия соответствет 
. Линейное опробывание подразумевает просмотр следующих ячеек таблицы до обнаружения первой свободной. Это строка 5 таблицы. Следовательно, туда будет занесено значение элемента с ключом 
.
ГЛАВА 6. СИСТЕМЫ СЧИСЛЕНИЯ
Система счисления – способ записи чисел цифрами и (или) символами из некоторого конечного алфавита. Любая система счисления, должна обеспечивать:
· возможность представления множества чисел (целых и/или вещественных);
· единственность представления каждого числа;
|
|
|
· возможность арифметического оперирования числами.
Набор цифр, букв и символов, используемых для представления числа, называется алфавитом системы счисления. Количество символов, используемых для записи числа, называется базисом или основанием.
Системы счисления делятся на позиционные, непозиционные и смешанные.
Непозиционной называется система, для которой значение цифры не зависит от его положения в числе. Система также может накладывать ограничения на положение цифр в числе (например, расположение в порядке убывания). К непозиционным относится римская система счисления.
Позиционная – система счисления, для которой значение цифры зависит от его положения в числе (двоичная, десятичная и т.д.). Пусть 
– основание системы счисления, тогда каждое целое конечное число в -й системе счисления может быть представлено в виде
Здесь 
– коэффициент, принимающий значение от 0 до 
( 
); степень 
является весовым коэффициентом разряда ( 
– разрядность числа).
Сокращенно такое число записывается в общепринятой форме
.
Например, для десятичной системы счисления число двести девять можно записать в виде
.
Удобство позиционных систем счисления заключается в возможности представления больших чисел с использованием относительно небольшого числа знаков, а также простота и легкость выполнения над ними арифметических действий. Именно поэтому позиционные системы счисления широко используются в современном мире.
|
|
|
Для смешанной системы счисления характерным является различный набор допустимых символов для каждого разряда. Основанием системы является возрастающая последовательность 
, а само число представляется в виде линейной последовательности
Следует отметить, что если для всей последовательности оснований разрядов (то есть для всех разрядов) будет справедливо соотношение 
, то смешанная система счисления будет являться -й системой.
Примером смешанной системы счисления являются представление времени в виде часов, минут и секунд, а также денежные знаки. Если рассматривать российские денежные знаки, то существует 13 разновидностей купюр и монет: 1, 5, 10 и 50 копеек; 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. Для того, чтобы записать какую-либо сумму в рублях, потребуется указать сколько денежных знаков каждого типа необходимо использовать. Тогда сумму 1468 рублей 57 копеек можно представить как число 104111111012, что соответствует набору купюр и монет, представленных в таблице 6.1.
Таблица 6.1.
Набор купюр и монет для суммы 1468 рублей 57 копеек
| Монета / купюра, руб. | Количество |
| 5000 | 0 |
| 1000 | 1 |
| 500 | 0 |
| 100 | 4 |
| 50 | 1 |
| 10 | 1 |
| 5 | 1 |
| 2 | 1 |
| 1 | 1 |
| 0,5 | 1 |
| 0,1 | 0 |
| 0,05 | 1 |
| 0,01 | 2 |
Системы счисления, в которых в каждом разряде набор допустимых символов один и тот же называются однородные.
Дата добавления: 2020-01-07; просмотров: 188; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!