10. Выбор хеш-функции

Обратимся к вопросу, как выбрать хорошую хеш-функцию. Ясно, что она должна создавать как можно меньше коллизий при хешировании, т.е. она должна равномерно распределять ключи на имеющиеся индексы в массиве. Наиболее известная хеш-функция (которую мы использовали в вышеизложенных примерах) использует метод деления, при котором некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения хеш-функции. Она обозначается h(key)=mod(key, m). Предположим, что m равно 1000 и что все ключи оканчиваются на 3 одинаковые цифры (например, последние три цифры номера изделия означают номер завода-изготовителя). Тогда остаток от деления на 1000 для всех ключей будет одинаков, т.е. возникнут коллизии при хешировании для всех записей, кроме первой. Ясно, что при таком наборе ключей допуска должна использоваться другая хеш-функция [3].

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

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

Например, предположим, что внутреннее представление некоторого ключа в виде последовательности разрядов имеет вид 010111001010110 и для индекса отводится 5 разрядов. Над тремя последовательностями разрядов 01011, 10010 и 10110 выполняется операция сложения, что дает 01111 или двоичное представление числа 15.

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

Если ключи не являются числами, то они должны быть преобразованы в целые числа перед применением описанных выше хеш-функций. Для этого имеется несколько способов. Например, для строки символов в качестве двоичного числа может интерпретироваться внутреннее двоичное представление кода каждого символа. Недостатком этого является то, что для большинства ЭВМ двоичное представление букв и цифр очень похоже друг на друга. Если ключи состоят только их одних букв, то индекс каждой буквы в алфавите может использоваться для создания некоторого целого числа. Так, первая буква алфавита (А) представится цифрами 01, а 14-я буква (N) представляется цифрами 14. Ключ “Hello” представляется целым числом 0805121215. Когда существует некоторое целое представление строки символов, то для сведения его к приемлемому размеру может быть использован метод свертки или середины квадрата.

5. Объектно-ориентированное программирование

   1. Введение в объектно-ориентированное программирование

Объектно-ориентированное программирование - это новый подход к программированию [4]. В ходе эволюции вычислительной техники и соответствующих операционных сред разрабатывались каждый раз более мощные методы программирования, чем предыдущие. Не останавливаясь на самых ранних методах программирования, сразу перейдем к анализу методов программирования, использующих языки высокого уровня. Язык программирования, легко понимаемый в коротких программах, становился плохо читаемым и неуправляемым, когда дело касалось больших программ. Избавление от неструктурированных программ пришло после изобретения в 1960 году языков структурного программирования. К ним относятся языки Алгол, Паскаль, и Си. Структурное программирование подразумевает точно обозначенные управляющие структуры, программные блоки, отсутствие или, по крайней мере, минимальное использование операторов GOTO, автономные подпрограммы, в которых поддерживается рекурсия и локальные переменные.

Сутью структурного программирования является возможность разбиения программы на составляющие ее элементы. Используя структурное программирование, средний программист может создавать и поддерживать программы свыше 50000 строк длиной. Но и это оказалось недостаточным на современном этапе. Чтобы писать более сложные программы, необходим был новый подход к программированию. В итоге были разработаны принципы объектно-ориентированного программирования (ООП). ООП аккумулирует лучшие идеи, воплощенные в структурном программировании и сочетает их с мощными новыми концепциями, которые позволяют оптимально организовывать программы. ООО позволяет разложить проблему на связанные между собой задачи. Каждая проблема становится самостоятельным объектом, содержащим свои собственные коды и данные. В этом случае вся процедура в целом упрощается, и программист получает возможность оперировать с гораздо большими по объему программами. Все языки ООП, включая С++, основаны на трех основополагающих концепциях, называемых инкапсуляцией, полиморфизмом и наследованием. Рассмотрим эти концепции.