Số ma thuật tăng :: hash_combine

Question

Hàm mẫu boost::hash_combine lấy tham chiếu đến băm (được gọi là seed) và một đối tượng v. Theo docs, nó kết hợp seed với các hash của v bởi

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 

tôi có thể thấy rằng đây là xác định. Tôi thấy lý do tại sao một XOR được sử dụng.

Tôi đặt cược phần bổ sung giúp lập bản đồ các giá trị tương tự nhau cách nhau để thăm dò bảng băm sẽ không bị hỏng, nhưng ai đó có thể giải thích hằng số ma thuật là gì?

Answer 1

Số ma thuật được cho là 32 bit ngẫu nhiên, trong đó mỗi số đều có khả năng là 0 hoặc 1 và không có mối tương quan đơn giản giữa các bit. Một cách phổ biến để tìm một chuỗi các bit như vậy là sử dụng việc mở rộng nhị phân của một số vô tỉ lệ; trong trường hợp này, con số đó là nghịch đảo của tỷ lệ vàng:

phi = (1 + sqrt(5))/2 
2^32/phi = 0x9e3779b9 

Vì vậy, bao gồm số này "ngẫu nhiên" thay đổi từng bit của hạt; như bạn nói, điều này có nghĩa là các giá trị liên tiếp sẽ cách xa nhau. Bao gồm các phiên bản dịch chuyển của hạt giống cũ đảm bảo rằng, ngay cả khi hash_value() có phạm vi giá trị khá nhỏ, sự khác biệt sẽ sớm được trải rộng trên tất cả các bit.

Answer 2

Hãy xem qua số DDJ article by Bob Jenkins from 1997. Hằng số ma thuật ("tỷ lệ vàng") được giải thích như sau:

Tỷ lệ vàng thực sự là một giá trị tùy ý. Mục đích của nó là tránh ánh xạ tất cả các số không đến tất cả các số không.