Cách viết hàm băm trong C?

Question

Bảng băm được cho là cách nhanh nhất/tốt nhất để lưu trữ/truy xuất dữ liệu.

sự hiểu biết của tôi về một bảng băm, băm như sau (Xin vui lòng sửa tôi nếu tôi sai hoặc Vui lòng thêm Nếu có bất cứ điều gì nhiều hơn):

• Một Hash Table là gì, nhưng một mảng (một hoặc nhiều chiều) để lưu trữ các giá trị.
• Hashing là quá trình tìm chỉ mục/vị trí trong mảng để chèn/truy xuất dữ liệu. Bạn lấy một (các) mục dữ liệu và chuyển nó thành một khóa (s) cho hàm băm và bạn sẽ nhận được chỉ mục/vị trí để chèn/lấy dữ liệu.

Tôi có một câu hỏi:

Là hàm băm dùng để lưu trữ/lấy dữ liệu từ một KHÁC hàm băm mật mã được sử dụng trong ứng dụng bảo mật để xác thực như MD5, HMAC, SHA-1, vv ..?

Chúng khác nhau theo cách nào?

• Cách viết hàm băm trong C?
• Có một số tiêu chuẩn hoặc nguyên tắc cho nó không?
• Làm cách nào để đảm bảo rằng đầu ra của hàm băm tức là, chỉ mục không nằm ngoài phạm vi?

Thật tuyệt vời nếu bạn có thể đề cập đến một số liên kết tốt để hiểu những điều này tốt hơn.

Answer 1

Bob Jenkins đã viết một mô tả chuyên sâu về hàng hóa của mình, nếu hơi lỗi thời, hash function. Bài viết này có các liên kết đến các hàm băm mới hơn, tốt hơn, nhưng việc ghi lại đề cập đến các mối quan tâm của việc xây dựng một hàm tốt.

Ngoài ra, hầu hết các triển khai bảng băm thực sự sử dụng một danh sách liên kết để giải quyết xung đột. Nếu bạn muốn chỉ sử dụng một mảng thì hàm băm cần kiểm tra các xung đột và tạo ra một chỉ mục băm mới.

Các hàm băm mật mã mà bạn đề cập có thể được sử dụng làm hàm băm cho bảng băm, nhưng chúng chậm hơn nhiều so với hàm băm được thiết kế cho bảng băm. Tốc độ làm cho các cuộc tấn công bạo lực trở nên dễ dàng hơn.

Answer 2

Băm mật mã nhấn mạnh việc làm cho mọi người cố ý tạo ra một vụ va chạm khó khăn. Đối với một bảng băm, sự nhấn mạnh là bình thường trên việc tạo ra sự lây lan hợp lý các kết quả một cách nhanh chóng. Như vậy, cả hai thường khá khác nhau (đặc biệt, băm mật mã thường là số nhiều hơn chậm hơn).

Đối với hàm băm điển hình, kết quả chỉ bị giới hạn bởi loại - ví dụ: nếu nó trả về một size_t, thì hoàn toàn tốt đẹp nếu nó trả về bất kỳ kích thước nào có thể là. Bạn có thể giảm phạm vi đầu ra đó xuống kích thước bảng của bạn (ví dụ: sử dụng phần còn lại chia cho kích thước bảng của bạn, số này thường phải là số nguyên tố).

Như một ví dụ, một hàm băm bình thường khá điển hình có thể giống như thế:

// warning: untested code. 
size_t hash(char const *input) { 

    const int ret_size = 32; 
    size_t ret = 0x555555; 
    const int per_char = 7; 

    while (*input) { 
     ret ^= *input++; 
     ret = ((ret << per_char) | (ret >> (ret_size - per_char)); 
    } 
    return ret; 
} 

Ý tưởng cơ bản ở đây là phải có tất cả các bit của chuỗi đầu vào ảnh hưởng đến kết quả, và (càng nhanh càng tốt) có tất cả các bit của kết quả bị ảnh hưởng bởi ít nhất một phần của đầu vào. Lưu ý rằng tôi không đặc biệt đề xuất điều này như một hàm băm tuyệt vời - chỉ cố gắng minh họa một số khái niệm cơ bản về những gì bạn đang cố gắng thực hiện.

Answer 3

Mục tiêu thiết kế khác nhau. Ví dụ:

Với ví dụ cryptographic hash functions, bạn không thể sử dụng hàm băm và hàm băm để xác định dữ liệu gốc hoặc bất kỳ dữ liệu nào khác có thể tạo ra cùng một giá trị băm.

Hàm băm được sử dụng với bảng băm & cấu trúc dữ liệu khác không cần các thuộc tính bảo mật như vậy. Nó thường đủ nếu hàm băm nhanh và nó sẽ phân phối tập hợp đầu vào đồng đều vào tập hợp các băm có thể (để tránh sự phân cụm/va chạm không cần thiết).