Tất tần tật về HashMap trong java Phần 2
Map
10
HashMap
5
Java
215
White

Banh Mii viết ngày 11/05/2021

Ở phần trước, chúng ta đã tìm hiểu cấu trúc bên trong và cách khởi tạo HashMap, ở phần này mình tiếp tục đi sâu hơn về cách HashMap hoạt động nhé.
Link phần 1:
https://kipalog.com/posts/-Tat-tan-tat-ve-HashMap-trong-java--Phan-1

1. Hashing, hashCode() và equal() method

Chắc chắn rồi, để hiểu về HashMap, chúng ta phải nắm được Hashing. Hashing là gì, và nó liên quan gì đến HashMap.

Hashing là quá trình convert từ Object sang 1 số Integer bằng cách chạy hàm hashCode(). Mặc định, hashCode() method sẽ trả về giá trị là địa chỉ ô nhớ ( memory reference ) của Object. Trong HashMap, hashcode() method dùng để tính bucket và do đó dùng để tính index (hai khái niệm này mình sẽ nói kỹ hơn ở phần sau).

equal() method dùng để kiểm tra 2 objects có bằng nhau hay không. Hashmap sử dụng hàm equal để check key có bị trùng hay không.

2. Bucket và index trong Hashmap

Bucket là một element của Hashmap array. Ở phần trước mình đã nhắc đến khái niệm node, bucket sẽ chứa các node, một bucket có thể có một hoặc nhiều node, tùy thuộc vào hàm hashcode(), nếu bạn implement hàm hashcode() càng tốt, thì buckets trong Hashmap càng được tận dụng. Ở đây, Linklist stucture được dùng để liên kết các node.

Index trong Hashmap:

Hiểu nôm na thì index chính là cái số thứ tự của node nằm trong HashMap, index cũng được tính dựa trên hashcode.

Phần tiếp theo khi đi vào hoạt động về hàm put() trong HashMap mình sẽ show rõ hơn về bucket và index, cùng theo dõi nhé.

3. Put phần tử vào HashMap

Giả sử mình khởi tạo một HashMap:

                        HashMap map = new HashMap();

Ở bài trước mình đã giải thích, ở đây mình không truyền initial capanity nên map của mình hiện có size là 16:

alt text

Bây giờ mình tiến hành put một cặp key-value vào map:

                        map.put(new Key("banhmii"), 20);

Bên trong HashMap sẽ làm như sau:

  1. Tính Hashcode của key : "banhmii". Ví dụ hashcode return 118
  2. Tính index : ví dụ index = 6
  3. Tạo ra một node với các giá trị: { int hash = 118, Key key = "banhmii", Integer value = 20, Node next = null }
  4. Đặt node này tại vị trí index = 6. Done

Tiếp tục mình put một cặp key-value khác vào HashMap:

                        map.put(new Key("anotherKey"), 30);

Tương tự, HashMap thực hiện các bước như sau:

  1. Tính Hashcode của key: "anotherKey", ví dụ Hashcode return 115.
  2. Tính index, return 3.
  3. Tạo ra môt node Object với các giá trị:
    {
    int hash = 115
    Key key = {"anotherKey"}
    Integer value = 30
    Node next = null
    }

  4. Đặt node này tại vị trí index = 3.

Như vậy, các bạn có thể thấy mặc dù được insert vào sau nhưng element này lại có index đứng trước cặp "banhmii-20". Đó là lý do vì sao chúng ta kết luận HashMap không đảm bảo thứ tự các phần tử.

Trường hợp đặc biệt: Hai key khác nhau nhưng trả về hashcode giống nhau. (collision)

                    map.put(new Key("collision"), 40);

Các bước:

  1. Tính hashcode của key: "collision", return 118
  2. Tính index, return 6 (giống với phần tử đầu tiên)
  3. Tạo ra một node Object với các giá trị:
    {
    int hash = 118
    Key key = {"collision"}
    Integer value = 40
    Node next = null
    }

  4. Vị trí này đã có một element khác, nên trường hợp này HashMap cần làm thêm một số steps:
    4.1. Check cả hai hàm equal và hashcode, nếu cả hai đều trả về true => thay thế phần tử cũ trước đó bằng phần tử hiện tại.
    4.2. Ở trường hợp này, do hai key không giống nhau nên equal trả về false, do vậy HashMap sẽ NỐI node object này với node object trước bằng linklist.

alt text

4. Get phần tử trong HashMap

Bây giờ, hãy thử lấy một phần tử trong map mình vừa tạo nhé:

                        map.get(new Key("anotherKey"));

Các bước thực hiện:

  1. Tính hashcode của key "anotherKey", return 115
  2. Tính index, return 3
  3. Đến vị trí index = 3 và so sánh given key (key mà mình đưa vào trong hàm get()) với key của element đầu tiên (ở trường hợp này chỉ có một element)
  4. Kiểm tra kết quả là giống nhau nên sẽ return value là 30. Done.

Giờ mình sẽ thử lấy với key khác: "collision"

                        map.get(new Key("collision"));

Các steps:

  1. Tính hashcode của key :"collision", return 118
  2. Tính index, return 6
  3. Đến vị trí index = 6 và so sánh given key với key của element đầu tiên (element đầu tiên ở vị trí này là cặp "banhmii-20")
  4. Do equal trả về false khi so sánh 2 key nên HashMap tiếp tục kiểm tra xem có next node hay không.
  5. Có next node nên HashMap check tiếp given key với cặp thứ 2 ở vị trí index = 6 là "collision-40".
  6. Equal trả về true nên đây là phần tử cần tìm, return value = 40.

Trên đây là tổng hợp về hoạt động của HashMap cũng như cách nó lưu trữ các phần tử.
Bài viết hơi dài nhỉ ^^.
Cảm ơn cac bạn đã đọc bài. Nếu có bổ sung hay thắc mắc gì hay comment phía dưới nhé. Cảm ơn các bạn.

Nguồn tham khảo:
https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

BanhMii 30-04-20210

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Banh Mii

4 bài viết.
16 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
5 0
Spring security là 1 framework thuộc hệ thống Spring, dành riêng cho việc thiết lập bảo mật của ứng dụng bao gồm authentication và authorization. M...
Banh Mii viết 2 tháng trước
5 0
White
3 0
Hiện nay, phần lớn các project đều dùng Git để quản lý, với các thao tác thông thường như pull, push, merge thì có lẽ đã quá quen thuộc với các bạn...
Banh Mii viết 2 tháng trước
3 0
White
2 0
HashMap được coi là một trong những Java Collection phổ biến nhất, và cũng thường xuyên góp mặt trong list các câu hỏi phỏng vấn. Vậy bạn đã bao g...
Banh Mii viết 3 tháng trước
2 0
Bài viết liên quan
White
18 8
Đâ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ẽ...
Hoàng Nguyễn viết hơn 5 năm trước
18 8
White
11 0
(Ảnh) Hồi đó tôi mới 12, năm cuối cấp thi đại học đến đít rồi còn bày đặt viết ứng dụng bản đồ. Giờ nghĩ lại thì vẫn thấy đó là ứng dụng tôi tự hà...
Nghiêm Tiến Viễn viết 1 năm trước
11 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
4 bài viết.
16 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!