it-swarm-vi.com

Các hằng số băm "ma thuật" như 0x9e3779b9 và 0x9e3779b1 đến từ đâu?

Trong mã xử lý các bảng băm, tôi thường tìm thấy hằng số 0x9e3779b9 hoặc đôi khi 0x9e3779b1. Ví dụ

hash = n * 0x9e3779b1 >>> 24

Tại sao giá trị đặc biệt này được sử dụng?

137
bkgs

0x9e3779b9 là phần không thể thiếu của phần phân số của Golden Ratio 0,61803398875 (sqrt (5) -1)/2, nhân với 2 ^ 32.

Do đó, nếu φ = (sqrt (5) +1)/2 = 1.61803398875 là Tỷ lệ vàng, hàm băm sẽ tính phần phân số của n *, có thuộc tính tán xạ Nice. Để thuyết phục bản thân, chỉ cần tạo một âm mưu phân tán của (n, n*c-FLOOR(n*c)) trong bảng tính yêu thích của bạn, thay thế c bằng, e, π, v.v. Một số vấn đề thực tế thú vị khi nhận sai được mô tả trong https://lkml.org/lkml/ 2016/4/29/838 .

Phương pháp này thường được gọi là "Băm tỷ lệ vàng" hay "Băm sợi" và được phổ biến bởi Donald Knuth (Nghệ thuật lập trình máy tính: Tập 3: Sắp xếp và tìm kiếm). Về mặt lý thuyết số, nó chủ yếu tập trung vào Giả thuyết Steinhaus ( https://en.wikipedia.org/wiki/Three-gap_theorem ) và tính đối xứng đệ quy của các phần phân số của bội số của bội số Tỷ lệ vàng.

Thỉnh thoảng, bạn cũng có thể thấy 0x9e3779b1, là số nguyên tố gần nhất với 0x9e3779b9 (và dường như là một chút "sùng bái hàng hóa" vì đây không phải là hàm băm mô-đun). Tương tự, 0x9e3779b97f4a7c150x9e3779b97f4a7c55 là tương đương 64 bit của các số này.

220
32f

Các câu trả lời khác giải thích ý định đằng sau những con số ma thuật đó, có lẽ là những gì bạn muốn biết. Tuy nhiên, người ta có thể nói rằng "họ đến từ đâu" là từ thực tiễn lập trình xấu. Số ma thuật là xấu, và chúng không bao giờ nên được sử dụng. Các hằng số như được đề cập phải được đặt tên biến mô tả phù hợp và thậm chí có thể thêm các bình luận vào nơi chúng được xác định. Sau đó, mỗi lần xuất hiện của các giá trị trong mã phải ở dạng biến được đặt tên. Trường hợp này xảy ra trong các mã nơi bạn đáp ứng các giá trị đó, bạn sẽ không bị bối rối bởi ý định của chúng ở nơi đầu tiên.

ví dụ:

Ví dụ xấu - sử dụng số ma thuật

hash = n * 0x9e3779b1

Ví dụ tốt hơn - với ý kiến ​​và biến có ý nghĩa

# Golden Ratio constant used for better hash scattering
# See https://softwareengineering.stackexchange.com/a/402543 
GOLDEN_RATIO = 0x9e3779b1
hash = n * GOLDEN_RATIO
30
isilanes
Trong mã xử lý các bảng băm, tôi thường tìm thấy hằng số 0x9e3779b9 hoặc đôi khi 0x9e3779b1

Câu trả lời khác giải thích chính xác tại sao giá trị này được sử dụng. Tuy nhiên, nếu bạn thường xuyên tìm thấy hằng số này, điều bạn có thể không nhận ra là bạn thường thấy mã dễ bị tấn công bởi lũ lụt.

Có hai chiến lược chống lại các cuộc tấn công lũ lụt băm:

  1. Sử dụng hàm băm an toàn có một hạt giống ngẫu nhiên bí mật. Hàm băm của bạn không có một hạt giống ngẫu nhiên bí mật. Murmurhash3_32 có một hạt ngẫu nhiên bí mật, nhưng nó có các đa bào độc lập với hạt do trạng thái bên trong nhỏ. Hàm băm tốt nhất có bảo mật gần mã hóa và hiệu năng vẫn gần như chấp nhận được có lẽ là SipHash. Thật không may, nó chậm, mặc dù không chậm như SHA512, v.v.

  2. Sử dụng hàm băm nhanh chóng để tính toán (chẳng hạn như hàm băm bạn đã tìm thấy hoặc Murmurhash3_32) và làm cho mỗi nhóm băm vào gốc của cây tìm kiếm nhị phân cân bằng. Vì vậy, một bảng băm được xâu chuỗi riêng biệt thông thường có mỗi nhóm dưới dạng một danh sách được liên kết, sẽ chậm nếu nhiều giá trị băm vào cùng một nhóm. Bằng cách biến nó thành một cây tìm kiếm nhị phân cân bằng như cây AVL hoặc cây đỏ đen, bạn vẫn đảm bảo hiệu suất trong trường hợp xấu nhất.

Ý kiến ​​của tôi là (2) tốt hơn vì SipHash quá chậm. Ngoài ra, trong không gian kernel của hệ điều hành có thể không có đủ entropy để tạo một hạt giống ngẫu nhiên bí mật sớm trong giai đoạn khởi động, vì vậy trong không gian kernel, bạn có thể không có khả năng tạo số ngẫu nhiên sớm khi khởi động.

Bảng băm được sử dụng rộng rãi. Thật dễ dàng để đưa nhiều hệ thống xuống thực tế chỉ bằng cách gửi nhiều giá trị băm vào cùng một nhóm.

5
juhist