Для чего нужен hash-set

Структура данных hash-set (и вообще set) — это такая редкая структура, что присутствует не во всех стандартных библиотеках. В .NET Framework, например, она появилась только с версии 3.5. Однако в некоторых случаях hash-set может быть весьма полезен.

В этой статье я покажу, когда имеет смысл применять hash-set и чем за это придется заплатить.



Во-первых, что такое set. Это такая коллекция, элементы которой неупорядоченны и уникальны (т.е. присутствуют в коллекции не более одного раза). Set поддерживает базовые операции:

• Добавить элемент.
• Удалить элемент.
• Проверить, существует ли элемент.
• Перебрать все элементы.

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

Теперь рассмотрим пример. Допустим нам нужно реализовать группировку большого числа элементов по равенству списка тэгов, причем для тэгов определен ignore list — то есть, тэги, которые не должны участвовать в сравнении. Тэги, в данном случае, — это недлинные строки (в основном, слова). Предположим так же, что ignore list содержит порядка 100 тэгов.

На Ruby алгоритм выглядит следующим образом:

def group_elements(elements, ignore_list)
  groups = []

  for element in elements
    assigned = false

    for group in groups
      #Если элемент принадлежит группе, он добавляется и возвращается true;
      #в противном случае, возвращается false.
      if group.accept(element, ignore_list) 
        assigned = true
        break
      end
    end

    #Если элемент не принадлежит ни одной группе,
    #создаем новую группу для этого элемента.
    if !assigned
      groups << Group.new(element)
    end
  end

  return groups
end

Вот как реализован метод Group::accept():

class Group
  ...
  def accept(element, ignore_list)
    for my_element in @elements
      if my_element.match(element)
        @elements << element
        return true
      end
    end

    return false
  end
  ...
end

И наконец, метод Element::match():

class Element
  ...
  def match(element, ignore_list)
    #Фильтруем списки тэгов.
    my_tags_filtered = @tags.select { |tag| !ignore_list.include?(tag) }
    its_tags_filtered = element.tags.select { |tag| !ignore_list.include?(tag) }

    #Находим пересечение множеств.
    intersection = my_tags_filtered & its_tags_filtered

    #Множества совпадают если их пересечение не пустое и 
    #его размер равен размеру большего из множеств.
    return intersection.length > 0 && 
           intersection.length == [my_tags_filtered.length, its_tags_filtered.length].max
  end
  ...
end

Здесь продемонстрирована реализация в лоб, где и сами списки тэгов, и ignore list — это обычные динамические массивы. То есть, операция ignore_list.include? имеет линейную сложность. Кроме того, вспомним, что тэги — это строки длиной в среднем 5-10 символов, а сравнение строк само по себе имеет линейную сложность. Учитывая, что группировка имеет сложность O(n²), оптимизация базовых операций сравнения может дать существенный прирост в производительности.

Сделать реализацию более оптимальной помогает hash-set. Если реализовать ignore list при помощи него, мы получим два серьезных преимущества. Во-первых, мы избавимся от линейного поиска по списку, заменяя его поиском hash-ключа; во-вторых, мы избавимся от сравнения строк. Есть правда один нюанс — в Ruby нет структуры данных hash-set. Однако это не проблема, потому что hash-set может заменить обычная hash-таблица, в которой элементы используются как ключи (в качестве значений можно использовать любой тип как можно меньшего размера). Этот странный прием применяется, например, в NHibernate, и хорошо работает если нет лучшего.

Я сравнивал две реализации вышеописанного алгоритма на Ruby с количеством элементов порядка 2000-3000, размером тэга 2-15 символов UTF-8 и количеством тэгов на элемент, в среднем, 5. Замена массива hash-set-ом дала прирост в производительности приблизительно в 10 раз.

В целом, hash-set-ы позволяют более оптимально реализовать операции над множествами — пересечение, объединение и вычитание. Однако не стоит забывать об их избыточности. Hash-set-ы резервируют значительно больше памяти, чем нужно для хранения их элементов, поэтому их имеет смысл использовать только для множеств среднего размера (100-10000 элементов). Фактически, вы тратите память, чтобы получить более быстрые вычисления. Для больших множеств следует использовать деревья.