Chủ đề này có 5 trả lời

[duchao]

Hien tôi đang tìm hiểu về hàm băm, có ai biết về vấn đề này hay có tài liệu về nó có thể giúp đỡ tôi không? Tôi không phải là dân tóan chính gốc vì vậy mong các bạn giúp đỡ. Xin cảm ơn nhiều!!!

[Duong_Qua]

Hỏi bạn là hahs function hay là hash function? Nếu là hash function thì bạn cần hỏi về mục gì thế ? (k-universal hash function, pseudogenerator,....)

[koreagerman]

Hien tôi đang tìm hiểu về hàm băm, có ai biết về vấn đề này hay có tài liệu về nó có thể giúp đỡ tôi không? Tôi không phải là dân tóan chính gốc vì vậy mong các bạn giúp đỡ. Xin cảm ơn nhiều!!!

Hàm băm, bảng băm là mấy khái niệm đề cập đến ở môn "Cấu trúc dữ liệu và Thuật giải". Bạn có thể tìm đọc các cuốn giáo trình về môn này.

[vuhung]

[quote name='koreagerman' date='Jan 25 2005, 02:22 PM'][quote name='duchao' date='Jan 24 2005, 09:42 PM']
Hàm băm, bảng băm là mấy khái niệm đề cập đến ở môn "Cấu trúc dữ liệu và Thuật giải". Bạn có thể tìm đọc các cuốn giáo trình về môn này.[/quote]
Hàm băm. Nghe chuối nhỉ, tiếng Anh nó là cái gì thế hả các bạn?

[Duong_Qua]

Nó là hash function, hash table. Ngoài sử dụng trong các ngôn ngữ lập trình, một ứng dụng đang được khá nhiều quan tâm hiện nay của hash function, hash table là data stream, khi mà bạn phải thiết lập 1 hash function/hashtable từ [n] -> [k] thỏa mãn 1 số tính chất nhất định (về probability) nào đấy .

[thanhluan001]

Mình mới học về hàm này, có gì anh em chỉ bảo thêm với.
Hash function ra đời vì thuật toán tìm kiếm là thuật toán tốn nhiều thời gian nhất. Ý tưởng kiếm một object trong 1 list rất dài dẫn tới vài thuật toán thú vị.

Thuật toán dễ nhất là vét cạn. Bạn chỉ phải duyệt danh sách từ đầu đến cuối, khi gặp phải object cần tìm thì dừng. Dễ thấy, thuật toán sẽ không hiệu quả với 1 danh sách dài va trường hợp xấu nhất sẽ phải duyệt qua tất cả các object. O(n)

Thứ 2 là thuật toán Chia để trị, hiệu quả hơn nhưng chỉ áp dụng cho danh sách đã được sắp xếp. Bắt đầu từ giữa danh sách, so sánh, nếu nhỏ hơn vật cần tìm thì tiếp tục nửa trên, else tiếp tục nửa dưới. Tiếp tục chia 2 nửa. Trường hợp xấu nhất là O (log 2 (n))

Hash function thì chỉ cần một lần gọi đến. Không có thuật toán tổng quát, tùy trường hợp bạn phải áp dụng cách khác nhau. Ví dụ như bạn muốn lưu lại điểm của 100 người.

Người thứ 1: 10
Người thứ 2: 19
Người thứ 3: 13
Người thứ 4: 12

Bạn có thể lưu vào mảng { {1,10} , {2,19}, {3,13}, {4,12} }. Rồi dùng vét cạn duyệt.

Hoặc, dùng bạn dùng mảng a với hàng như là mục lục. Vd: a[1] cho ngưòi thứ 1...Tổng quát, a[i] cho người thứ i. Hiệu quả thuật toán là hằng số.