Коллизия хэш-мапы
🟠 lvl: mid+
👆 В предыдущих сериях мы узнали о Hashable и для чего он нужен. Сейчас же поговорим о коллизиях хэша.
Напомню, хэш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера. В иос за это отвечает Hasher
До этого стандарта разработчики страдали частой коллизией, особенно работая с цветами.
ℹ️ Коллизия происходит, когда разные входные данные производят одинаковый хэш, но значения не равны
Хэш-функция считается устойчивой к коллизиям до того момента, пока не будет обнаружена пара сообщений, дающая одинаковый выход. Стоит отметить, что коллизии всегда будут существовать для любой хэш-функции по той причине, что возможные входы бесконечны, а количество выходов конечно
С хорошей хэш-функцией простые поиски, вставки и удаления занимают в среднем постоянное время. Однако если хеш-функция выбрана недостаточно точно для соответствия данным, ожидаемое время таких операций может стать пропорциональным количеству элементов, хранящихся в таблице.
Детальнее можно познакомиться отличном материале SE-0206
✅ Итого: По умолчанию Swift использует универсальную хэш-функцию, которая сводит последовательность байтов к одному целому числу.
Однако мы можем улучшить её, адаптировав хэш-функцию к своему домену.
- Почитать о производительности Hasher в треде с сеньором-помидором из яблока
- Мощненькое чтиво про приемы хэширования
🟠 lvl: mid+
Напомню, хэш-функция - это математический алгоритм, который отображает данные произвольного размера в битовый массив фиксированного размера. В иос за это отвечает Hasher
До этого стандарта разработчики страдали частой коллизией, особенно работая с цветами.
ℹ️ Коллизия происходит, когда разные входные данные производят одинаковый хэш, но значения не равны
Хэш-функция считается устойчивой к коллизиям до того момента, пока не будет обнаружена пара сообщений, дающая одинаковый выход. Стоит отметить, что коллизии всегда будут существовать для любой хэш-функции по той причине, что возможные входы бесконечны, а количество выходов конечно
С хорошей хэш-функцией простые поиски, вставки и удаления занимают в среднем постоянное время. Однако если хеш-функция выбрана недостаточно точно для соответствия данным, ожидаемое время таких операций может стать пропорциональным количеству элементов, хранящихся в таблице.
Детальнее можно познакомиться отличном материале SE-0206
✅ Итого: По умолчанию Swift использует универсальную хэш-функцию, которая сводит последовательность байтов к одному целому числу.
Однако мы можем улучшить её, адаптировав хэш-функцию к своему домену.
- Почитать о производительности Hasher в треде с сеньором-помидором из яблока
- Мощненькое чтиво про приемы хэширования