Хэш таблица и сет

Ранее мы поговорили поговорили о такой структуре данных как массив. Настало время поговорить про остальные базовые структуры данных

Хэш

Хэш таблица (еще она называется Hash map в других ЯП) - структура данных, хранящая в себе сразу 2 элмента - ключ и значение. Ключ - уникальный, значение - нет.

# создание пустой хэш таблицы
hash = Hash.new
# Упрощенная запись
hash = {}
# Способ создания хэш таблицы с заранее созданным содержанием
hash = Hash['key_1' => 'value_1', 'key_2' => 'value_2', 'key_1' => 'value_3']
# Упрощенная запись через кавычки
hash = {'key_1' => 'value_1', 'key_2' => 'value_2', 'key_1' => 'value_3'}
# Начиная с ruby 1.9 появилась возможность записывать ключ - значение через двоеточие. 
# Данный вариант записи стоит считать наиболее предпочтительный, вместо Hash[...] или использования => 
# так как при записи key: value, key приводится к символу, о котором мы поговорим в следующем уроке
hash = {'key_1': 'value_1', 'key_2': 'value_2', 'key_1': 'value_3'}
# Обрати внимание, что key_1 содержится только один раз, не смотря на то, что мы его объявляли дважды
# И значение содержится от последней объявляенной пары с таким же ключом
puts hash # = {'key_1' => 'value_3', 'key_2' => 'value_2'}

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

# создание пустой хэш таблицы
dictionary = Hash.new
# Упрощенная запись
dictionary = {
    'be': 'быть',
    'have': 'иметь',
    'mandarin': 'мандарин',
    'tangerine': 'манадрин'
}

# как можем заметить словарь включает в себя несколько одинаковых значений
puts dictionary

# Получение значения по его ключу
# Принцип схож с массивом, только если там мы оперируем индексом, то здесь у нас произвольный ключ
puts dictionary['be'] # = быть

# Так как такого ключа нет в нашем хэше, то значение будет nil
puts dictionary['you'] # = nil

Теперь стоит обсудить как изменять хэш таблицу:

muttable_hash = {'key_1': 'value_1'}

puts muttable_hash.length # = 1

# принцип похож на изменение значения массива по индексу
# только если там у нас массив изменял размер до последнего индекса
# то тут поведение уже нормальное и ожидаемое 
muttable_hash['key_2'] = 'value_2'

puts muttable_hash.length # = 2

# изменение значения по ключу ничем не отличается от добавления
# так как ключи уникальны, то значение просто перезапишется  
muttable_hash['key_1'] = 'value_2'

puts muttable_hash.length # = 2

# метод удаления достаточно предсказуеми
muttable_hash.delete('key_2')

Давайте посмотрим на особенность итерации хэша в цикле:

example = { '1':1, '2':1, '3':1}

#попробуем написать в обычном для нас формате
for x in example
  # только вместо puts будем использовать p для более подробной информации
  p x # = [:"1", 1], потом [:"2", 1], потом [:"3", 1] 
  # если все еще не поняли, то давайте сразу посмотрим на тип у x
  puts x.class # = Array. Да, при обходе в цикле хэша, на каждую иетрацию мы получаем доступ к ключу и значению, которые представлены в виде массива
  # где 1 элемент - ключ
  puts "key: #{x[0]}"
  # а второй элемент это наше значение
  puts "value: #{x[1]}"
end

# данный цикл делает тоже самое, что и цикл выше
# только мы заменили одну переменную, которая была массивом
# на 2 переменные, первая - ключ, вторая - значение   
for key, value in example
    puts "key: #{key}"
    puts "value: #{value}"
end

Сет

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

# set является частью языка ruby, но недоступен в глобальной области видимости в отличии от Hash или Array, поэтому его необходимо 'требовать' перед тем как использовать
require 'set'

str_set = Set.new

# метод .add(element) добавляет элемент в set
str_set.add('Hello')
str_set.add('World')
str_set.add('Hello')

# Хоть мы добавили 3 элемента, но так как один из них повторяется, то в сете у нас 2 элемента
puts str_set.length # = 2

Сравнение Set vs Array

Хоть базовые алгоритмы мы изучим в дальнейшем, но сейчас важно понимать в чем приемущество Set по сравнению с Array

Рассмотрим такой метод как .include? который присутствует и у Array и у Set

# Метод добавления элементов позволяет нам избавиться от дублирования кода
def add_elements(structure)
  for x in 1..10_000_000
    # хоть метод добавления у Array и Set отличаются
    # но обе структуры имеют метод <<, который является alias для метода push и add
    # Подробнее про такую конструкцию мы поговорим в разделе с полиморфизмом
    structure << x
  end
end

set = Set.new
arr = []

# сначала добавляем элементы в сет
# подробнее про time мы поговорим в следующих уроках
# пока не обращаем внимание, здесь он играет утилитарную роль для замера скорости
start = Time.now
add_elements(set)
finish = Time.now

# показывает время, затраченное на добавление элементов в секундах для сета
puts "Time taken to add items to Set (in seconds) - #{finish - start}"

# теперь добавим такие же элементы в массив
start = Time.now
add_elements(arr)
finish = Time.now

# показывает время, затраченное на добавление элементов в секундах для массива
puts "Time taken to add items to Array (in seconds) - #{finish - start}"

start = Time.now
# метод .include? возращает true если элемент с атким значением присутствует в структуре
set.include?(9153452)
finish = Time.now

# показывает время, затраченное на проверку на наличие в секундах для сета
puts "Time taken to check for an item in Set (in seconds) - #{finish - start}"

start = Time.now
# точно такой же смысл работы как и у сета
arr.include?(9153452)
finish = Time.now

# показывает время, затраченное на проверку на наличие в секундах для массива
puts "Time taken to check for an item in Array (in seconds) - #{finish - start}"

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

Проверили ? Да, разница впечатляющая. Все дело в особенности работы этих структур. Метод .unclude? у Array обходит все свои элементы и проверяет на соотвествие (==). Сначала 1 элемент, потом 2, потом 3 и тд. Чем больше элементов, тем дольше может работать unclude?.

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

Возможно у вас появилась мысль а зачем тогда испоьзовать массив если есть сет ? Всему свое место. Set - отлично, когда нам целенаправлено нужно использовать уникальность знчений. Если посмотреть на разницу во времени на добавление элементов, то заметим внушительный перевес по скорости у массива.

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

• У массива доступ к элементу по значению прямо зависит от размера самого массива

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

Задание key_vs_value

У Hash также имеются методы value?, который проверяет на наличие значения, и key?, который проверяет на наличие ключ.

• Перепишите пример со сравнением скорости массива и сета на сравнение скорости метода value? и key?, переписав также метод добавления элементов, где ключ и значение это одно и тоже значение для хэш таблицы

• Расскажите о выводах которые вы можете сделать касаемо этих методов, после изучения полученных результатов

Задание email_checker

Задание на умение работать сетом.

• Напишите программу, в которой будет храниться перечень адресов электронной почты. Адреса можно добавлять через консоль командой ADD и печатать весь список командой LIST.

• Программа должна проверять корректность вводимых email’ов (вспоминаем прошлый урок) и печатать сообщение об ошибке при необходимости.

Принцип работы команд

• LIST — выводит список электронных адресов.

• ADD — проверяет и, если формат адреса верный, добавляет в множество.

Примеры команд

• LIST

• ADD [e-mail]

Команды вводятся одной строкой пользователем в консоль.

Задание phone_book

Задание на умение работать с хэш таблицей.

• Напишите программу, которая будет работать как телефонная книга:

  • Если пишем новое имя, программа просит ввести номер телефона и запоминает его. Если новый номер телефона — просит ввести имя и также запоминает.

  • Если вводим существующее имя или номер телефона, программа выводит всю информацию о контакте.

  • При вводе команды LIST программа печатает в консоль список всех абонентов в алфавитном порядке с номерами.

• Определяйте имя и телефон с помощью регулярных выражений.

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