Link nội dung bài viết gốc: https://gpcoder.com/2645-hashmap-trong-java-hoat-dong-nhu-the-nao/

Bạn Đang Xem: HashMap trong Java hoạt động như thế nào?

HashMap lưu trữ tài liệu ở dạng các cặp key-value (khóa-giá trị). Mỗi cặp key-value được lưu trữ trong một đối tượng người dùng của lớp Entryvàlt;K, Vvàgt;. Lớp học bên trong này còn có bốn trường: key (khóa), value (giá trị), next (thành phần kế tiếp) và hash (giá trị băm).

• key: lưu khóa của một thành phần và giá trị khóa này là final.
• value: lưu giá trị của thành phần.
• next: lưu giữ con trỏ tới cặp khóa-giá trị tiếp theo. Tính chất này làm cho những cặp khóa-giá trị được lưu trữ dưới dạng một list liên kết.
• hash: lưu giữ mã băm (hashcode) của khóa.

Lớp HashMap trong Java sử dụng một hashtable để tùy chỉnh (implements) Map Interface. Cấu trúc lưu trữ bên trong của HashMap như sau:

Hình ảnh trên cho thấy cách HashMap lưu trữ các thành phần của nó. Bên trong HashMap sử dụng một mảng Entryvàlt;K, Vvàgt; được gọi là table[] để lưu trữ các cặp khóa-giá trị.

HashMap không chèn các đối tượng người dùng khi chúng ta đặt (put) chúng vào thành phần HashMap ngay. Thay vào đó, nó sử dụng mã băm (hashcode) của khóa để quyết định chỉ mục (index) cho cặp giá trị-cặp cụ thể. Nó được gọi là Hashing.

Toàn bộ cấu trúc tài liệu HashMap dựa trên nguyên tắc Hashing. Hashing là chức năng hoặc thuật toán hoặc phương pháp mà khi vận dụng cho bất kỳ đối tượng người dùng / biến trả về một giá trị số nguyên duy nhất đại diện thay mặt nhận định rằng đối tượng người dùng / biến. Giá trị số nguyên duy nhất này được gọi là mã băm (hash code).

Hàm Hash được gọi là tốt nếu nó trả về cùng một mã băm mỗi lúc nó được gọi trên cùng một đối tượng người dùng. Hai đối tượng người dùng có thể có cùng một mã băm (hash code).

Bất kỳ khi nào bạn chèn cặp khóa-giá trị mới bằng phương pháp sử dụng phương thức put(), HashMap không chèn tức thời vào table[]. Thay vào đó, nó sẽ gọi hàm băm trên khoá (key). HashMap có hàm băm riêng để tính toán mã băm của khoá (key).

Phương thức hashCode() và equals()

HashMap sử dụng phương thức hashCode và equals để thêm vào (put) và lấy lại (get) phần từ một tập hợp tương ứng. Khi hàm put() đuợc gọi, HashMap tính toán giá trị hash (giá trị băm) của khoá và lưu trữ cặp giá trị (key-value) đuợc đánh chỉ mục (index) thích hợp vào tập hợp. Nếu khoá đã tồn tại, giá trị của nó đuợc update (update) bằng giá trị mới.

Nếu 2 hàm này sẽ không đuợc tùy chỉnh (implement) xác thực, như 2 khoá khác nhau lại cho ra hash code (giá trị đã băm) giống nhau và vì vậy chúng sẽ đuợc xem như thể bằng nhau trong tập hợp. Hai hàm này còn sử dụng để phát hiện trùng lặp. Nên việc tùy chỉnh 2 hàm là yếu tốt then chốt để kiểm tra tính đúng đắn của HashMap.

Trong tương lai là cách thực hiện mã của phương thức put() trong lớp HashMap:

Hãy xem đoạn mã này hoạt động ra sao:

Bước 1: Kiểm tra trước tiên liệu khóa có mức giá trị hay là không. Nếu khóa là null, nó gọi phương thức putForNullKey(). table[0] luôn luôn luôn được dành riêng cho khóa rỗng. Bởi vì, mã băm của null là 0.

Bước 2: Nếu khóa không phải là null, thì nó sẽ tính toán mã băm (hash code) của khóa bằng phương pháp gọi phương thức hash().

Bước 3: Gọi lệnh indexFor() bằng phương pháp truyền mã băm được tính trong bước 2 và chiều dài của mảng table[]. Phương thức này trả về chỉ mục trong mảng table[] cho cặp cặp khóa-giá trị được chỉ định.

Bước 4: Sau khoản thời gian nhận được chỉ mục, nó sẽ kiểm tra tất cả những khóa có trong list liên kết (linked list) tại chỉ mục đó. Nếu khóa đã có trong list liên kết, nó sẽ thay thế giá trị cũ bằng giá trị mới.

Bước 5: Nếu khoá không có trong list được liên kết, nó sẽ nối thêm cặp khóa-giá trị được xác định ở cuối list liên kết.

Xem Thêm : Lục căn, Lục trần và Lục thức là gì

Trong tương lai là cách thực hiện mã của phương thức get() trong lớp HashMap:

Hãy xem đoạn mã này hoạt động ra sao:

Bước 1: Kiểm tra trước tiên liệu khóa có mức giá trị hay là không. Nếu khóa là null, nó gọi phương thức getForNullKey().

Bước 2: Nếu khóa không phải là null, mã băm (hash code) của khoá được chỉ định sẽ tiến hành tính.

Bước 3: indexFor() phương pháp được sử dụng để tìm ra các chỉ số của nhiều khóa quy định trong mảng table[].

Bước 4: Sau khoản thời gian nhận được chỉ mục, nó sẽ lặp mặc dù list liên kết (linked list) ở vị trí đó và kiểm tra phương pháp sử dụng bằng phương thức equals(). Nếu tìm thấy khóa, nó trả về giá trị liên kết với nó. nếu không trả về null.

Kết quả thực thi Khóa học trên:

hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118

hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Giảng giải hoạt động của Khóa học trên:

line 1: Khởi tạo hashMap rỗng: bảng tính hashmap được kích thước là 16

Mapvàlt;Key, Integervàgt; map = new HashMapvàlt;>(); // line 1

line 2: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị ở trên HashMap

map.put(new Key(“vishal”), 20); // line 2

Các bước:

• Tính mã băm (hash code) của khóa {“vishal”}. Nó sẽ tiến hành tạo ra là 118.
• Tính chỉ số (index) bằng phương pháp sử dụng phương pháp chỉ số sẽ là 6.

Tạo một đối tượng người dùng node như sau:

{ int hash = 118 Key key = {“vishal”} Integer value = 20 Node next = null }

Đặt đối tượng người dùng này ở chỉ số 6, nếu không có đối tượng người dùng nào khác được trình bày ở đó. Hiện tại HashMap trở thành:

line 3: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị khác ở trên HashMap

Xem Thêm : Lớp học online kết hợp offline là gì? Thiết bị cần thiết để triển khai

map.put(new Key(“sachin”), 30); // line 3

Các bước:

Tính mã băm (hash code) của khóa {“sachin”}. Nó sẽ tiến hành tạo ra là 115. Tính chỉ số (index) bằng phương pháp sử dụng phương pháp chỉ số sẽ là 3. Tạo một đối tượng người dùng node như sau:

{ int hash = 115 Key key = {“sachin”} Integer value = 30 Node next = null }

Đặt đối tượng người dùng này ở chỉ số 3, nếu không có đối tượng người dùng nào khác được trình bày ở đó. Hiện tại HashMap trở thành:

line 4: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị khác ở trên HashMap

map.put(new Key(“vaibhav”), 40); // line 4

Các bước:

• Tính mã băm (hash code) của khóa {“vaibhav”}. Nó sẽ tiến hành tạo ra là 118.
• Tính chỉ số (index) bằng phương pháp sử dụng phương pháp chỉ số sẽ là 6. Tạo một đối tượng người dùng node như sau:

{ int hash = 118 Key key = {“vaibhav”} Integer value = 40 Node next = null }

Đặt đối tượng người dùng này ở chỉ số 6, nếu không có đối tượng người dùng nào khác được đặt tại đó. Trong trường hợp này, một đối tượng người dùng nút được tìm thấy tại chỉ số 6. Do đó, cần kiểm tra qua phương thức hashCode() và equals() nếu cả hai khóa đều giống nhau. Nếu các khóa (key) giống nhau, hãy thay giá trị (value) bằng giá trị ngày nay. Nếu không thì thêm thành phần vào thời gian cuối list liên kết (linked list) và cả hai đều được lưu trữ tại chỉ mục 6.

Hiện tại HashMap trở thành:

line 5:Tìm tài liệu cho key “sachin”:

map.get(new Key(“sachin”); // line 5

Các bước:

• Tính mã băm (hashcode) của Key {“sachin”}. Nó sẽ tiến hành tạo ra là 115.
• Tính chỉ số (index) bằng phương pháp sử dụng phương thức index sẽ là 3.
• Đi tới chỉ số 3 của mảng và so sánh thành phần của thành phần trước tiên với khóa đã cho. Nếu cả hai đều bằng (equal) thì trả lại giá trị, nếu không thì kiểm tra các thành phần tiếp theo nếu có.
• Trong trường hợp này, nó được tìm thấy như thể thành phần trước tiên và giá trị trả về là 30.

line 6: Tìm tài liệu cho key “sachin”:

map.get(new Key(“vaibhav”); // line 6

Các bước:

• Tính mã băm (hashcode) của Key {“vaibhav”}. Nó sẽ tiến hành tạo ra là 118.
• Tính chỉ số (index) bằng phương pháp sử dụng phương thức index sẽ là 6.
• Đi tới chỉ số 6 của mảng và so sánh thành phần của thành phần trước tiên với khóa đã cho. Nếu cả hai đều bằng (equal) thì trả lại giá trị, nếu không thì kiểm tra các thành phần tiếp theo nếu có.
• Trong trường hợp này, nó được tìm thấy ở thành phần trước tiên và giá trị trả về là 30.
• Trong trường hợp này, nó không được tìm thấy ở thành phần trước tiên và giá trị tiếp theo của đối tượng người dùng nút (node) không phải là null.
  • Nếu tiếp theo của nút (node) thì trả về null.
  • Nếu nút (node) kế tiếp không phải là null thì đi qua thành phần thứ hai và tái diễn bước 3 cho tới khi không tìm thấy khóa hoặc tiếp theo không phải là null.

Nguồn: https://gpcoder.com/2645-hashmap-trong-java-hoat-dong-nhu-the-nao/