Чому хеш-структури даних ідеально підходять для часу O(n)

1. Швидкий пошук:

• Хеш-структури та хеш-мапи забезпечують середню часову складність O(1) для вставок, видалень та пошуків. Це важливо для досягнення загальної продуктивності O(n) в задачах, де часто потрібен пошук.

1. Основні властивості:

• Хеш-набір корисний для зберігання унікальних елементів та швидкої перевірки їх наявності.
• Хеш-мапа дозволяє асоціювати значення з ключем, що дає змогу виконувати додаткові операції чи зберігати дані.

1. Зменшення надмірності:

• Зберігаючи лише необхідні дані (наприклад, унікальні елементи або підрахунки), хеш-структури допомагають оптимізувати операції.

Загальні варіанти використання та як застосовувати хеш-структури:

1. Пошук дублікатів у масиві

• Задача: Визначити, чи є у масиві дублікати.
• Підхід: Використати хеш-набір для відслідковування елементів.

def containsDuplicate(nums):  
 seen = set()  
 for num in nums:  
 if num in seen:  
 return True  
 seen.add(num)  
 return False

2. Пошук найдовшої послідовності чисел

• Задача: Знайти найдовшу послідовність підрядних цілих чисел у масиві.
• Підхід: Використати хеш-набір для зберігання елементів і почати рахувати лише з найменших елементів послідовностей.

def longestConsecutive(nums):  
 num_set = set(nums)  
 longest = 0  
 for num in num_set:  
 if num - 1 not in num_set: # Початок послідовності  
 length = 1  
 while num + length in num_set:  
 length += 1  
 longest = max(longest, length)  
 return longest

3. Підмасив з заданою сумою

• Задача: Знайти, чи є підмасив з певною сумою.
• Підхід: Використати хеш-мапу для зберігання префіксних сум та їх індексів.

def subarraySum(nums, k):  
 prefix_sum = 0  
 count = 0  
 prefix_map = {0: 1} # Базовий випадок для підмасиву, що починається з індексу 0  
 for num in nums:  
 prefix_sum += num  
 if prefix_sum - k in prefix_map:  
 count += prefix_map[prefix_sum - k]  
 prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1  
 return count

4. Пошук першого унікального елемента

• Задача: Знайти перший не повторюваний елемент у масиві.
• Підхід: Використати хеш-мапу для зберігання підрахунків, а потім ще раз пройти масив, щоб знайти перший унікальний елемент.

def firstUnique(nums):  
 count = {}  
 for num in nums:  
 count[num] = count.get(num, 0) + 1  
 for num in nums:  
 if count[num] == 1:  
 return num  
 return -1

Коли використовувати хеш-структури, а коли інші структури даних:

Як ефективно використовувати хеш-структури:

1. Ініціалізація:

• Для унікальних значень: hash_set = set().
• Для пар "ключ-значення": hash_map = {}.

1. Типові операції:

• Перевірити наявність елемента: x in hash_set.
• Додати елемент: hash_set.add(x).
• Отримати значення: value = hash_map.get(key, default).

1. Уникати колізій:

• Переконайтеся, що елементи можна хешувати (наприклад, числа, рядки). Уникайте кастомних об'єктів без визначеного методу __hash__.

1. Врахування пам'яті:

• Хеш-структури вимагають додаткової пам'яті пропорційно до розміру вхідних даних, тому вони можуть бути неідеальними для дуже великих наборів даних, якщо пам'ять обмежена.

Основні висновки:

• Хеш-набори найкраще підходять, коли потрібно перевіряти наявність елементів або забезпечувати унікальність.
• Хеш-мапи ідеальні для зберігання додаткових даних про елементи (наприклад, частоти, індекси тощо).
• Хеш-структури ефективні в сценаріях, що вимагають частих та швидких пошуків або оновлень.
• Завжди аналізуйте обмеження задачі (наприклад, впорядкований вихід), щоб визначити найбільш підходящу структуру.

Дайте знати, якщо вам потрібні приклади для конкретних типів задач!

Перекладено з: Why Hash-Based Data Structures Are Ideal for O(n) Time