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

Hầu hết các bạn sẽ đồng ý rằng HashMapngày nay, đây là chủ đề được thảo luận nhiều nhất trong các cuộc phỏng vấn. Đôi khi tôi có những cuộc thảo luận tương tự với đồng nghiệp của mình và điều đó thực sự có ích. Bây giờ tôi sẽ có một cuộc thảo luận như vậy với bạn. Tôi cho rằng nếu bạn quan tâm đến nội dung và hoạt động của HashMap thì bạn đã quen với những điều cơ bản của HashMap , vì vậy tôi sẽ bỏ qua phần đó. Nhưng nếu bạn chưa quen với lĩnh vực này, tôi khuyên bạn nên truy cập trang Java Docs . Trước khi tiếp tục, tôi thực sự khuyên bạn nên xem bài viết trước của tôi: Làm việc với hashCode và phương thức bằng trong Java. Nội dung của bài viết này:

1. Câu trả lời duy nhất có thể.
2. Băm là gì.
3. Một chút về lớp học Entry.
4. . put()_
5. Phương pháp hoạt động như thế nào get().
6. Ghi chú

Câu trả lời duy nhất có thể

Nếu có ai yêu cầu tôi giải thích " HashMap hoạt động như thế nào?" ", tôi sẽ trả lời đơn giản: " Theo nguyên tắc Băm ." Nó không thể đơn giản hơn. Để hiểu điều này và nhận được câu trả lời mở rộng, bạn cần chắc chắn rằng mình biết những điều cơ bản về Băm. Phải?

Băm là gì

Băm ở dạng đơn giản nhất là cách chuyển đổi bất kỳ biến/đối tượng nào thành một mã duy nhất sau khi áp dụng bất kỳ công thức/thuật toán nào cho các thuộc tính của chúng. Hàm băm thực sự phải tuân theo quy tắc sau: Hàm băm phải trả về cùng một mã băm bất cứ khi nào nó được áp dụng cho các đối tượng giống nhau hoặc bằng nhau. Nói cách khác, hai đối tượng giống hệt nhau phải lần lượt trả về cùng một mã băm. Bạn có thể đọc thêm về điều này tại đây: Làm việc với phương thức hashCode và bằng trong Java

Một chút về lớp Entry

Theo định nghĩa, bản đồ là “một đối tượng lưu trữ các giá trị và khóa theo cặp”. Khá đơn giản phải không? Vì vậy, phải có một loại cơ chế nào đó trong HashMap lưu trữ các cặp Giá trị và Khóa? Trả lời có. HashMapcó một lớp bên trong Entrytrông như thế này:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Đương nhiên, lớp Entrycó Khóa và Giá trị được lưu trữ dưới dạng thuộc tính. Khóa được đánh dấu là finalvà chúng tôi cũng thấy hai trường bổ sung: nextvà hash. Chúng tôi sẽ cố gắng hiểu mục đích của các trường này khi bài viết tiến triển.

Phương thức put() của Java làm gì?

Trước khi chúng ta đi sâu vào việc triển khai phương thức này put(), điều quan trọng là phải hiểu rằng các phiên bản của một lớp Entryđược lưu trữ trong một mảng. Lớp HashMap định nghĩa biến này là:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Bây giờ hãy xem mã triển khai phương thức put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
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;
}

Chúng ta hãy tìm ra nó từng bước một:

• Trước hết, chúng tôi kiểm tra xem khóa có tồn tại hay không. Nếu khóa không tồn tại ( null), giá trị được đặt trong bảng ở vị trí 0 vì mã băm cho giá trị là null, это – всегда 0.


• Trong bước tiếp theo, giá trị băm được tính bằng mã băm của khóa thu được bằng cách gọi phương thức hashCode(). Giá trị băm này được sử dụng để tính toán vị trí trong mảng nơi đối tượng sẽ được đặt Entry. Các nhà thiết kế JDK cho rằng một hàm được viết kém hashCode()có thể trả về giá trị băm quá cao hoặc quá thấp. Để giải quyết vấn đề này, họ đã giới thiệu một hash()hàm khác và truyền giá trị băm của một đối tượng vào đó để làm cho giá trị băm khớp với kích thước của mảng.


• Bây giờ hàm được gọi indexFor(hash, table.length)để tính toán vị trí chính xác nơi đối tượng sẽ được đặt Entry.


• Đây là nơi phần chính bắt đầu. Bây giờ, dựa trên những gì chúng ta biết rằng hai đối tượng không bằng nhau có thể có mã băm bằng nhau, chúng ta đặt câu hỏi: Liệu hai đối tượng khác nhau có được đặt ở cùng một vị trí trong mảng [nhóm] không LinkedList? Nếu bạn còn nhớ, lớp này Entrycó thuộc tính " next". Thuộc tính này luôn trỏ đến đối tượng tiếp theo trong chuỗi. Đây chính xác là hành vi LinkedList.

Vì vậy, các đối tượng Entryđược lưu trữ ở dạng LinkedList. Khi một đối tượng Entryđược đặt ở một vị trí cụ thể, HashMap sẽ kiểm tra xem liệu đã có mục nào ở vị trí đó chưa. Nếu không có mục nào thì đối tượng được đặt ở vị trí này. Tuy nhiên, nếu đã có một đối tượng ở vị trí này thì thuộc tính tiếp theo sẽ được chọn. Nếu nó trả về nullvà đối tượng hiện tại Entrytrở thành liên kết tiếp theo trong tệp LinkedList. Nếu biến tiếp theo không phải là null, quy trình sẽ được lặp lại cho biến tiếp theo cho đến khi tìm thấy null. Điều gì sẽ xảy ra nếu chúng ta đặt một đối tượng khác có giá trị khác nhưng có cùng khóa như trước? Về mặt logic, điều này sẽ dẫn đến giá trị cũ được thay thế. Làm thế nào điều này xảy ra? Nói chung, sau khi xác định vị trí của một đối tượng Entry, khi di chuyển LinkedListđến vị trí được tính toán, HashMapnó gọi phương thức so sánh khóa cho từng đối tượng Entry. Tất cả Entrycác đối tượng này LinkedListcó thể có mã băm giống nhau, nhưng phương pháp này equals()sẽ kiểm tra sự giống nhau thực sự. Điều này sẽ chỉ thay thế giá trị trong Entry. Do đó, HashMap đảm bảo tính duy nhất của tất cả các khóa.

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

Bây giờ chúng ta đã có ý tưởng về cách lưu trữ các cặp khóa-giá trị trong HashMap. Câu hỏi lớn tiếp theo là: Điều gì xảy ra khi một đối tượng được truyền từ HashMap sang một phương thức get()? Giá trị của một vật được xác định như thế nào? Chúng ta hẳn đã biết câu trả lời rồi, bởi vì cách xác định tính duy nhất của khóa trong phương thức put()có cùng logic mà phương thức đó áp dụng get(). Khi HashMapnó xác định khóa của đối tượng được truyền vào dưới dạng đối số, nó chỉ trả về giá trị của đối tượng tương ứng Entry. Nếu không tìm thấy kết quả phù hợp, phương thức get()sẽ trả về null. Chúng ta hãy xem mã:

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;
}

Đoạn mã trên tương tự như phương thức put()cho đến thời điểm này if (e.hash == hash && ((k = e.key) == key || key.equals(k))), sau đó nó chỉ trả về giá trị của đối tượng.

Ghi chú

• Cấu trúc dữ liệu được lưu trữ trong một đối tượng Entrylà một mảng có tên tablevà kiểu Entry.
• Mỗi vị trí riêng lẻ trong mảng được gọi là nhóm vì nó có thể chứa phần tử đầu tiên LinkedListcủa đối tượng Entry.
• hashCode()Cần có chìa khóa để tính toán vị trí của đối tượng Entry.
• equals()Khóa được sử dụng để kiểm tra tính duy nhất của khóa trong bản đồ( map).
• hashCode()và equals()Giá trị không được sử dụng trong các phương thức get()và set()trong HashMap.
• Mã băm cho các khóa có giá trị nullluôn là 0. Và một đối tượng như vậy Entrysẽ luôn được lưu ở vị trí 0 của mảng.

Tôi hy vọng tôi đã truyền đạt suy nghĩ của mình một cách chính xác trong bài viết này. Nếu bạn tìm thấy lỗi hoặc có thắc mắc, vui lòng để lại trong phần bình luận. Chúc bạn học tập vui vẻ!