Nếu là một lập trình viên PHP, bạn đã bao giờ tự hỏi sao Array của PHP lại khác các ngôn ngữ khác như thế? Sao Array của PHP lại hỗ trợ key dạng string.
Ví dụ $a['test'] = 'Hello Hashtables';
Tương tự, trong Java ta dùng java.util.HashMap, trong Python ta dùng Dictionary
Điểm chung của cả 3 là được implement bởi Hashtable.
Hashtable là một cấu trúc dữ liệu được sử dụng rộng rãi trong các ứng dụng và cả các ngôn ngữ lập trình.
Để “nhét” key (dạng string) vào trong 1 mảng người ta dùng 1 hash function chuyển key thành số và đưa vào trong mảng.
Ví dụ: Hash(‘test’) = 1231; a[1231] = 'Hello Hashtables';
Giờ thì dễ hiểu hơn rồi nhỉ!
Ok bây giờ chúng ta sẽ tìm hiểu cách người ta implement hashtables nhé!
Đầu tiên sẽ có 2 vấn đề chúng ta cần xử lý:
- Tính toán hash function
- Khi hash ra trùng key thì xử lý thế nào?
Hash function
Hash function giúp chúng ta chuyển key thành index của mảng, một hàm hash function càng đỡ gây ra sự trùng lặp thì càng tốt. Tuỳ từng bài toán ta sẽ có phương pháp hash khác nhau.
Ví dụ: trong 1 lớp học có 50 học sinh, ta dùng số điện thoại của họ làm key lưu trữ thông tin, thật tồi tệ nếu bạn dùng 3 số đầu (097, 098 …) để hash.
Trong 1 mảng có M phần tử, hash function phải đảm bảo cho index rơi vào [0, M – 1].
Dưới đây là code implement từng kiểu dữ liệu của Java
Như vậy chúng ta đã nắm được tư tưởng của hash function, lần tới chúng ta sẽ nói về cách xử lý khi hash function cho ra 1 kết quả với 2 giá trị khác nhau.
(hình ảnh trên bài viết được lấy từ slide khoá học algorithm trên coursera)
(3 lượt thả tim)
Loading...
