Trong bài viết này, chúng ta sẽ tìm hiểu sự khác biệt giữa HashMap và TreeMap trong Java.
HashMap
- Là hash table trong Java
- Cài đặt dựa trên Map interface
- Implements: Map, Cloneable, Serializable
- Cho phép 1 null key
- Cho phép nhiều null value
- Nhanh hơn TreeMap - O(1) cho get/put
- KHÔNG sắp xếp key → cho phép heterogeneous elements
- KHÔNG duy trì thứ tự elements
- Dùng khi KHÔNG cần key-value theo thứ tự sắp xếp
- Dùng equals() của Object để so sánh key (Map class override)
- Chỉ có method cơ bản: keySet(), get(), put()
TreeMap
- Là cấu trúc cây (tree structure) trong Java
- Cài đặt dựa trên Map interface
- Implements: NavigableMap, Cloneable, Serializable
- KHÔNG cho phép null key
- Cho phép nhiều null value
- Chỉ cho phép homogeneous key (vì được sắp xếp)
- Chậm hơn HashMap - O(log n) cho add/remove/contains
- Dùng Red-Black tree nội bộ (self-balancing BST)
- Dùng compareTo() để so sánh key
- Nhiều tính năng: tailMap(), firstKey(), lastKey(), pollFirstEntry(), pollLastEntry()
- Element sắp xếp ascending (natural order)
- Dùng KHI CẦN key-value theo thứ tự sắp xếp