Что быстрее поиск в массиве или в словаре?

Поиск в массиве vs поиск в словаре: анализ скорости

В iOS-разработке (и computer science в целом) поиск в словаре (Dictionary) значительно быстрее поиска в массиве (Array) в подавляющем большинстве сценариев. Это фундаментальное различие обусловлено структурой данных и алгоритмами, которые они используют.

Временная сложность (Big O Notation)

Ключевое отличие — временная сложность операций:

Поиск в массиве (Array)

• Линейный поиск (без дополнительных условий): O(n)
  В худшем случае необходимо проверить каждый элемент.

  let array = [10, 20, 30, 40, 50]
  let target = 30
  var found = false
  for element in array { // Может пройти все n элементов
      if element == target {
          found = true
          break
      }
  }
  

• Бинарный поиск (если массив отсортирован): O(log n)
  Но требует сортировки (O(n log n)) и поддержания порядка при вставках.

Поиск в словаре (Dictionary)

• Поиск по ключу (основной сценарий): O(1) в среднем случае
  Даже для огромных коллекций время доступа практически постоянно.

  var dictionary = ["A": 1, "B": 2, "C": 3]
  let value = dictionary["B"] // Доступ по хэшу ключа "B"
  

Почему словарь быстрее: механизм хэширования

Словарь использует хэш-таблицу:

1. Ключ хэшируется в уникальный (или почти уникальный) индекс
2. Прямой доступ к "корзине" (bucket) по этому индексу
3. Разрешение коллизий через цепочки или открытую адресацию

// Под капотом (упрощённо)
struct Dictionary<Key: Hashable, Value> {
    private var buckets: [Int: [(Key, Value)]]
    
    func getValue(for key: Key) -> Value? {
        let hash = key.hashValue // O(1) для Hashable типов
        let index = abs(hash) % buckets.count
        return buckets[index]?.first { $0.0 == key }?.1
    }
}

Практические измерения в iOS

Рассмотрим тест на 100000 элементов:

// Тест скорости поиска
let size = 100_000
let targetKey = "ключ_50000"

// Массив пар (ключ, значение)
let array = (0..<size).map { ("ключ_\($0)", $0) }

// Словарь с теми же данными
let dictionary = Dictionary(uniqueKeysWithValues: array)

// Поиск в массиве (линейный)
let startArray = Date()
let arrayResult = array.first { $0.0 == targetKey }?.1
let timeArray = Date().timeIntervalSince(startArray)

// Поиск в словаре
let startDict = Date()
let dictResult = dictionary[targetKey]
let timeDict = Date().timeIntervalSince(startDict)

print("Массив: \(timeArray) сек")   // ~0.01-0.1 сек
print("Словарь: \(timeDict) сек")   // ~0.000001-0.00001 сек

Когда что использовать?

Используйте словарь, когда:

• Частый поиск по уникальным ключам
• Не важен порядок элементов
• Нужна константная скорость доступа
• Примеры: кэши, индексы, маппинг идентификаторов

Используйте массив, когда:

• Важен порядок элементов
• Частые итерации по всем элементам
• Индексы являются "ключами" (доступ по индексу O(1))
• Данные уже отсортированы и нужен бинарный поиск
• Память критична (словарь использует больше памяти)

Нюансы производительности в Swift

1. Качество хэш-функции: Для кастомных типов важно правильно реализовать Hashable

   struct User: Hashable {
       let id: UUID
       let email: String
       
       // Хорошая хэш-функция уменьшает коллизии
       func hash(into hasher: inout Hasher) {
           hasher.combine(id) // UUID уже хороший хэш
       }
   }
   

2. Загрузка хэш-таблицы: При большом количестве коллизий деградация до O(n)

3. Размер словаря: Рехеширование при увеличении размера вызывает кратковременные затраты

Заключение

Словарь обеспечивает константное время доступа O(1) против линейного O(n) у массива для поиска по значению. Разница становится экспоненциально значимее с ростом данных. Однако выбор структуры данных должен учитывать:

• Паттерны доступа (только поиск или также итерации)
• Требования к памяти
• Необходимость порядка
• Частоту обновлений (вставка в словарь O(1), в отсортированный массив O(n))

Для поиска по ключу всегда предпочитайте Dictionary, если только у вас нет специфических требований к упорядочиванию или памяти. В iOS-разработке это знание критически важно для оптимизации производительности, особенно при работе с большими наборами данных в UITableView, кэшировании изображений или обработке JSON-ответов от API.