Hàm băm giá rất thấp

Question

Tôi cần hàm băm cho bảng tra cứu, để nếu giá trị của tôi từ 0 đến N, tôi cần hàm băm cung cấp cho tôi giá trị từ 0 đến n, là n < < N Một thông tin khác là tôi đã biết N trước.

Tôi đã được investigatinv về hàm băm chi phí thấp khác nhau và tôi đã tìm thấy chỉ này:

h = z mod n range(z) - 0 to N, range(h) - 0 to n 

hàm băm của tôi cần phải được thực hiện trong HW, vì vậy nó cần phải có một chi phí rất thấp. Bất cứ ai có thể giới thiệu bất kỳ công thức hoặc thuật toán khác ngoài những điều đơn giản ?. Khi tôi nói HW tôi có nghĩa là một thực sự thực hiện trong HW, và không hướng dẫn trong một bộ vi xử lý.

Cảm ơn bạn.

Cập nhật với các giải pháp

Cảm ơn tất cả các câu trả lời, tôi sẽ không chọn một yêu thích, bởi vì tất cả chúng đều giá trị ngang nhau tùy thuộc vào các đặc tính của ứng dụng đích.

Answer 1

bit ReWire trong thứ tự ngẫu nhiên và lấy thấp hơn log2(n) bit

Hoặc chỉ mất dưới log2(n) bit nếu dữ liệu của bạn được phân bố đều.

Answer 2

CRC?

Đã có rất nhiều phần cứng hỗ trợ cho quá trình này.

Answer 3

Dạng kinh điển là h(x) = (a*x + b) mod n, trong đó a và b là hằng số và n là kích thước bảng băm của bạn. Bạn muốn làm cho n một số nguyên tố, để có được phân phối tối ưu (ish).

Lưu ý rằng điều này là nhạy cảm với một số loại phân phối nhất định - ví dụ, chỉ cần thực hiện x mod n chủ yếu dựa vào tính ngẫu nhiên của các bit có thứ tự thấp; nếu họ không phải là ngẫu nhiên trong bộ của bạn, bạn sẽ nhận được skew khá đáng kể.

Bob Jenkins đã thiết kế một số chức năng băm rất tốt; đây là một thiết kế đặc biệt để đơn giản để thực hiện trong phần cứng: http://burtleburtle.net/bob/hash/nandhash.html

Đối với rất nhiều hàm băm khác nhau, thảo luận thiết kế, vv, xem phần còn lại của trang web: http://burtleburtle.net/bob/hash/

Answer 4

Tôi tin rằng đây là tốt nhất có thể băm cho vấn đề này (nhanh hơn modulo, phân phối tốt hơn), cho rằng tất cả các số của bạn bằng 0..N có cùng xác suất:

h = z * n/N; 

Trong đó tất cả các giá trị là số nguyên, do đó bạn có một số nguyên. Bằng cách này, mỗi giá trị giữa 0..N được ánh xạ tới chính xác cùng một số giá trị trong n.

Ví dụ, khi n = 3 và N = 7 (giá trị 3 và 7 không nằm trong phạm vi), băm là này:

z * n/N = hash 
---------------- 
0 * 3/7 = 0 
1 * 3/7 = 0 
2 * 3/7 = 0 
3 * 3/7 = 1 
4 * 3/7 = 1 
5 * 3/7 = 2 
6 * 3/7 = 2 

Vì vậy, mỗi giá trị băm được sử dụng như nhau thường, chỉ cần tắt bởi 1. Chỉ cần cẩn thận rằng n*(N-1) không tràn.

Nếu N là lũy thừa của 2, bạn có thể thay thế bộ chia bằng cách dịch chuyển. ví dụ. nếu N = 256:

h = (z * n) >> 8; 

Answer 5

Nếu bạn đang thực sự nói chuyện với phần cứng (so với các phần mềm, hoặc thực hiện phần cứng của phần mềm) và số điện thoại của xô băm n có thể được viết như n = 2 ^m-1 , dễ nhất có lẽ là một chiều dài tối đa linear feedback shift register (LFSR) trong đó CRC là một cá thể. Dưới đây là một cách bạn có thể sử dụng thanh ghi thay đổi m-bit để tạo băm của gói dữ liệu (đảm bảo tất cả dữ liệu được biểu diễn một cách nhất quán như chuỗi K-bit, nếu bạn có chuỗi ngắn hơn thì hãy đệm một đầu bằng số 0.):

1. khởi tạo trạng thái của LFSR (CRC-32 sử dụng tất cả 1 của; tất cả các số có lẽ là xấu)
2. phím Shift trong các bit dữ liệu của bạn
3. (Không bắt buộc) Shift trong một số không j thêm (j giữa m và 2m có lẽ là một lựa chọn tốt); điều này cho biết thêm một số băm bổ sung để giảm tương quan trực tiếp giữa các bit đầu vào/đầu ra
4. Sử dụng nội dung của thanh ghi thay đổi m-bit làm giá trị băm của bạn.