Пятница, 24.11.2017, 10:22
Приветствую Вас Гость | RSS
Главная | Лекции | Регистрация | Вход
Меню сайта
Форма входа
Логин:
Пароль:
Категории раздела
Лекция [24]
Мини-чат
100
Поиск
Наш опрос
Оцените мой сайт
Всего ответов: 2
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0
    Программирование Perl
    Главная » Статьи » Лекция » Лекция

    Лекция 6.1: Хэши

    Ассоциации и хэши

    В программировании ассоциативные связи являются одним из основных видов связей между информационными объектами наряду с наследованием (связями типа "предок-потомок") и агрегацией (связями типа "часть-целое"). Ассоциации позволяют устанавливать необходимые логические связи между сущностями по избранному программистом критерию. Ассоциативная связьподобна стрелке на схеме, направленной от одного объекта к другому. Часто ассоциации используются для нахождения по заданной величине соответствующего значения. В этом случае две части ассоциативной связи соответственно называют поисковым ключом (key) и значением (value), ассоциированным с этим ключом. На этом принципе основана классическаяструктура данных, называемая словарем (dictionary).

     

    В языке Perl для выражения ассоциаций имеются ассоциативные массивы или хэш-таблицы, которые для краткости принято называть хэшами. Хэш (hash) представляет из себя набор ассоциативных связейКлючом хэша может быть любая скалярная величина: строка, ссылка, целое или дробное число, автоматически преобразуемое в строку. Причем значения всех ключей в хэше уникальны, поскольку внутренняя организация хэша не допускает ключей с одинаковыми значениями. Ассоциированное сключом значение может быть любой скалярной величиной. Хэши сочетают в себе ряд привлекательных качеств: гибкость, мощь, быстроту и удобство работы. Поэтому они весьма часто используются при программировании на Perl самых различных задач. С помощью хэшей можно моделировать понятия из математики, информатики, лингвистики и других областей знаний: множества, словари, фреймысемантические сети, программные объекты и простые базы данных. Размер хэша в Perl ограничен только доступной программе памятью, поэтому хэши позволяют эффективно обрабатывать большие объемы данных, в которых требуется выполнять быстрый поиск. Примечательно то, что в других языках ассоциативные массивы реализованы в виде коллекций объектов в библиотечных модулях, а в языке Perl хэши встроены в ядро языка, что обеспечивает их максимально эффективную работу.

     

    Хэши - переменные и литералы

    В программе хэш представляется в виде переменной, имеющей тип хэша, которая записывается с разыменовывающим префиксом% перед именем. Этот префикс обозначает, что это переменная-хэш, в которой хранится набор ассоциативных связей, иначе говоря, пар "ключ - значение":

     
    %hash # переменная-хэш
     

    Непосредственные величины ключей и значений хэша могут быть представлены в виде списочного литерала, который записывается как список в круглых скобках, состоящий из элементов хэша. Каждый элемент в литерале состоит из двух частей: поискового ключа и связанного с ним значения, разделенных символами =>, например:

     
    ('версия' => 5.8, 'язык' => 'Perl') # ключ - строка
    (3.14 => 'число Пи') # ключ - дробь
    (1 => 'one', 2 => 'two', 3 => 'three') # ключ - целое
    ($key1 => $value1, $key2 => $value2) # ключ в переменной
     

    Операция => эквивалентна запятой, за исключением того, что она создает строковый контекст, так что ее левый операндавтоматически преобразуется к строке. Именно поэтому числа в этом примере записаны без кавычек. Литеральные списки, содержащие ассоциативные пары, обычно применяются для присваивания хэшам начальных значений:

     
    %quarter1 = (1 => 'январь', 2 => 'февраль', 3 => 'март');
    %dns = ($site => $ip, 'www.perl.com' => '208.201.239.36');
    %empty = (); # пустой список удаляет все элементы хэша
     

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

     
    %num2word = (10 => 'десять', 5 => 'пять', 10 => 'ten');
    # в %num2word останется только (5 => 'пять', 10 => 'ten')
     

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

     

    Начальные значения элементов хэша могут браться из любого списка, при этом значения нечетных элементов списка становятся в хэше ключами, а четных - ассоциированными с этими ключами значениями. Так что два следующих присваивания эквивалентны:

     
    %dictionary = ('я' => 'I', 'он' => 'he', 'она' => 'she');
    %dictionary = ('я', 'I', 'он', 'he', 'она', 'she');
     

    И конечно, для заполнения хэша элементами вместо списочного литерала можно использовать массив, содержащий пары "ключ -значение":

     
    %dictionary = @list_of_key_value_pairs; # массив пар
     

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

     

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

     
    @key_value_list = %hash; # список ключей и значений
     

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

    Элементы хэшей

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

     
    $hash{$key} = $value; # добавление значения в хэш по ключу
    $value = $hash{$key}; # извлечение значения из хэша по ключу
     

    Начинающие осваивать Perl могут думать про хэши, что это такие странные массивы ("ассоциативные"), у которых индексы могут быть не только числами, но и строками, и поэтому записываются эти необычные индексы не в квадратных скобках, а в фигурных (по-английски "curly braces" - "кучерявые скобки"). Вот примеры использования элементов хэша:

     
    $month = 'January';
    $days_in_month{$month}= 31; # со строкой связано число
    $ru{$month}= 'январь'; # со строкой связана строка
    print "В $ru{$month} $days_in_month{'January'} день";
     

    В некоторых программах можно встретить при записи элементов хэша строковые ключи, не заключенные в кавычки: это допускается, если ключ - одно слово, записанное по правилам написания идентификаторов, так называемое "голое слово" ("bareword").

     

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

     
    $variable # скалярная переменная
    @variable # переменная-массив
    %variable # переменная-хэш
     

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

     
    while (my $line = <>) { # считать строку из входного потока
     chomp($line); # удалить из строки символ '\n'
     @words = split(' ', $line); # разбить строку на слова
     foreach my $word (@words) { # для каждого найденного слова
     $hash{$word}++; # увеличить счетчик
     }
    }
    # теперь в %hash содержатся счетчики слов
     

    Позднее, в лекции, посвященной регулярным выражениям, будет сказано, как выделять из строки слова не только по пробелам.

     

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

     

    Категория: Лекция | Добавил: mazay (13.05.2014)
    Просмотров: 120 | Рейтинг: 0.0/0
    Всего комментариев: 0
    Добавлять комментарии могут только зарегистрированные пользователи.
    [ Регистрация | Вход ]
    Создать бесплатный сайт с uCozCopyright MyCorp © 2017