Series Java những điều có thể bạn đã biết: Map/HashMap hoạt động như thế nào?

Đây là một câu hỏi thường gặp trong những buổi phỏng vấn ứng viên Java, và cũng có không ít bạn vì câu hỏi này mà gặp trắc trở, hôm nay chúng ta sẽ thảo luận về nó.

Đầu tiên, Map và HashMap là gì?

Map là một tập dữ liệu được lưu dưới dạng key-value. Một Map không thể chứa những key trùng nhau, nhưng mỗi key thì có thể được ánh xạ đến nhiều hơn một giá trị.

Map interface được định nghĩa gồm những method phục vụ những hoạt động  cơ bản (như put, get, remove, containsKey, containsValue, size, empty), phục vụ việc thao tác hàng loạt (như putAll, clear), và phục vụ việc xem dữ liệu trong tập (như keySet, entrySet, values).

HashMap là một implement của Map interface trong Java. HashMap không synchronize và không thread safe. Cách implement thì chắc các bạn đã quá rõ rồi, tôi sẽ không cần đưa ra ví dụ nữa.

HashMap hoạt đông dựa trên Hashing. Để hiểu được Hashing , chúng ta phải hiểu được các khái niệm về HashFunction, HashValue và Bucket.

Vậy, Hashing là gì?

Nào, cùng xét một mảng dữ liệu không được sắp xếp, làm sao để tìm kiếm trên mảng đó?

Tất nhiên, để tìm kiếm chúng ta phải thực hiện việc so sánh tất cả các phần tử của mảng. Vậy độ phức tạp sẽ là O(n).

Nếu mảng đó được sắp xếp, áp dụng tìm kiếm nhị phân thì độ phức tạp sẽ giảm xuống còn O(log n).

Ngoài ra, việc tìm kiếm còn có thể nhanh hơn nếu như hàm chỉ trả về một index của phần tử trong mảng. Trong trường hợp này, độ phức tạp chỉ còn là O(1). Đó chính là Hash Function.

Hash function là một hàm mà khi đưa vào một giá trị bất kì, nó sẽ trả về một giá trị tương ứng gọi là Hash Value.

Java cung cấp một hash function đó chính là hashCode(). Hàm này được implement trong class Object và đương nhiên tất cả các class trong Java đều có vì chúng đều thừa kế từ Object.

Như đã nói ở trên, để hiểu về Hashing, chúng ta phải hiểu về HashFunction, HashValue và Bucket. Giờ đã có hai, vậy Bucket là gì?

Bucket là khái niệm dùng để chỉ nơi mà chúng ta lưu trữ những cặp key-value. Trong HashMap, Bucket sử dụng một LinkedList để lưu trữ.

Trong Java HashMap được implement như thế nào?

Trong HashMap, hàm get(Object key) gọi hàm hashCode() của key để lấy hashValue của key, sau đó mang hashValue này để tìm bucket tương ứng, nơi mà key-value đang được lưu như là một Entry object. Ngó qua implement ta thấy như sau.

Hàm get(Object key) cũng kiểm tra xem key có null hay không. Null cũng được coi là một key trong HashMap, và dĩ nhiên chỉ có một key null. Nếu key là null thì hash luôn luôn là 0 và tương ứng index cũng là 0. Nếu key không phải là null thì gọi hash function tương ứng với key.

Kế tiếp, hashValue được dùng để tìm bucket tương ứng nơi mà Entry đang được lưu. Entry được lưu trữ trong bucket với hash, key, value và bucket index. Cuối cùng là trả về giá trị tương ứng với key.

Lưu ý nho nhỏ, độ phức tạp của hàm get() và put() trong HashMap là O(1) vì nó sử dụng hashCode để tìm giá trị.

Và bây giờ tôi chắc chắn  rằng các bạn đang thắc mắc, hash thì cũng chỉ là một con số, khả năng trùng nhau là có, vậy Làm thế nào nếu nhiều key có cùng một hashValue?

Đây là lý do mà việc implement hàm equals() chung với hashCode() trở nên cực kì quan trọng.

Như đã nói ở trên, một bucket là một LinkedList, nó không phải là java.util.Linkedlist nên các bạn đừng hiểu nhầm. HashMap có implementation riêng cho việc này. Do đó, nếu một hashValue chỉ đến một bucket chứa nhiều Entry nó sẽ duyệt LinkedList và so sánh các key của mỗi Entry bằng cách sử dụng key.equals() cho đến khi equals() trả về true. Sau đó giá trị tương ứng với key sẽ được trả về.

Tất cả các class đều có thể là key nếu nó được override hàm equals() và hashCode(), ngoài ra việc này cũng giúp biến các class trở thành immutable class.

Nói về performance.

Để nói về performance, đối với một HashMap có hai yếu tố sẽ ảnh hưởng trực tiếp tới performance đó là initial capacity (kích thước khởi tạo) và load factor (hệ số tải).

Capacity là con số nói về số lượng bucket trong HashMap.

Load factor là chỉ số để đo đếm việc đến ngưỡng nào đó thì capacity của HashMap sẽ được tự đông tăng lên. Khi số lương entry trong HashMap đạt đến ngưỡng vượt quá load factor cũng như capacity thì HashMap sẽ được rehash. Sau đó HashMap sẽ tăng số lượng bucket lên gấp đôi. Giá trị mặc định của load factor là 0.75.

Nói tóm lại.

Hy vọng qua bài viết này các bạn đã hiểu về các hoạt động của HashMap trong Java, và không bị lúng túng trong những lần phỏng vấn bị hỏi về vấn đề này nữa.

Chào tạm biệt và hẹn gặp lại các bạn trong những bài viết tới.