Hacker News Digest

Автор обсуждает реализацию идеального хеширования для строк, где известный набор строк отображается в целые числа с отверганием остальных. Критикуется подход с использованием PEXT (из-за больших таблиц, отсутствия на ARM и медленной работы на старых x86), предлагается альтернатива из шахматного программирования — "магические битборды". Метод заключается в умножении значения на магическое число (например, 0x28400000U) и сдвиге верхних бит для получения уникальных индексов. Для строк длиной 4 символа это позволяет создать компактную таблицу с 10 записями, где проверка memcmp гарантирует отсутствие ложных срабатываний.

Для строк разной длины можно выбирать различные битовые диапазоны (16, 32 или 64 бита) или их комбинации. В удачных случаях, как с 24-символьными CSS-ключами, удается найти магическое число, дающее прямую индексацию без промежуточной таблицы. Авторы предпочитают меньшие типы данных для компактности кода и возможности перебора вместо случайного поиска. Подход эффективен для наборов в тысячи строк с допустимым временем компиляции.

• Обсуждение началось с вопроса о том, как создать идеальный хеш-функцию для известного набора ключей, и обсуждение затронуло как теоретические, так и практические аспекты, включая использование gperf и других инструментов.
• Участники обсудили, что вместо попыток создать идеальную хеш-функцию, иногда более практичным решением может быть отказ от совершенства в пользу более простого решения, особенно если набор ключей не полностью известен заранее.
• Также было отмечено, что существуют библиотеки, такие как marisa-trie и другие, которые могут быть использованы для эффективного хранения и поиска больших наборов строк, и что они могут быть использованы вместо попыток создать идеальную хеш-функцию.
• Было также упомянуто, что в некоторых случаях может быть более практично использовать простые, но менее идеальные решения, особенно если это позволяет избежать сложностей, связанных с созданием идеальной хеш-функции.
• В конце обсуждение вернулось к вопросу о том, как лучше всего подходить к проблеме создания идеальной хеш-функции для известного набора ключей, и было высказано мнение, что вместо попыток создать идеальную хеш-функцию, иногда более разумно может быть просто использовать существующие инструменты и библиотеки.

Написанная на Rust утилита ut предлагает разработчикам набор инструментов для повседневных задач, вдохновляясь функциональностью it-tools.tech. Она включает конвертеры, генераторы хешей, кодировщики и другие инструменты для работы с данными, кодом и системами. Проект стремится объединить распространённые утилиты в одном месте, упрощая доступ без переключения между сервисами.

Использование Rust обеспечивает высокую производительность и безопасность, а модульная архитектура позволяет легко расширять функционал. Это решение особенно полезно для команд, ценящих локальные инструменты без зависимости от облачных сервисов.

• Предложения по распространению: упаковать как Python и NPM модули для удобного запуска через uvx или npx, использовать cargo-dist для автоматизации.
• Критика архитектуры: обсуждается целесообразность единого бинарника (по аналогии с BusyBox) против множества отдельных утилит в духе UNIX-философии "делай одно дело хорошо".
• Вопросы к функционалу: предостережения против включения слишком большого количества функций (например, HTTP), предложения добавить конкретные команды (uuidv7, retry).
• Замечания по реализации: критика требований к вводу (только UTF-8, чтение stdin до EOF), отсутствие тестов для кода, созданного с помощью ИИ.
• Общая оценка: инструмент воспринят как удобный "швейцарский нож" с продуманными умолчаниями, но вызвал дискуссию о разумных пределах его роста.

Разработан плагин Note Codes для Obsidian, который присваивает каждой заметке в хранилище уникальный четырёхсимвольный код. Эти коды позволяют быстро ссылаться на заметки из других мест, например из рукописных записей. Для удобства реализован обработчик протокола, так что ссылка вида obsidian://note-codes/open?code=XX-XX сразу откроет соответствующую заметку.

Коды генерируются на основе имени и пути файла с использованием SHA-256 и кодировки Base32 по схеме Дугласа Крокфорда. Исключены легко путаемые символы вроде O, I, L, U, но плагин корректно обрабатывает их при поиске. Ёмкость системы — 1 048 576 уникальных кодов. Плагин открыт и доступен на GitHub.

• Обсуждается практичность 4-символьных кодов для краткой идентификации заметок в Obsidian, основанных на хеше имени файла.
• Поднимается проблема коллизий из-за малого пространства кодов (1 млн вариантов) и парадокса дней рождений, особенно при большом количестве заметок.
• Критикуется привязка кода к имени и пути файла, так как это делает ссылки нестабильными: код меняется при переименовании или перемещении заметки.
• Предлагаются альтернативы: использование уникальных префиксов (как в Git), GUID или эвристик для генерации кодов, связанных с содержимым.
• Основное предназначение кодов — быстрое указание на заметки из внешних источников (например, рукописных записей), но это же делает проблему нестабильности ссылок критичной.

• Сортировка с хешем быстрее хеш-таблиц: на больших данных 1,5–4×, несмотря на «O(n log n)».
• Память: хеш-таблица тянет 128 Б на 8-Б ключ (64 чтение + 64 запись), радикс-сорт 3 прохода — 48 Б (вся линия кэша используется).
• Плохие распределения (мало заполненных корзин) замедляют радикс-сорт; решаем хешем hash(key) перед сортировкой. Берём обратимую функцию (Murmur3, MulSwapMul), хешируем «на лету» в первом проходе.
• Результат: 2 ГиБ уникальных uint64 за 1,9 с против 2,6 с у оптимизированной хеш-таблицы.
• Подходит, когда порядок не важен, а нужны только уникальные значения; иначе остаёмся на хеш-таблицах.

• Улучшенная нестабильная сортировка Rust почти догнала по скорости специально настроенный radix-sort, несмотря на разницу в O(n log n) vs O(n).
• Хэш-таблица «побеждает» лишь при ограниченном размере ключа и хорошем кэше; при росте данных снова проигрывает из-за промахов и O(n log n) внутри.
• Radix можно ускорить, выделяя buckets через MMU, а не вручную управляя памятью.
• На очень больших объёмах (≥120 ГБ) константы radix снова могут перевесить, но пока доминирует кэш-эффективность сортировки.
• Всё обсуждение подчёркивает: конкретные константы и архитектура CPU важнее «чистой» Big-O.