Почему одна и та же хэш-функция Python и Rust дает разные результаты для одной и той же строки?
TL;DR:
При одинаковых параметрах обе хеш-функции дают одинаковые результаты. Для этого необходимо выполнить несколько предварительных условий.
Я создаю систему, в которой есть части на Rust и Python. Мне нужна библиотека хеширования, которая выдает одинаковые значения для одного и того же ввода на обоих концах. Я думал, что Python и Rust также используют SipHash 1-3, поэтому я попытался использовать его.
Питон:
>>> import ctypes
>>> ctypes.c_size_t(hash(b'abcd')).value
14608482441665817778
>>> getsizeof(ctypes.c_size_t(hash(b'abcd')).value)
36
>>> type(b'abcd')
<class 'bytes'>
Ржавчина:
use hashers::{builtin::DefaultHasher};
use std::hash::{Hash, Hasher};
pub fn hash_str(s: &str) -> u64 {
let mut hasher = DefaultHasher::new();
s.hash(&mut hasher);
hasher.finish()
}
pub fn hash_bytes(b: &[u8]) -> u64 {
let mut hasher = DefaultHasher::new();
b.hash(&mut hasher);
hasher.finish()
}
fn test_hash_str() {
let s1: &str = "abcd";
let h1: u64 = hash_str(s1);
assert_eq!(h1, 13543138095457285553);
}
#[test]
fn test_hash_bytes() {
let b1: &[u8] = "abcd".as_bytes();
let h1: u64 = hash_bytes(b1);
assert_eq!(h1, 18334232741324577590);
}
К сожалению, я не могу получить одинаковые значения на обоих концах. Есть ли способ как-то получить те же значения?
ОБНОВЛЯТЬ:
После проверки реализации Python обнаружилась деталь, которую я изначально пропустил, так что Python использует своего рода случайную соль для каждого запуска. Это означает, что результат, который я получил от функции Python, не может быть таким же, как в версии Rust.
Это можно отключить с помощью PYTHONHASHSEED=0 python...
Однако это по-прежнему не заставляет Python создавать те же значения, что и версия Rust. Я пробовал пользовательские реализации SipHash на обоих концах. Результаты совпадают на обоих концах:
Оба используют siphasher::sip::SipHasher13; и DefaultHasher выдает те же результаты. Результат для строки такой же, как и для &str, но отличается для версии .as_bytes().
#[test]
fn test_hash_string() {
let s1: String = "abcd".to_string();
let h1: u64 = hash_string(s1);
assert_eq!(h1, 13543138095457285553);
}
#[test]
fn test_hash_str() {
let s1: &str = "abcd";
let h1: u64 = hash_str(s1);
assert_eq!(h1, 13543138095457285553);
}
#[test]
fn test_hash_bytes() {
let b1: &[u8] = "abcd".as_bytes();
let h1: u64 = hash_bytes(b1);
assert_eq!(h1, 18334232741324577590);
}
На стороне Python после отключения рандомизации:
sh = SipHash(c=1, d=3)
h = sh.auth(0, "abcd")
assert h == 16416137402921954953
Хеш-функция — это не что-то одно, например, скажем, структура данных стека. Существует бесконечно много возможных хеш-функций, одни бесполезны, другие годятся для каких-то целей, некоторые для других. Важно знать, какую хэш-функцию вы используете, чтобы вы могли использовать ту же самую в другой программе или языке; вот где полезны такие стандарты, как SHA256.
По крайней мере, вам нужно отключить рандомизацию. Вы?
@KellyBundy, как отключить рандомизацию? Кажется, Rust инициализирует хэш-функцию k0 = 0 и k1 = 0. Что вы подразумеваете под рандомизацией?
@chepner Я знаю. Как я уже сказал, Python и Rust используют SipHash 1-3. Возможно, есть небольшие различия в реализации, и поэтому они дают разные результаты.
@chepner hashlib имеет ограниченный набор хеш-функций, которые в первую очередь предназначены для обеспечения безопасности и достаточно эффективны. SipHash идеально подходит для того варианта использования, для которого я хотел бы его использовать. На самом деле, он обладает лучшими свойствами, чем те, что реализованы в hashlib.
@Istvan Смотрите -R и PYTHONHASHSEED.
@KellyBundy woo Я не знал об этом! Большое спасибо. Это объясняет, почему я получаю разные результаты.
Означает ли это, что вы получите те же результаты после его отключения? Тогда, пожалуйста, опубликуйте ответ с ним. Я не могу проверить это на себе. И мне уже было неудобно частично ответить на него здесь.
@KellyBundy Я работаю над тестовым случаем, чтобы проверить. Я собираюсь опубликовать это!! :)
@KellyBundy, к сожалению, нет, PYTHONHASHSEED=0 дает те же результаты, но отличаются от версии Rust.
@KellyBundy действительно интересно то, что он дает одно и то же значение для «abcd» и b «abcd», в то время как Rust дает разные результаты.
@KellyBundy Это интересно, но мне все еще интересно, как я могу иметь одинаковые значения с хеш-функцией из обоих языков. По крайней мере, результаты совпадают на обоих концах.
Какую версию Python вы используете? И можете ли вы сказать, какой (если есть) Python или Rust вычисляет «правильное» значение?
Питон 3.11. Не уверен. Позвольте мне попытаться выкопать больше языков и результатов.
Есть такой сайт: md5hashing.net
«Как я могу иметь одинаковые значения с хеш-функцией из обоих языков», — Чепнер уже ответил на этот вопрос. Используя библиотеку, предназначенную для этой цели. Внутренняя хеш-функция специально не предназначена для обмена между языками и может измениться в любое время. Rust даже заявляет, что в документации std::collections::hash_map::DefaultHasher: The internal algorithm is not specified, and so it and its hashes should not be relied upon over releases.
Ответы 1
Не используйте внутренний хэш для внешних целей. Он не должен быть предсказуемым или совместимым, он просто предназначен для использования в качестве внутреннего хеширования. Rust даже упоминает об этом в своих документах:
Внутренний алгоритм не указан, поэтому он и его хэши не следует полагаться на релизы.
Не используйте
.hash()функциональность типов Rust. Он также не предназначен для внешних хэшей; он выполняет некоторую неуказанную внутреннюю бинаризацию данных. Используйте функциональность хэшера.writeнапрямую, чтобы передать ему двоичные данные.
Тем не менее, решение состоит в том, чтобы использовать определенную библиотеку хеширования для вашей цели совместимости, а не внутреннюю.
В Rust это наверное сифашер если хотите сифаш-1-3. Однако я не уверен насчет Python, так как давно им не пользовался.
Вот пример кода для Rust:
use siphasher::sip::SipHasher13;
use std::hash::Hasher;
pub fn hash_str(s: &str) -> u64 {
hash_bytes(s.as_bytes())
}
pub fn hash_bytes(b: &[u8]) -> u64 {
let mut hasher = SipHasher13::new();
hasher.write(b);
hasher.finish()
}
#[test]
fn test_hash_str() {
let s1: &str = "abcd";
let h1: u64 = hash_str(s1);
assert_eq!(h1, 16416137402921954953);
}
#[test]
fn test_hash_bytes() {
let b1: &[u8] = "abcd".as_bytes();
let h1: u64 = hash_bytes(b1);
assert_eq!(h1, 16416137402921954953);
}
Обратите внимание, что хотя я действительно не рекомендую это делать, то же самое относится и к внутреннему хэшеру Rust:
use std::hash::Hasher;
fn main() {
let mut hasher = std::collections::hash_map::DefaultHasher::new();
hasher.write("abcd".as_bytes());
println!("{}", hasher.finish());
}
16416137402921954953
Фон
Так почему же s.hash() и s.as_bytes().hash() ведут себя странно?
Напишем простой отладочный хэшер:
use std::hash::{Hash, Hasher};
struct DebugHasher;
impl Hasher for DebugHasher {
fn finish(&self) -> u64 {
0
}
fn write(&mut self, bytes: &[u8]) {
println!(" write: {:?}", bytes);
}
}
fn main() {
let s = "abcd";
println!("--- s ---");
s.hash(&mut DebugHasher);
println!("--- s.as_bytes() ---");
s.as_bytes().hash(&mut DebugHasher);
}
--- s ---
write: [97, 98, 99, 100]
write: [255]
--- s.as_bytes() ---
write: [4, 0, 0, 0, 0, 0, 0, 0]
write: [97, 98, 99, 100]
Теперь у нас есть ответ:
sкажется добавляется0xff. Это также можно увидеть в его исходном коде:fn write_str(&mut self, s: &str) { self.write(s.as_bytes()); self.write_u8(0xff); }s.as_bytes(), кажется, прикрепляет странные байты спереди. В его исходном коде видно, что это длина строки:#[stable(feature = "rust1", since = "1.0.0")] #[rustc_const_unstable(feature = "const_hash", issue = "104061")] impl<T: ~const Hash> const Hash for [T] { #[inline] fn hash<H: ~const Hasher>(&self, state: &mut H) { state.write_length_prefix(self.len()); Hash::hash_slice(self, state) } }
Спасибо! Это было действительно поучительно.
Может быть интересно упомянуть, почему добавляются такие посторонние байты. Короче говоря, речь идет о различении катенаций. Представьте себе кортеж из 2 полей: ("Hello, World", "") vs ("Hello, ", "World!"). Это не одни и те же кортежи, поэтому они должны создавать разные хеши. То же самое и с ломтиками. Чтобы различать, добавляются посторонние части данных (префикс или суффикс).
@MatthieuM. Я не понимаю. Зачем что-то нужно добавлять в эти кортежи?
@KellyBundy: эти кортежи не равны, поэтому было бы лучше, если бы их хэши были разными. Если вы просто хешируете последовательность 'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd' для обоих, поскольку вы начинаете с одной и той же последовательности, вы получаете один и тот же хеш. Для более качественного хэша — такого, который различает два кортежа — вам нужно ввести некоторую разницу между ними. В Rust выбор состоял в том, чтобы добавить маркер суффикса для строк (используя байт, который никогда не встречается в UTF-8) и длину префикса для срезов (более дорогой, но T неизвестен, никакой маркер не будет работать).
@MatthieuM. Ах, значит, '!' во втором кортеже — опечатка? А кортежи хэшируются путем объединения их элементов и хеширования результата? Я думаю, что Python делает это по-другому, элементы кортежа хешируются отдельно, а их хэши затем объединяются с другим алгоритмом хеширования.
@KellyBundy: На самом деле я забыл это в первом кортеже и не могу редактировать сейчас. Но да, два кортежа должны были содержать строки, которые после связывания были бы равны.
Внутренние хеш-функции предназначены для использования самим языком (например, Python использует их для реализации хеш-таблиц, лежащих в основе реализации
dict). Если вам нужно передать хэш-значения из одной программы в другую, посмотрите (опять же, в Python) алгоритмы, реализованные в модулеhashlib.