Cách HashMap (Dictionary) hoạt động trong Java

Cách HashMap (Dictionary) hoạt động trong Java

HashMap (hay Dictionary) là một key-value data structure quan trọng. Các dev nhà ta chắc hẳn ai cũng đã từng dùng HashMap để giải quyết các bài toán hằng ngày rồi. Vậy liệu các bạn có đặt câu hỏi HashMap hoạt động như thế nào? Làm sao làm việc với HashMap lại nhanh? Đây cũng là câu hỏi thường xuyên được hỏi trong các buổi phỏng vấn Software Engineering

• HashMap hoạt động như thế nào? Bạn có thể tự xây dựng một HashMap cho riêng mình không?
• Hash Collision là gì? Làm sao để giải quyết Hash Collision?
• Những gì cần lưu ý khi sử dụng HashMap?

HashMap

HashMap là key-value data structure cho phép chúng ta lưu trữ data và chi phí cho các thao tác cơ bản (put, get, delete) chỉ là O(1).

HashMap hoạt động như thế nào?

HashMap hoạt động dựa trên nguyên lý hashing (Hashing principle). Khi chúng ta gọi hàm put(key, value) hay get(key) thì về cơ bản HashMap sẽ làm 2 bước sau

Tìm bucket

Bucket là nơi lưu trữ các key có hash gần như nhau, bucket được lưu trong một array nên chi phí truy xuất chỉ là O(1), Từ key, làm sao ta có thể tìm được index của bucket? Câu trả lời đơn giản là dùng giá trị hash của key và một công thức ánh xạ giá trị hash này với index trong array (index = hash % n chẳng hạn), thao tác này cũng tốn O(1) luôn.

Thao tác trên bucket:

Tìm xem key có thực sự tồn tại trong bucket hay không bằng hàm Equals(). Trong trường hợp có nhiều key có giá trị hash như nhau, thì một bucket có thể có nhiều item(key-value), việc của ta khi đó là duyệt qua bucket và kiểm tra xem có giá trị key trong bucket không.

Có thể thấy, tốc độ của HashMap không thực sự là O(1), trong trường hợp hàm hash tệ, dẫn đến tất cả các key-value đều nằm trong cùng 1 bucket. Tùy thuộc vào cấu trúc dữ liệu của bucket mà kết quả có thể khác nhau. Java 7 dùng Singlely Linked-List (O(n)), còn Java 8 sử dụng Red-Black Tree O(logn) để implement bucket.

Làm sao để xây dựng một HashMap?

Xây dựng một HashMap không quá phức tạp, bạn có thể đọc thêm source code của ngôn ngữ bạn đang sử dụng để hiểu thêm. Nhưng về cơ bản sẽ có những vẫn đề cơ bản sau.

• Bucket table: internal array chứa các bucket, array này có size xác định và sẽ được mở rộng khi số lượng phần tử trong HashMap đạt ngưỡng.
• Bucket: nơi lưu trữ các key-value có giá trị gần như nhau, bucket có thể là Linked-List hoặc Tree.
• put(key, value) và get(key): dùng dùng giá trị hash của key để tìm ra index của bucket, sau đó dùng equal để kiểm tra key có tồn tại trong bucket hay không.
• rehashing: Size của bucket table sẽ được mở rộng, các phần tử sẽ được rearrange lại khi số lượng phần tử của Hashmap đến một ngưỡng nào đó (load factor, trong Java, giá trị này bằng 0.75 * size).

Hash Collision là gì?

Hash Collision là trường hợp hàm hash implement tệ, dẫn đến nhiều key-value nằm trong cùng một bucket. Tùy thuộc vào implement của bucket mà chi phí có thế khác nhau.
Ngoài ra, khi số lượng item tăng lên, khả năng xảy ra hash collision cao hơn thì ta có thể tăng size của bucket table lên, rehashing lại toàn HashMap. Trong Java, default load factor = 0.75, điều này có nghĩa số lượng bucket luôn lớn hơn số lượng item, Developer của Java hy vọng rằng mỗi bucket chỉ có một item.

Những gì cần lưu ý khi sử dụng HashMap

HashCode và Equals: Khi implement Equals thì phải implement HashCode, 2 object bằng nhau thì hashcode cũng phải bằng nhau!
Ngoài ra, hàm hash cũng cần phải implement sao cho có thể phân tán key-value đều cho các bucket (Best practive các bạn có thể tham khảo cuốn Effective Java, Item 9)

Init capacity và rehashing: rehashing có chi phí lớn, hãy tính toán và khởi tạo HashMap với kích thước hợp lý.