Cách băm một vector số?

Question

Có bất kỳ thuật toán băm đã biết nào nhập vào một vectơ của int và xuất một int đơn lẻ hoạt động tương tự như một sản phẩm bên trong không?

Nói cách khác, tôi đang nghĩ về một thuật toán băm mà có thể trông như thế này trong C++:

// For simplicity, I'm not worrying about overflow, and assuming |v| < 7. 
int HashVector(const vector<int>& v) { 
    const int N = kSomethingBig; 
    const int w[] = {234, 739, 934, 23, 828, 194}; // Carefully chosen constants. 
    int result = 0; 
    for (int i = 0; i < v.size(); ++i) result = (result + w[i] * v[i]) % N; 
    return result; 
} 

Tôi quan tâm đến điều này bởi vì tôi đang viết lên một bài báo về một thuật toán mà sẽ có lợi từ bất kỳ tác phẩm nào trước đây trên các băm tương tự. Đặc biệt, nó sẽ là tuyệt vời nếu có bất cứ điều gì được biết về các thuộc tính va chạm của một thuật toán băm như thế này.

Thuật toán tôi quan tâm sẽ là vectơ số nguyên băm, nhưng một số thứ cho vectơ nổi cũng sẽ rất tuyệt.

Làm rõ

Các băm được thiết kế để sử dụng trong một bảng băm để tra cứu key/value nhanh. Không có mối quan tâm an ninh ở đây.

Câu trả lời mong muốn giống như một tập hợp các hằng số hoạt động đặc biệt tốt cho một băm như thế này - tương tự như một số nhân và modulo, hoạt động tốt hơn các số khác như một trình tạo số giả ngẫu nhiên.

Ví dụ, một số lựa chọn hằng số cho bộ tạo giả ngẫu nhiên tuyến tính được biết là cung cấp độ dài chu kỳ tối ưu và có modulo dễ tính toán. Có thể ai đó đã thực hiện nghiên cứu để chỉ ra rằng một tập hợp các hằng số nhân, cùng với một hằng số modulo, trong một băm vectơ có thể làm giảm nguy cơ va chạm giữa các vectơ số nguyên lân cận.

Answer 1

Tôi đã thực hiện một số thử nghiệm (chưa được xuất bản, thực tế) với thử nghiệm một loạt các thuật toán băm chuỗi. (Nó chỉ ra rằng hàm băm mặc định của Java cho Strings sucks.)

Thí nghiệm đơn giản là để băm từ điển tiếng Anh và so sánh bao nhiêu va chạm mà bạn có trong thuật toán A vs thuật toán B.

Bạn có thể xây dựng một tương tự thử nghiệm: tạo ngẫu nhiên $ BIG_NUMBER các vectơ có thể có độ dài 7 hoặc ít hơn. Băm chúng vào thuật toán A, băm chúng vào thuật toán B, sau đó so sánh số lượng và mức độ nghiêm trọng của va chạm.

Sau khi bạn có thể thực hiện điều đó, bạn có thể sử dụng kỹ thuật ủ mô phỏng hoặc kỹ thuật tương tự để tìm "số ma thuật" hoạt động tốt cho bạn. Trong tác phẩm của tôi, với các từ vựng được quan tâm và kích thước băm giới hạn chặt chẽ, chúng tôi có thể thực hiện thuật toán chung cho một số ngôn ngữ của con người bằng cách thay đổi "số ma thuật".

Answer 2

Tùy thuộc vào kích thước của các hằng số, tôi phải nói mức độ hỗn loạn trong vector đầu vào sẽ có tác động đến kết quả. Tuy nhiên, phân tích định tính nhanh về bài đăng của bạn sẽ gợi ý rằng bạn có một khởi đầu tốt:

• Đầu vào của bạn được nhân lên, do đó tăng mức độ tách biệt giữa các giá trị đầu vào tương tự cho mỗi lần lặp lại (ví dụ: 65 + 66 nhỏ hơn 65 * 66), rất tốt.
• Đó là xác định, trừ khi vectơ của bạn nên được coi là một tập hợp chứ không phải là một chuỗi. Để rõ ràng, v = {23, 30, 37} có khác với v = {30, 23, 37} không?
• Tính đồng nhất của phân phối sẽ thay đổi dựa trên phạm vi và sự hỗn loạn của giá trị đầu vào trong v. Tuy nhiên, đó cũng đúng với thuật toán băm số nguyên tổng quát.

Ngạc nhiên, tại sao không chỉ sử dụng thuật toán băm hiện có cho số nguyên và thực hiện một số phép tính thú vị về kết quả?

Answer 3

Mặc dù tôi có thể hoàn toàn hiểu nhầm bạn, nhưng có thể là một ý tưởng hay để xử lý vectơ dưới dạng luồng byte và thực hiện một số băm trên đó, tức là SHA1 hoặc MD5.

Chỉ cần làm rõ, các băm đó được biết là có các đặc tính băm tốt và tôi tin rằng không có lý do gì để tạo lại một chiếc xe đạp và để thực hiện băm mới. Một khả năng khác là sử dụng ma trận CRC đã biết.

Answer 4

Python dùng để băm tuples theo cách này (source):

class tuple: 
    def __hash__(self): 
     value = 0x345678 
     for item in self: 
      value = c_mul(1000003, value)^hash(item) 
     value = value^len(self) 
     if value == -1: 
      value = -2 
     return value 

Trong trường hợp của bạn, item sẽ luôn luôn là một số nguyên, trong đó sử dụng thuật toán này:

class int: 
    def __hash__(self): 
     value = self 
     if value == -1: 
      value == -2 
     return value 

này không có gì để làm với một sản phẩm bên trong, mặc dù ... vì vậy có lẽ nó không giúp đỡ nhiều.