Swift Set: коли func. contains(...) => true вводить в оману й приховує зламану колекцію
Перепишіть прізвище на картці, але залиште її в старій шухляді, і наступний пошук піде не туди. Це аналогія застарілого індексу, а не буквальна модель хешування за абеткою.
Суть проблеми:
Додаємо у Swift-колекцію Set двох користувачів з ID 1 та 2. Після цього змінюємо ID першого користувача (user.id = 2), а перебір колекції показує вже [2, 2]: обидва збережені об’єкти порівнюються як рівні. Перевірка contains при цьому може повернути true, тож побіжний тест створює враження, що все працює.
Мутація компілюється, бо множина зберігає посилання на екземпляри класу. Інше посилання може змінити поле, яке визначає рівність, без жодної операції над самою колекцією. Як викрити цей збій, коли пошук начебто успішний?
Якщо простежити одне присвоєння далі, з’явиться ще одна несподіванка. Пояснення «Swift обирає один випадковий seed на процес» описує лише частину причин, через які нові множини можуть давати різні відповіді. Перевіримо це на фактичному виводі програми та реалізації пошуку. Що таке випадковий seed і як він впливає на хешування, також розберемо далі.
TL;DR
- Поки об’єкт перебуває в
Setабо є ключемDictionary, поля для==таhash(into:)мають залишатися стабільними.letдля колекції не робить незмінними екземпляри класів усередині. - Успішний
containsпісля зміни ключа не підтверджує коректності колекції. У ній уже можуть бути два елементи, рівні через==. - У дослідженій реалізації seed процесу поєднується із seed конкретної таблиці. Нові таблиці можуть давати різні результати в одному процесі; повторний пошук у тій самій незмінній таблиці — інший дослід.
- Не зберігайте
hashValueяк постійний ключ кешу чи ID у базі даних: те саме значення може отримати інший хеш після перезапуску програми. Для сутності зберігайте стабільний ID; для відбитка вмісту — відповідний стабільний алгоритм і визначене подання байтів. - Як уникнути проблем: для унікальності облікових записів використовуйте стабільний ID. Для відстеження живих екземплярів підійдуть
===таObjectIdentifier. Якщо потрібно змінити сам ключ, спершу видаліть його з усіх відповідних колекцій, а після мутації вставте знову.
Set уже порушує унікальність, хоча contains повертає true
Note
Повний код двох версій, з багом і з виправленням, наведено нижче, одразу після виводу. У ньому User — клас, а його == та hash(into:) використовують id. Множина users зберігає посилання на ці об’єкти; інша частина застосунку може тримати посилання на ті самі екземпляри.
Починаємо з ID 1 та 2. Об’єкти нерівні, тому вставка зберігає обидва. Через інше посилання змінюємо перший ID на 2. Повторної вставки, яка перевірила б унікальність, тут немає. Локальний запуск друкує:
Stored IDs: [2, 2]
Count: 2
Objects compare equal: true
Contains first: true
Contains second: true
Every stored ID is unique: falseКолекція вже зламана: у Set не повинно бути двох елементів, рівних через ==. Ми самі порушили цю вимогу, змінивши ключ після вставки. contains лише шукає рівний елемент; він не перевіряє всі збережені елементи на дублікати. Тому його true не виправдовує мутацію й не означає, що множина коректна. Помилку тут викривають два однакові ID та Count: 2.
У порівнянні нижче змінюється одна дія. Ліворуч ключ змінюється на місці. Праворуч елемент спочатку видаляється за старим ключем, змінюється й вставляється знову. Натисніть «Запустити обидва», щоб порівняти збережені ID та перевірку унікальності.
З багом
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
user.id = id
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let first = User(id: 1)
let second = User(id: 2)
var users: Set<User> = [first, second]
changeID(first, to: 2, in: &users)
let ids = users.map(\.id).sorted()
print("Stored IDs: \(ids)")
print("Count: \(users.count)")
print("Objects compare equal: \(first == second)")
print("Contains first: \(users.contains(first))")
print("Contains second: \(users.contains(second))")
let unique = users.count == Set(ids).count
print("Every stored ID is unique: \(unique)")
// ▷ Try: change the destination ID from 2 to 3 and compare membership as well as uniqueness.Виправлено
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
users.remove(user)
user.id = id
users.insert(user)
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let first = User(id: 1)
let second = User(id: 2)
var users: Set<User> = [first, second]
changeID(first, to: 2, in: &users)
let ids = users.map(\.id).sorted()
print("Stored IDs: \(ids)")
print("Count: \(users.count)")
print("Objects compare equal: \(first == second)")
print("Contains first: \(users.contains(first))")
print("Contains second: \(users.contains(second))")
let unique = users.count == Set(ids).count
print("Every stored ID is unique: \(unique)")
// ▷ Try: change the destination ID from 2 to 3 and compare membership as well as uniqueness.Що змінилося
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
+ users.remove(user)
user.id = id
+ users.insert(user)
}
Ліворуч зміна ключа на місці залишає два рівні елементи. Праворуч видалення перед мутацією й повторна вставка залишають один рівний елемент. Поля користувачів при цьому не об’єднуються.
Повторна вставка знову перевіряє рівність. Оскільки новий ID уже є в множині, виправлений приклад залишає для нього один елемент. Тут навмисно залишається один із рівних елементів; поля користувачів не об’єднуються. Якщо застосунок забороняє конфлікти ID, зміну слід відхилити. Для моделі облікового запису зазвичай простіше зробити його ID незмінним.
Що тут цікавого: у виправленому прикладі contains(first) також може бути true, навіть якщо множина залишила другий, уже наявний екземпляр. contains перевіряє рівність, а не наявність саме цього посилання. Тут кількість збережених елементів та їхні ID підтверджують, що рівний елемент лише один.
Видаляти потрібно до мутації. Видалення також виконує пошук, тому зміна ключа може завадити й цій операції. Якщо один об’єкт зберігається в кількох колекціях, його потрібно видалити за старим ключем з кожної з них. У наведеному порівнянні колекція лише одна.
Посилання залишилося на місці, ключ пошуку змінився
Опис проблеми: для цього прикладу уявімо хеш-таблицю як пронумеровані місця зберігання — комірки (buckets). Під час вставки хеш визначає початкову комірку, після чого колекція перевіряє рівність і знаходить місце для нового елемента. Пошук проходить відповідний маршрут.
Коли елемент є екземпляром класу, зберігається посилання. Присвоєння user.id = 2 змінює об’єкт, до якого воно веде. Методи вставки чи видалення множини при цьому не викликаються. Посилання залишається в комірці, обраній тоді, коли ключ дорівнював 1.
Тепер contains(user) хешує поточний ключ, 2. Пошук може початися в іншому місці й зустріти порожню комірку раніше, ніж дійде до збереженого посилання. Об’єкт не зник; змінився маршрут, яким колекція намагається його знайти.
Ярлик змінився, а папка залишилася на місці. Пошук за новим ключем може звернутися до порожньої комірки.
🔎 На що дивитися: стежте за User u. Його id змінюється, а посилання в комірці [1] залишається на місці. Потім Пошук використовує новий ключ і потрапляє до порожньої комірки [2].
Це навчальна модель на чотири комірки з вигаданими хешами (105 і 202). Вона виокремлює посилання та два маршрути пошуку; далі зіставимо її з native-реалізацією.
Тут важливі дві вимоги:
- Рівність і хешування мають бути узгоджені. Рівні значення повинні подавати в
Hasherоднакові суттєві компоненти в однаковому порядку. Це задокументована вимога Hashable. - Ключ не можна змінювати всередині колекції. Компоненти, які визначають рівність, мають залишатися стабільними, поки елемент зберігається в множині.
Реалізація User узгоджена із собою в кожен окремий момент: обидва методи читають id. Помилка виникає, коли ключ змінюється, а колекція досі індексує попередній стан. Оголошення множини через let не заморожує поля об’єктів усередині. Копіювання Set також не створює незалежних копій цих екземплярів.
Чому func. contains(…) може повернути true після зміни ключа
З одним елементом ту саму помилку складніше помітити. Перебір досі показує об’єкт, а хеш-пошук може повернути false. В іншому запуску результат може бути true.
Tip
Перевірте самі: кілька разів запустіть програму нижче кнопкою «Запустити» або через «Відкрити в онлайн-редакторі» → Run. Порівняйте Hash-based lookup із Same instance found by iteration: між запусками пошук може повертати то true, то false, хоча перебір знаходить той самий екземпляр. Обидва результати за кілька спроб не гарантовані; незмінний true теж не робить цю мутацію безпечною.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
print("Count: \(users.count)")
print("Stored IDs: \(users.map(\.id).sorted())")
print("Hash-based lookup: \(users.contains(user))")
let found = users.contains { $0 === user }
print("Same instance found by iteration: \(found)")
// ▷ Try: change id to another number; a successful lookup does not validate the mutation.В одному зафіксованому запуску програма надрукувала Count: 1, Stored IDs: [2] та Hash-based lookup: false, хоча перебір знайшов той самий екземпляр. Перебір проходить збереженими посиланнями; contains(_:) шукає за поточним ключем. Перевірка через перебір тут допомагає дослідити збій, а не виправляє некоректний індекс.
Нехай у навчальній таблиці чотири комірки. Вставка з вигаданим хешем 105 починається в комірці 105 % 4, тобто 1. Після мутації можливі, наприклад, такі хеші:
| Хеш нового ключа | Початкова комірка | Що відбувається в моделі з одним елементом |
|---|---|---|
202 |
2 |
Комірка порожня, тому пошук не знаходить елемент. |
309 |
1 |
Пошук доходить до збереженого посилання; == читає поточні ID, 2 == 2, і порівняння успішне. |
Скінченна кількість комірок не дає кожному можливому хешу окремого стартового місця. Два різні повні хеші можуть обрати ту саму комірку.
105 та 309 — різні хеші. Збігається початкова комірка, отримана після відображення значно більшого діапазону хешів у чотири позиції. Для такого пояснення не потрібно знаходити колізію двох повних хеш-значень.
Native-реалізація Swift використовує кількість комірок, що є степенем двійки, та обчислює початковий індекс як hashValue & bucketMask. Потім вона проходить зайняті комірки, порівнює елементи через == і продовжує до збігу або першої порожньої позиції. Це видно в idealBucket у HashTable.swift та find у NativeSet.swift.
Приклад із додатними числами та % 4 пояснює відображення в індекс; він не дає способу обчислити реальну комірку з user.hashValue. Множина також передає власний seed, а публічна Set.capacity не є кількістю комірок.
Коли зайнятих комірок більше, їх послідовна перевірка, або probing, створює додаткові шляхи до збігу. Тому успішний contains мало говорить про коректність мутації. У конкретному тесті пошук міг випадково пройти через потрібне посилання.
Чому нові Set в одному процесі можуть давати різні відповіді
Навіщо потрібен випадковий seed? Щоб ускладнити нападнику підбір ключів, які перевантажать застосунок. Якщо хешування передбачуване, можна заздалегідь підібрати багато різних ключів із колізіями й передати їх програмі. Замість середньої O(1) пошук або вставка може вимагати O(n) перевірок, а серія з n вставок — до O(n²) роботи. CPU зайнятий обробкою таких даних; застосунок перестає вчасно реагувати, а сервіс може не встигати обслуговувати запити. Це hash-flooding, один із способів відмови в обслуговуванні. Таку загрозу описує мотивація SE-0206.
Seed — випадкове початкове значення для хешування, яке Swift зазвичай обирає під час запуску процесу. З іншим seed той самий набір ключів може розподілятися інакше, тож підібрані для одного запуску колізії складніше повторно використати в іншому. Це захист від передбачуваних наборів колізій; самі колізії залишаються можливими. Коректна колекція перевіряє ключі через ==: колізія може сповільнити пошук, але сама по собі не змушує його повернути дані іншого ключа.
Коли це з’явилося у Swift? загальне рандомізоване хешування стандартної бібліотеки та публічний Hasher прийшли зі Swift 4.2. Це зафіксовано в release notes Apple та SE-0206. Не варто узагальнювати це як «до 4.2 seed ніде не було»: наприклад, String у Swift 4.1 на платформах поза Apple вже використовував випадково ініціалізований SipHash. Цей виняток описав Karoy Lorentey, автор нової реалізації.
Тепер перевіримо, чи одного seed процесу досить, щоб пояснити весь дослід. Створимо нові множини в одному процесі. Одне оптимізоване виконання дало таку послідовність для десяти короткоживучих таблиць:
F T T F F F F F F FT означає, що contains повернув true; F — false. Між цими спробами процес не перезапускався. У тому самому виконанні 64 таблиці, які утримувалися одночасно, дали 36 відповідей true та 28 відповідей false. Це спостережені кількості, а не гарантовані Swift імовірності.
Важливо розрізняти самі досліди:
| Що залишається живим? | Що перевіряємо? |
|---|---|
| Одна множина | Повторний пошук у тій самій таблиці й контексті хешування. |
| Нові короткоживучі множини | Пам’ять може звільнятися між спробами. |
| Нові множини, утримувані разом | Окремі таблиці без негайного повторного використання пам’яті. |
| Новий процес | Новий seed виконання й нові таблиці. |
Наступна програма запускає перші три сценарії та двічі хешує той самий рядок. Вона виконується послідовно, тож гонка даних не є частиною експерименту. Ваш вивід може відрізнятися від зафіксованої послідовності.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func shortLivedTables() -> String {
var results: [String] = []
for _ in 0..<10 {
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
results.append(users.contains(user) ? "T" : "F")
}
return results.joined(separator: " ")
}
func retainedTables() -> String {
var tables: [Set<User>] = []
var users: [User] = []
for _ in 0..<64 {
let user = User(id: 1)
tables.append([user])
users.append(user)
}
for user in users { user.id = 2 }
return zip(tables, users).map { table, user in
table.contains(user) ? "T" : "F"
}.joined(separator: " ")
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
let repeated = (0..<10).map { _ in
users.contains(user) ? "T" : "F"
}.joined(separator: " ")
print("One table: \(repeated)")
print("Short-lived tables: \(shortLivedTables())")
print("Retained tables: \(retainedTables())")
print("Same string, twice:")
print("Swift".hashValue)
print("Swift".hashValue)
// ▷ Try: run again; keep key-stability tests separate from these intentionally invalid lookups.
Тут корисна аналогія початкового налаштування: за іншої конфігурації той самий вхід може перетворитися інакше. На відміну від роторів Enigma, що просуваються, незмінна таблиця Swift не перемикає контекст хешування після кожного пошуку.
Seed виконання справді існує. Звичайний Hasher() використовує його, і повторне хешування тих самих компонентів у межах одного виконання дає однаковий результат. Native-колекції додають ще один вхід: NativeSet.hashValue(for:) передає _storage._seed під час хешування елемента.
У дослідженій ревізії коду звичайний seed таблиці спирається на адресу її об’єкта зберігання, яку поєднують із seed виконання. Копії через copy-on-write можуть зберігати попередній seed; нове сховище та зміна розміру можуть створити інший. Тому повторний пошук і повторне створення таблиць потрібно досліджувати окремо.
🔎 На що дивитися: Seed процесу спільний для цього виконання. Простежте його поєднання із Seed таблиці A та Seed таблиці B. Повторний Пошук у тій самій незмінній таблиці використовує той самий контекст; створення іншої таблиці може додати інший.
Важливий результат: нові множини можуть давати різні відповіді в одному процесі. Це не означає, що повторні запити до тієї самої незмінної таблиці випадково перемикаються між true та false.
Як перевіряли: Swift 6.4.2, 20 запусків і обмеження досліду
Локальний дослід використовував Apple Swift 6.4.2 у режимі мови Swift 6, без оптимізації та з -O. По п’ять нових процесів для кожної конфігурації зі звичайним і детермінованим хешуванням дали 20 виконань. Онлайн-сервіс може використовувати іншу версію інструментарію.
Однакові відповіді в короткоживучому циклі узгоджуються з можливістю, що алокатор повторно використовує звільнені адреси сховищ. Адреси тут не вимірювалися, тому це припущення на основі реалізації, а не трасування алокатора. Утримання 64 таблиць усуває негайне повторне використання їхньої звільненої пам’яті як пояснення цього сценарію.
Посилання на вихідний код фіксують досліджену ревізію Swift. Це не твердження, що встановлений Apple toolchain зібрано саме з неї. Деталі seed таблиці пояснюють спостережену поведінку; стабільність полів рівності та хешування залишається вимогою до моделі.
Рандомізація захищає таблицю, але не виправляє змінений ключ
Не зберігайте hashValue як постійний ключ кешу чи ідентифікатор бази даних. Для бізнесової сутності зберігайте стабільний ідентифікатор. Для відбитка вмісту оберіть відповідний стабільний алгоритм, наприклад SHA-256, і визначене подання байтів. Це різні завдання; жодне не робить безпечною зміну індексованого ключа на місці.
Причина — у початковому налаштуванні хешування: те саме значення може отримати інший hashValue після перезапуску. Між версіями стандартної бібліотеки може змінитися й сам алгоритм; досліджена реалізація використовує SipHash-1-3. Документація Hasher прямо застерігає від повторного використання хешів між виконаннями програми.
Для локальної діагностики можна запустити скомпільовану програму так:
SWIFT_DETERMINISTIC_HASHING=1 ./seed-experimentЗмінну потрібно встановити до запуску процесу. У моїх детермінованих виконаннях усі перевірки входження після мутації ключа повернули false. Це ще одне спостереження для конкретної версії інструментів, а не вимога для ваших тестів. Змінна впливає на seed; помилка мутації ключа залишається.
Визначте, що означає «той самий користувач»
Вирішіть, що Set має вважати дублікатом. Два об’єкти Account з однаковим стабільним ID зазвичай представляють один обліковий запис: множина має залишити один із них. Дві окремі сесії цього користувача можуть бути різними елементами, навіть якщо їхній accountID однаковий. Нижче виберемо правило для кожного випадку та перевіримо його кодом. Це допоможе зберігати потрібну унікальність, не прив’язуючи пошук до поля, яке ви змінюєте.
| Що має вважатися тим самим елементом? | Відповідне подання |
|---|---|
| Той самий обліковий запис, навіть завантажений в інший екземпляр | Рівність і хешування за стабільним незмінним ID облікового запису. |
| ID вибраного користувача, поки завантажені дані змінюються | Set<User.ID> із моделями, що зберігаються окремо. |
| Саме той самий живий екземпляр об’єкта | === для рівності та ObjectIdentifier(self) для хешування. |
| Значення, справжній ключ якого потрібно змінити | Видалити за старим ключем, змінити й вставити знову в кожну відповідну колекцію. |
Наступний приклад порівнює перший і третій варіанти. Змініть ім’я облікового запису: стабільний ID досі дозволяє знайти еквівалентний, заново завантажений об’єкт. Потім змініть ID облікового запису в сесії: рівність за посиланням досі розпізнає саме цю сесію, а інша сесія залишається окремим елементом.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class Account: Hashable {
let id: Int
var displayName: String
init(id: Int, displayName: String) {
self.id = id
self.displayName = displayName
}
static func == (lhs: Account, rhs: Account) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
final class Session: Hashable {
var accountID: Int
init(accountID: Int) { self.accountID = accountID }
static func == (lhs: Session, rhs: Session) -> Bool {
lhs === rhs
}
func hash(into hasher: inout Hasher) {
hasher.combine(ObjectIdentifier(self))
}
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let account = Account(id: 1, displayName: "Jim")
let accounts: Set<Account> = [account]
account.displayName = "Jim Halpert"
let reloaded = Account(id: 1, displayName: "James")
print("Reloaded account found: \(accounts.contains(reloaded))")
let session = Session(accountID: 1)
let other = Session(accountID: 1)
let sessions: Set<Session> = [session, other]
session.accountID = 2
print("Separate sessions stored: \(sessions.count)")
print("Same session found: \(sessions.contains(session))")
print("New session found: \(sessions.contains(Session(accountID: 2)))")
// ▷ Try: give the reloaded account another ID, then compare it with the separate session behavior.Для ObjectIdentifier потрібна відповідна рівність за ідентичністю екземпляра. Якщо хешувати за екземпляром, але вважати різні екземпляри рівними за ID облікового запису, узгодженість рівності та хешування порушиться. Документація ObjectIdentifier також обмежує змістовність такого порівняння часом життя екземпляра; це не постійний ідентифікатор облікового запису.
Змінний клас цілком може бути корисним елементом множини, якщо його стан, що визначає рівність, стабільний. У прикладі облікового запису displayName можна змінювати, бо ця властивість не бере участі ні в рівності, ні в хешуванні. Це нічого не гарантує щодо одночасного доступу з різних потоків: синхронізація — окреме завдання.
У тестах такої моделі перевіряйте, що знаходиться еквівалентний заново завантажений обліковий запис, зміна неключових полів зберігає входження, а окремі об’єкти з рівністю за ідентичністю залишаються окремими. Зміну ключа перевіряйте через операцію, яка керує колекцією. Не вимагайте в тесті конкретного числового хешу або певної відповіді після порушення вимоги стабільності ключа.
Що перевірити у своєму коді:
- Відкрийте
==іhash(into:)свого типу. Випишіть властивості, які вони читають, наприкладid. - Якщо це ID облікового запису, зробіть його незмінним:
let id. Ім’я та інші поля можна змінювати, якщо вони не беруть участі в рівності й хешуванні. - Якщо потрібно зберігати саме окремі живі екземпляри, використовуйте разом
===іObjectIdentifier(self), як у прикладіSessionвище. - Якщо сам ключ усе ж потрібно змінити, спочатку видаліть об’єкт з кожного
SetчиDictionary, де він є елементом або ключем. Лише потім змініть поле й вставте його знову. Заздалегідь вирішіть, що робити, якщо новий ID уже зайнятий: відхилити зміну чи залишити один рівний елемент. - У тесті перевірте не лише
contains, а й кількість елементів та їхні ID. Після зміни неключового поля елемент має знаходитися; після керованої зміни ключа не повинно залишатися двох рівних елементів.
Додаткові ресурси
- Фото обкладинки: Card catalogue drawers, Carolina Prysyazhnyuk, CC BY-SA 2.0. Зменшено та конвертовано у WebP.
- Фото голубника: Pigeons-in-holes, BenFrantzDale, CC BY-SA 3.0. Зменшено та конвертовано у WebP.
- Фото роторів Enigma: Enigma rotors with alphabet rings, TedColes, CC0 1.0. Зменшено та конвертовано у WebP.
- Приклади коду в онлайн-редакторі:
MutateInPlace.swift,RemoveThenInsert.swift,MutationLookup.swift,SeedExperiment.swift,IdentityModels.swift - Hashable: рівні значення хешують однакові суттєві компоненти.
- ObjectIdentifier: ідентичність протягом життя екземпляра.
- Реалізація пошуку Swift NativeSet.
- Відображення в комірки та seed таблиці у Swift HashTable.
- Hasher: seed виконання та обмеження збереження хешів.
- Реалізація SipHash і поєднання seed.
- Ініціалізація runtime та детерміноване хешування.
- SE-0206: Hashable Enhancements.
- Swift 4.2: рандомізоване хешування й Hasher у release notes Apple.
- Karoy Lorentey: відмінності хешування у Swift 4.1 і 4.2.
- Hasher: не зберігати хеші між запусками.
- SHA256 у CryptoKit.
Обговорення
Переклад коментарів
Мову не знайдено.