GP Coder

Trang chia sẻ kiến thức lập trình Java

  • Java Core
    • Basic Java
    • OOP
    • Exception Handling
    • Multi-Thread
    • Java I/O
    • Networking
    • Reflection
    • Collection
    • Java 8
  • Design pattern
    • Creational Pattern
    • Structuaral Pattern
    • Behavior Pattern
  • Web Service
    • SOAP
    • REST
  • JPA
  • Java library
    • Report
    • Json
    • Unit Test
  • Message Queue
    • ActiveMQ
    • RabbitMQ
  • All
Trang chủ Java Core Collection HashMap trong Java hoạt động như thế nào?

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

Đăng vào 17/11/2017 . Được đăng bởi GP Coder . 12265 Lượt xem . Toàn màn hình

Nội dung

  • 1 Cấu trúc dữ liệu bên trong HashMap
  • 2 Hashing là gì?
  • 3 Phương thức hashCode() và equals()
  • 4 Phương thức put() hoạt động như thế nào?
  • 5 Phương thức get() hoạt động như thế nào?
  • 6 Ví dụ hoạt động của HashMap

Cấu trúc dữ liệu bên trong HashMap

HashMap lưu trữ dữ 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 của lớp Entry<K, V>. Bên trong class này có bốn trường: key (khóa), value (giá trị), next (phần tử kế tiếp) và hash (giá trị băm).

  • key: lưu khóa của một phần tử và giá trị khóa này là final.
  • value: lưu giá trị của phần tử.
  • next: lưu giữ con trỏ tới cặp khóa-giá trị tiếp theo. Thuộc tính này làm cho các cặp khóa-giá trị được lưu trữ dưới dạng một danh sách liên kết.
  • hash: lưu giữ mã băm (hashcode) của khóa.
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Lớp HashMap trong Java sử dụng một hashtable để cài đặt (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 phần tử của nó. Bên trong HashMap sử dụng một mảng Entry<K, V> đượ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 khi bạn đặt (put) chúng vào phần tử 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.

Hashing là gì?

Toàn bộ cấu trúc dữ 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 áp dụng cho bất kỳ đối tượng / biến trả về một giá trị số nguyên duy nhất đại diện cho rằng đối tượ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 khi nó được gọi trên cùng một đối tượng. Hai đối tượng có thể có cùng một mã băm (hash code).

Bất cứ khi nào bạn chèn cặp khóa-giá trị mới bằng cách sử dụng phương thức put(), HashMap không chèn lập tức 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 cập nhật (update) bằng giá trị mới.

Nếu 2 hàm này không đuợc cài đặt (implement) chính xá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ư là 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 cài đặt 2 hàm là yếu tốt then chốt để kiểm tra tính đúng đắn của HashMap.

Phương thức put() hoạt động như thế nào?

Dưới đây là cách thực hiện mã của phương thức put() trong lớp HashMap:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Hãy xem đoạn mã này hoạt động như thế nào:

Bước 1: Kiểm tra đầu tiên liệu khóa có giá trị hay không. Nếu khóa là null, nó gọi phương thức putForNullKey(). table[0] 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 cách gọi phương thức hash().

Bước 3: Gọi lệnh indexFor() bằng cách 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 khi nhận được chỉ mục, nó sẽ kiểm tra tất cả các khóa có trong danh sách liên kết (linked list) tại chỉ mục đó. Nếu khóa đã có trong danh sách 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 danh sách được liên kết, nó sẽ nối thêm cặp khóa-giá trị được xác định ở cuối danh sách liên kết.

Phương thức get() hoạt động như thế nào?

Dưới đây là cách thực hiện mã của phương thức get() trong lớp HashMap:

public V get(Object key) {
    if (key == null)
    return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

Hãy xem đoạn mã này hoạt động như thế nào:

Bước 1: Kiểm tra đầu tiên liệu khóa có giá trị hay 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ẽ được tính.

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

Bước 4: Sau khi nhận được chỉ mục, nó sẽ lặp mặc dù danh sách 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.

Ví dụ hoạt động của HashMap

package com.gpcoder.collection.map;
 
import java.util.HashMap;
import java.util.Map;
 
/**
 * Java program to illustrate internal working of HashMap
 */
class Key {
    String key;
 
    Key(String key) {
        this.key = key;
    }
 
    @Override
    public int hashCode() {
        int hash = (int) key.charAt(0);
        System.out.println("hashCode for key: " + key + " = " + hash);
        return hash;
    }
 
    @Override
    public boolean equals(Object obj) {
        return key.equals(((Key) obj).key);
    }
}
 
public class HashMapInternalWorking {
    public static void main(String[] args) {
        Map<Key, Integer> map = new HashMap<>();    // line 1
        map.put(new Key("vishal"), 20);         // line 2
        map.put(new Key("sachin"), 30);         // line 3
        map.put(new Key("vaibhav"), 40);        // line 4
 
        System.out.println();
        System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); // line 5
        System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); // line 6
    }
}

Kết quả thực thi chương trình 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ải thích hoạt động của chương trình trên:

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

Map<Key, Integer> map = new HashMap<>(); // 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ẽ được tạo ra là 118.
  • Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 6.
  • Tạo một đối tượng node như sau:

{

int hash = 118

Key key = {“vishal”}

Integer value = 20

Node next = null

}

  • Đặt đối tượng này ở chỉ số 6, nếu không có đối tượng nào khác được trình bày ở đó.

Bây giờ 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

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ẽ được tạo ra là 115.
  • Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 3.
  • Tạo một đối tượng node như sau:

{

int hash = 115

Key key = {“sachin”}

Integer value = 30

Node next = null

}

  • Đặt đối tượng này ở chỉ số 3, nếu không có đối tượng nào khác được trình bày ở đó.

Bây giờ 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ẽ được tạo ra là 118.
  • Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 6.
  • Tạo một đối tượng node như sau:

{

int hash = 118

Key key = {“vaibhav”}

Integer value = 40

Node next = null

}

  • Đặt đối tượng này ở chỉ số 6, nếu không có đối tượng nào khác được đặt ở đó.
  • Trong trường hợp này, một đối tượ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ị hiện tại.
    • Nếu không thì thêm phần tử vào cuối danh sách liên kết (linked list) và cả hai đều được lưu trữ tại chỉ mục 6.

Bây giờ HashMap trở thành:

line 5:Tìm dữ liệu cho key “sachin”:

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

Các bước:

  1. Tính mã băm (hashcode) của Key {“sachin”}. Nó sẽ được tạo ra là 115.
  2. Tính chỉ số (index) bằng cách sử dụng phương thức index sẽ là 3.
  3. Đi tới chỉ số 3 của mảng và so sánh phần tử của phần tử đầu 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 phần tử tiếp theo nếu có.
  4. Trong trường hợp này, nó được tìm thấy như là phần tử đầu tiên và giá trị trả về là 30.

line 6:Tìm dữ liệu cho key “sachin”:

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

Các bước:

  1. Tính mã băm (hashcode) của Key {“vaibhav”}. Nó sẽ được tạo ra là 118.
  2. Tính chỉ số (index) bằng cách sử dụng phương thức index sẽ là 6.
  3. Đi tới chỉ số 6 của mảng và so sánh phần tử của phần tử đầu 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 phần tử tiếp theo nếu có.
  4. Trong trường hợp này, nó không được tìm thấy ở phần tử đầu tiên và giá trị tiếp theo của đối tượ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 phần tử thứ hai và lặp lại bước 3 cho đến khi không tìm thấy khóa hoặc tiếp theo không phải là null.

Tài liệu tham khảo:

  • http://javaconceptoftheday.com/how-hashmap-works-internally-in-java/
  • http://www.geeksforgeeks.org/internal-working-of-hashmap-java/
5.0
21
Nếu bạn thấy hay thì hãy chia sẻ bài viết cho mọi người nhé! Và Donate tác giả

Shares

Chuyên mục: Collection Được gắn thẻ: Collection, How to

Lớp HashMap trong Java
Lớp LinkedHashMap trong Java

Có thể bạn muốn xem:

  • Loại bỏ các phần tử trùng trong một ArrayList như thế nào? (28/11/2017)
  • So sánh HashMap và Hashtable trong Java (20/11/2017)
  • Lớp Collections trong Java (Collections Utility Class) (25/11/2017)
  • Queue và PriorityQueue trong Java (22/11/2017)
  • Chuyển đổi Array sang ArrayList và ngược lại (30/11/2017)

Bình luận

bình luận

Tìm kiếm

Bài viết mới

  • Clean code 13/01/2024
  • Giới thiệu CloudAMQP – Một RabbitMQ server trên Cloud 02/10/2020
  • Kết nối RabbitMQ sử dụng Web STOMP Plugin 19/06/2020
  • Sử dụng publisher confirm trong RabbitMQ 16/06/2020
  • Sử dụng Dead Letter Exchange trong RabbitMQ 13/06/2020

Xem nhiều

  • Hướng dẫn Java Design Pattern – Factory Method (97351 lượt xem)
  • Hướng dẫn Java Design Pattern – Singleton (96987 lượt xem)
  • Giới thiệu Design Patterns (86649 lượt xem)
  • Lập trình đa luồng trong Java (Java Multi-threading) (85488 lượt xem)
  • Giới thiệu về Stream API trong Java 8 (83026 lượt xem)

Nội dung bài viết

  • 1 Cấu trúc dữ liệu bên trong HashMap
  • 2 Hashing là gì?
  • 3 Phương thức hashCode() và equals()
  • 4 Phương thức put() hoạt động như thế nào?
  • 5 Phương thức get() hoạt động như thế nào?
  • 6 Ví dụ hoạt động của HashMap

Lưu trữ

Thẻ đánh dấu

Annotation Authentication Basic Java Behavior Pattern Collection Creational Design Pattern Cấu trúc điều khiển Database Dependency Injection Design pattern Eclipse Exception Executor Service Google Guice Gson Hibernate How to Interceptor IO Jackson Java 8 Java Core JDBC JDK Jersey JMS JPA json JUnit JWT Message Queue Mockito Multithreading OOP PowerMockito RabbitMQ Reflection Report REST SOAP Structuaral Pattern Swagger Thread Pool Unit Test Webservice

Liên kết

  • Clean Code
  • JavaTpoint
  • Refactoring Guru
  • Source Making
  • TutorialsPoint
  • W3Schools Online Web Tutorials

Giới thiệu

GP Coder là trang web cá nhân, được thành lập với mục đích lưu trữ, chia sẽ kiến thức đã học và làm việc của tôi. Các bài viết trên trang này chủ yếu về ngôn ngữ Java và các công nghệ có liên quan đến Java như: Spring, JSF, Web Services, Unit Test, Hibernate, SQL, ...
Hi vọng góp được chút ít công sức cho sự phát triển cộng đồng Coder Việt.

Donate tác giả

Tìm kiếm các bài viết của GP Coder với Google Search

Liên hệ

Các bạn có thể liên hệ với tôi thông qua:
  • Trang liên hệ
  • Linkedin: gpcoder
  • Email: contact@gpcoder.com
  • Skype: ptgiang56it

Follow me

Copyright 2025 © GP Coder · All Rights Reserved · Giới thiệu · Chính sách · Điều khoản · Liên hệ ·

Share

Blogger
Delicious
Digg
Email
Facebook
Facebook messenger
Flipboard
Google
Hacker News
Line
LinkedIn
Mastodon
Mix
Odnoklassniki
PDF
Pinterest
Pocket
Print
Reddit
Renren
Short link
SMS
Skype
Telegram
Tumblr
Twitter
VKontakte
wechat
Weibo
WhatsApp
X
Xing
Yahoo! Mail

Copy short link

Copy link