Cài đặt hàm băm cho số thực

Vo_Xuan_Tu · June 25, 2020, 2:35pm

mọi người cho em hỏi là sao để ta cài đặt hàm băm cho số thực được ạ.

noz1995 · June 25, 2020, 1:23pm

Ví dụ MD5 cho số thực x:

String hash = MD5("" + x);

Hay bạn muốn nó phức tạp thế nào?

Vo_Xuan_Tu · June 25, 2020, 2:35pm

Bình thường ta có hàm

int hash(int x) { return x%M; }

M là size của bảng băm. Bây giờ mình muốn đầu vô là kiểu số thực thay vì int thì ta sửa nó như thế nào hả bạn. cái đoạn code trên của bạn mình đọc không hiểu.

SITUVN.gcd · June 25, 2020, 2:03pm

Ép về số nguyên. Nhưng cách này gây sai số.
Lấy BitInt của số thực. Từ khóa tìm kiếm: float bit to int.
Đối với C và C++ thì có thể dùng cách đơn giản là ép kiểu con trỏ. float* -> int* và double* -> long long*. Mà, còn khoản Little-Endian và Big-Endian cho số nguyên nữa. Chả biết có quy định gì về khoản này không nữa.

tntxtnt · June 25, 2020, 2:25pm

C++ có std::hash<float> và std::hash<double> nha :V ko cần tự ép đâu :V
https://en.cppreference.com/w/cpp/utility/hash

float f = ...;
size_t hashValue = std::hash<float>{}(f);

github.com

microsoft/STL/blob/7447ad59d61f50c13861878f340d051c298458df/stl/inc/type_traits#L2255


struct hash

    : _Conditionally_enabled_hash<_Kty,

          !is_const_v<_Kty> && !is_volatile_v<_Kty> && (is_enum_v<_Kty> || is_integral_v<_Kty> || is_pointer_v<_Kty>)> {

    // hash functor primary template (handles enums, integrals, and pointers)

    static size_t _Do_hash(const _Kty& _Keyval) noexcept {

        return _Hash_representation(_Keyval);

    }

};



template <>

struct hash<float> {

    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef float _ARGUMENT_TYPE_NAME;

    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef size_t _RESULT_TYPE_NAME;

    _NODISCARD size_t operator()(const float _Keyval) const noexcept {

        return _Hash_representation(_Keyval == 0.0F ? 0.0F : _Keyval); // map -0 to 0

    }

};



template <>

struct hash<double> {

    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef double _ARGUMENT_TYPE_NAME;

source code của MSVC :V Họ chuyển -0.0 về 0.0, rồi cast float đó thành const unsigned char*, rồi cộng từng byte vào kết quả cuối cùng, mỗi lần cộng byte lại nhân với 1 số ng tố nào đó :V

xài code này chắc phải gắn thêm Apache license gì nữa =]

Vo_Xuan_Tu · June 25, 2020, 2:27pm

cảm ơn đã giúp em. Em mới là sinh viên IT năm nhất thôi nên đọc cái code trên em ko hiểu gì hết

tntxtnt · June 25, 2020, 2:49pm

mò từ từ mà đọc :V
hash<float>::operator() gọi _Hash_representation
_Hash_representation lại gọi tiếp _Fnv1a_append_value
_Fnv1a_append_value gọi _Fnv1a_append_bytes
_Fnv1a_append_bytes nó như thế này:

    for (size_t _Idx = 0; _Idx < _Count; ++_Idx) {
        _Val ^= static_cast<size_t>(_First[_Idx]);
        _Val *= _FNV_prime;
    }
    return _Val;

đồng nghĩa với val = (val xor byte[i]) * prime rồi return val thôi, ban đầu val có giá trị offset là _FNV_offset_basis = 14695981039346656037ULL (win64 - 64-bit target), còn prime là _FNV_prime = 1099511628211ULL. Mảng byte thì ép kiểu tử input float reinterpret_cast<const unsigned char*>(_First) :V

Sherly1001 · June 26, 2020, 6:28am

Số thực thì lưu vào máy cũng là một dãy bit 0 1, ngồi nghĩ hàm băm cho cái dãy kia cũng được.