Почему одна и та же хэш-функция 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

Внутренние хеш-функции предназначены для использования самим языком (например, Python использует их для реализации хеш-таблиц, лежащих в основе реализации dict). Если вам нужно передать хэш-значения из одной программы в другую, посмотрите (опять же, в Python) алгоритмы, реализованные в модуле hashlib.

chepner 12.02.2023 16:06

Хеш-функция — это не что-то одно, например, скажем, структура данных стека. Существует бесконечно много возможных хеш-функций, одни бесполезны, другие годятся для каких-то целей, некоторые для других. Важно знать, какую хэш-функцию вы используете, чтобы вы могли использовать ту же самую в другой программе или языке; вот где полезны такие стандарты, как SHA256.

chepner 12.02.2023 16:07

По крайней мере, вам нужно отключить рандомизацию. Вы?

Kelly Bundy 12.02.2023 16:18

@KellyBundy, как отключить рандомизацию? Кажется, Rust инициализирует хэш-функцию k0 = 0 и k1 = 0. Что вы подразумеваете под рандомизацией?

Istvan 12.02.2023 18:12

@chepner Я знаю. Как я уже сказал, Python и Rust используют SipHash 1-3. Возможно, есть небольшие различия в реализации, и поэтому они дают разные результаты.

Istvan 12.02.2023 18:13

@chepner hashlib имеет ограниченный набор хеш-функций, которые в первую очередь предназначены для обеспечения безопасности и достаточно эффективны. SipHash идеально подходит для того варианта использования, для которого я хотел бы его использовать. На самом деле, он обладает лучшими свойствами, чем те, что реализованы в hashlib.

Istvan 12.02.2023 18:14

@Istvan Смотрите -R и PYTHONHASHSEED.

Kelly Bundy 12.02.2023 18:25

@KellyBundy woo Я не знал об этом! Большое спасибо. Это объясняет, почему я получаю разные результаты.

Istvan 12.02.2023 19:29

Означает ли это, что вы получите те же результаты после его отключения? Тогда, пожалуйста, опубликуйте ответ с ним. Я не могу проверить это на себе. И мне уже было неудобно частично ответить на него здесь.

Kelly Bundy 12.02.2023 19:35

@KellyBundy Я работаю над тестовым случаем, чтобы проверить. Я собираюсь опубликовать это!! :)

Istvan 12.02.2023 19:41

@KellyBundy, к сожалению, нет, PYTHONHASHSEED=0 дает те же результаты, но отличаются от версии Rust.

Istvan 12.02.2023 19:47

@KellyBundy действительно интересно то, что он дает одно и то же значение для «abcd» и b «abcd», в то время как Rust дает разные результаты.

Istvan 12.02.2023 19:48

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

Istvan 12.02.2023 20:04

Какую версию Python вы используете? И можете ли вы сказать, какой (если есть) Python или Rust вычисляет «правильное» значение?

Kelly Bundy 12.02.2023 20:13

Питон 3.11. Не уверен. Позвольте мне попытаться выкопать больше языков и результатов.

Istvan 12.02.2023 20:16

Есть такой сайт: md5hashing.net

Istvan 12.02.2023 20:53

«Как я могу иметь одинаковые значения с хеш-функцией из обоих языков», — Чепнер уже ответил на этот вопрос. Используя библиотеку, предназначенную для этой цели. Внутренняя хеш-функция специально не предназначена для обмена между языками и может измениться в любое время. 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.

Finomnis 12.02.2023 23:35
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
18
140
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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)
        }
    }
    

Спасибо! Это было действительно поучительно.

Istvan 13.02.2023 08:19

Может быть интересно упомянуть, почему добавляются такие посторонние байты. Короче говоря, речь идет о различении катенаций. Представьте себе кортеж из 2 полей: ("Hello, World", "") vs ("Hello, ", "World!"). Это не одни и те же кортежи, поэтому они должны создавать разные хеши. То же самое и с ломтиками. Чтобы различать, добавляются посторонние части данных (префикс или суффикс).

Matthieu M. 13.02.2023 10:06

@MatthieuM. Я не понимаю. Зачем что-то нужно добавлять в эти кортежи?

Kelly Bundy 13.02.2023 10:24

@KellyBundy: эти кортежи не равны, поэтому было бы лучше, если бы их хэши были разными. Если вы просто хешируете последовательность 'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd' для обоих, поскольку вы начинаете с одной и той же последовательности, вы получаете один и тот же хеш. Для более качественного хэша — такого, который различает два кортежа — вам нужно ввести некоторую разницу между ними. В Rust выбор состоял в том, чтобы добавить маркер суффикса для строк (используя байт, который никогда не встречается в UTF-8) и длину префикса для срезов (более дорогой, но T неизвестен, никакой маркер не будет работать).

Matthieu M. 13.02.2023 10:27

@MatthieuM. Ах, значит, '!' во втором кортеже — опечатка? А кортежи хэшируются путем объединения их элементов и хеширования результата? Я думаю, что Python делает это по-другому, элементы кортежа хешируются отдельно, а их хэши затем объединяются с другим алгоритмом хеширования.

Kelly Bundy 13.02.2023 10:39

@KellyBundy: На самом деле я забыл это в первом кортеже и не могу редактировать сейчас. Но да, два кортежа должны были содержать строки, которые после связывания были бы равны.

Matthieu M. 13.02.2023 10:42

Другие вопросы по теме