Bài báo
Bắt đầu
Bắt đầu học
JavaRush /Blog Java /Random-VI /Phân tích chi tiết lớp HashMap
Vonorim
Mức độ

Phân tích chi tiết lớp HashMap

Xuất bản trong nhóm
Trước khi chuyển sang thảo luận chi tiết về lớp, hãy tập trung vào các khái niệm cơ bản liên quan đến bảng băm. Bài viết này sẽ không thảo luận về các phương pháp làm việc với ánh xạ băm. Chỉ các thao tác chèn, tìm kiếm và xóa mới được thảo luận rõ ràng và chi tiết. Tôi nghĩ sẽ không khó để đọc mô tả về các phương thức có sẵn cho HashMap từ cùng một Schildt. Có lẽ trong tương lai tôi sẽ viết một bài báo khác dành cho những phương pháp như vậy, nhưng hiện tại điều này vẫn còn nghi ngờ. So với Java 7, lớp HashMap trong Java 8 đã trải qua những thay đổi đáng kể (+1000 dòng mã). Bạn có thể đọc về cách triển khai trong Java 7 tại đây (nhưng không còn phù hợp nữa): habr Bảng băm là một cấu trúc dữ liệu triển khai giao diện mảng kết hợp (mô hình hoặc mục nhập khóa-giá trị trừu tượng), cung cấp khả năng chèn và tìm kiếm rất nhanh: bất kể Việc chèn và tìm kiếm các phần tử số (và đôi khi xóa) được thực hiện trong thời gian gần với hằng số - O(1). Về cơ bản, đây là một mảng thông thường, trong đó vị trí của phần tử phụ thuộc vào giá trị của chính phần tử đó. Mối quan hệ giữa giá trị của một phần tử và vị trí của nó trong bảng băm được xác định bằng hàm băm. Hàm băm lấy một phần dữ liệu đầu vào mà chúng ta gọi là khóa và làm đầu ra, nó tạo ra một số nguyên được gọi là giá trị băm (hoặc mã băm) . Giá trị băm sau đó liên kết khóa của chúng tôi với một chỉ mục bảng băm cụ thể. Đối với các thao tác cơ bản: chèn, tra cứu và xóa, chúng ta sử dụng cùng một hàm băm nên các thao tác này được thực hiện khá nhanh. Vì lý do này, điều quan trọng là hàm băm phải hoạt động nhất quán và xuất ra cùng một chỉ mục cho cùng một dữ liệu đầu vào. Điều đáng chú ý là mã băm kết quả có thể là một giá trị số rất lớn và mảng ban đầu được thiết kế có điều kiện chỉ có 16 phần tử. Tại sao không tạo một mảng có hàng tỷ phần tử để chỉ thêm 10 phần tử? Vì vậy, bằng cách nào đó chúng ta phải chuyển mã băm này thành các giá trị từ 0 đến 15 (nếu kích thước mảng là 16). Và đối với điều này, các phép biến đổi bổ sung được sử dụng. Vì vậy, chúng tôi tạo một chỉ mục để giảm thiểu kích thước của mảng. Ví dụ: trong HashMap trước Java 8, phương thức bổ sung này đã được sử dụng để tìm ô mong muốn: 
static int indexFor(int h, int length) {
        return h & (length-1);
}
Làm đầu vào, nó lấy mã băm thu được do công việc hashCode()và độ dài của mảng bên trong (số lượng ô). Và nó trả về kết quả “mã băm” -> bitwise “AND” -> (độ dài mảng – 1). Lớp HashMapkế thừa từ lớp AbstractMapvà thực hiện các giao diện sau: Map, Cloneable, Serializable. Phương thức .method chịu trách nhiệm về hàm băm trong Java hashCode(). Việc triển khai mặc định hashCode()trả về một giá trị được gọi là mã băm nhận dạng . Ngay cả khi một lớp ghi đè hashCode(), bạn luôn có thể lấy mã băm ID của đối tượng bằng cách gọi System.identityHashCode(Object o). Việc triển khai mặc định hashCode()trong OpenJDK không liên quan gì đến địa chỉ bộ nhớ, như đôi khi người ta vẫn tin. Xem thêm chi tiết tại đây: habr Trong HashMap , bảng băm được triển khai dựa trên một mảng (hay chính xác hơn là động, vì bảng có thể mở rộng) của các danh sách liên kết đơn lẻ. Về cơ bản, chúng tôi nhận được mã băm của khóa nhờ phương thức hashCode(), sau đó được sửa đổi (như chúng tôi sẽ xem xét sau) và nội bộ, bằng cách sử dụng một phương thức bổ sung, các giá trị kết quả sẽ được phân phối đến các ô cần thiết. Các phần tử mảng (ô) còn được gọi là nhóm , được sử dụng để lưu trữ các nút riêng lẻ. Mỗi nhóm là một bộ sưu tập (danh sách hoặc cây). Nút là một đối tượng của một lớp lồng nhau Node(hoặc TreeNodetrong cấu trúc cây). Trên thực tế, bên trong ô mảng LinkedListchỉ có một danh sách liên kết đơn hoặc một cây màu đỏ đen, làm cơ sở cho việc triển khai một lớp khác - TreeMap.
Phân tích chi tiết lớp HashMap - 1
Tùy chọn với cây đỏ đen không xuất hiện thường xuyên (như thế nào, cái gì và ở đâu - bên dưới) và cấu trúc này khá khó hiểu nên điểm nhấn sẽ tập trung vào một nút thuộc loại Nút. Nút là một lớp lồng nhau bên trong HashMapcó các trường sau:
Phân tích chi tiết lớp HashMap - 2
  • final int hash— hàm băm của phần tử hiện tại mà chúng ta thu được nhờ băm khóa;
  • final K key- khóa của phần tử hiện tại. Đây là nơi những gì bạn chỉ định làm đối tượng đầu tiên trong phương thức được ghi vào put();
  • V value- giá trị của phần tử hiện tại. Và những gì bạn chỉ định làm đối tượng thứ hai trong phương thức được viết ở đây put();
  • Node < K, V> next- liên kết tới nút tiếp theo trong cùng một giỏ. Danh sách được kết nối, vì vậy nó cần một liên kết không đến nút tiếp theo, nếu có.
Bây giờ chúng ta hãy xem xét các trường của chính lớp HashMap:
  • transient Node < K, V> [] table– bản thân bảng băm, được triển khai trên cơ sở một mảng, để lưu trữ các cặp khóa-giá trị dưới dạng nút. Đây là nơi lưu trữ các Nút của chúng tôi;
  • transient int size- số cặp khóa-giá trị;
  • int threshold— số phần tử tối đa, khi đạt đến kích thước của bảng băm sẽ tăng gấp đôi. Tính theo công thức (công suất * LoadFactor);
  • final float loadFactor— tham số này xác định mức độ tải mà bảng băm hiện tại cần để tạo bảng băm mới, tức là ngay khi bảng băm đầy 75%, một bảng băm mới sẽ được tạo và các phần tử hiện tại sẽ được chuyển vào đó (một hoạt động tốn kém, vì tất cả các phần tử phải được băm lại);
  • transient Set< Map.Entry< K,V>> entrySet- chứa một bộ nhớ đệm entrySet()mà chúng ta có thể lặp lại HashMap.
Và hằng số:
Java-университет
  • static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— dung lượng bảng băm mặc định (16);
  • static final int MAXIMUM_CAPACITY = 1 << 30- dung lượng tối đa có thể có của bảng băm (khoảng 1 tỷ);
  • static final float DEFAULT_LOAD_FACTOR = 0.75f- hệ số tải mặc định;
  • static final int TREEIFY_THRESHOLD = 8là “ngưỡng” số phần tử trong một nhóm, khi đạt đến ngưỡng đó danh sách liên kết nội bộ sẽ được chuyển thành cấu trúc cây (cây đỏ đen).
  • static final int UNTREEIFY_THRESHOLD = 6— nếu số phần tử trong một giỏ giảm xuống còn 6 thì sẽ xảy ra quá trình chuyển đổi ngược từ cây sang danh sách liên kết;
  • static final int MIN_TREEIFY_CAPACITY = 64— dung lượng tối thiểu (số lượng nhóm) của bảng băm mà tại đó có thể chuyển đổi sang cấu trúc cây. Những thứ kia. Nếu có ít nhất 64 nhóm trong bảng băm và có 8 phần tử trở lên trong một nhóm thì quá trình chuyển đổi sang cấu trúc cây sẽ xảy ra.
Các nhà xây dựng lớp:
  1. public HashMap()— tạo màn hình băm theo mặc định: theo âm lượng (capacity) = 16và theo hệ số tải (load factor) = 0.75;
  2. public HashMap(Map< ? extends K, ? extends V> m)— tạo một ánh xạ băm được khởi tạo bởi các phần tử của một ánh xạ nhất định khác với dung lượng ban đầu đủ để chứa các phần tử của ánh xạ khác;
  3. public HashMap(int initialCapacity)— tạo bản đồ băm với dung lượng ban đầu nhất định. Để HashMap hoạt động chính xác và chính xác, kích thước của mảng bên trong phải là lũy thừa của hai (tức là 16, 64, 128, v.v.);
  4. public HashMap(int initialCapacity, float loadFactor)— tạo bản đồ băm với các tham số được chỉ định: công suất ban đầu và hệ số tải.
Một lớp thực hiện một giao diện Mapvà mở rộng một lớp AbstractMapmà không cần thêm các phương thức riêng của nó. Bản đồ băm không đảm bảo thứ tự các phần tử của nó. Do đó, thứ tự các phần tử được nhập vào bản đồ băm không nhất thiết là thứ tự mà trình vòng lặp truy xuất chúng. Thêm đối tượng Việc thêm cặp khóa-giá trị được thực hiện bằng cách sử dụng put(). Hãy xem các bước liên quan khi thêm một đối tượng:

  1. Giá trị băm của khóa của đối tượng đã nhập được tính toán. Hàm băm khóa được tính bằng một phương thức static final int hash(Object key)đã truy cập vào hashCode()phương thức khóa mà chúng ta biết. Để thực hiện việc này, phương thức được ghi đè hashCode()hoặc cách triển khai mặc định của nó sẽ được sử dụng. Các phép biến đổi bổ sung trong phương thức hash():

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

  2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

    
i = (n - 1) & hash

    где n – длина массива.

  3. Создается an object Node.

  4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

    Теперь к очень подробному примеру.

    1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

    2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

    3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

    4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

    5. Đồng thời, chúng tôi tính toán chỉ mục của nhóm nơi đối tượng của chúng tôi sẽ được đặt và kiểm tra xem đã có phần tử nào trong đó chưa. Chúng tôi tính toán:

      
i = (n - 1) & hash
i = (16 - 1) & 2306996
i = 4

      kiểm tra:

      
if ((p = tab[i = (n - 1) & hash]) == null)

    6. Vì kết quả kiểm tra cho thấy chúng tôi nhận được kết quả đúng (không có phần tử nào trong nhóm), nên một đối tượng Node có các trường sau sẽ được tạo:

      
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
      Phân tích chi tiết lớp HashMap - 3

      Đối tượng Node được tạo của chúng tôi sẽ được thêm vào nhóm theo chỉ mục [4]:

      tab[i] = newNode(hash, key, value, null);
tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()là một phương thức chỉ đơn giản trả về một đối tượng của lớp Node.

    7. Sau khi thêm, sẽ tiến hành kiểm tra xem số phần tử hiện tại có vượt quá tham số hay không threshold:

      if (++size > threshold)
    resize();

      Nếu vượt quá thì một phương thức sẽ được gọi resize()để tăng kích thước của bảng băm.

      Tại thời điểm này, phương thức putVal()(và , tương ứng put()) sẽ hoàn thành công việc của nó.

      Kết quả có thể được biểu diễn bằng đồ họa như sau:

      Phân tích chi tiết lớp HashMap - 4

      Nói chung, đây là giao diện khi thêm Nút (cặp khóa-giá trị) vào bảng băm nếu nhóm mong muốn trống . Bây giờ, hãy thử thêm một phần tử sẽ dẫn đến xung đột (khi có nhiều hơn một phần tử trong một nhóm).

Một chút về xung đột Tình huống khi các khóa khác nhau nằm trong cùng một nhóm (ngay cả với các giá trị băm khác nhau) được gọi là xung đột hoặc xung đột. Ngay cả khi bảng băm lớn hơn tập dữ liệu và hàm băm tốt đã được chọn, điều này không đảm bảo rằng xung đột sẽ không xảy ra. Và giá trị băm được giới hạn trong phạm vi giá trị int (khoảng 4 tỷ). Giá trị mới thu được cũng cần phải được viết ở đâu đó và để làm được điều này, bạn cần xác định chính xác nó sẽ được viết ở đâu. Điều này được gọi là giải quyết xung đột. Có hai cách tiếp cận:
  • phương pháp xâu chuỗi hoặc xâu chuỗi bên ngoài (được triển khai trong HashMap) - tức là ô thực sự chứa một danh sách (chuỗi). Và danh sách có thể đã chứa một số giá trị (không nhất thiết phải có cùng mã băm).
  • phương pháp thăm dò tuyến tính hoặc địa chỉ mở (được triển khai trong IdentityHashMap) - bao gồm tìm kiếm ô trống đầu tiên sau ô được hàm băm trỏ đến;
Bạn có thể đọc về va chạm ở đây: bấm vào

  1. Sử dụng phương thức này, put()chúng tôi sẽ thêm một cặp khóa-giá trị khác vào ánh xạ băm:

    map.put("BLAKE", 10);

  2. Chúng tôi tính toán “băm sơ bộ” – 63281361. Chúng tôi sửa đổi nó và kết quả là chúng tôi nhận được mã băm cuối cùng – 63281940.

  3. Vì lần kiểm tra đầu tiên về "sự trống rỗng" bây giờ sẽ trả về sai (không cần tạo bảng), nên chúng tôi tính toán ngay chỉ mục của nhóm nơi đối tượng của chúng tôi sẽ được đặt:

    
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4

  4. Nhóm tại chỉ mục đã chỉ định sẽ được kiểm tra sự hiện diện của các phần tử trong đó và vì điều kiện if ((p = tab[i = (n - 1) & hash]) == null)không được đáp ứng trong trường hợp này (đã có một phần tử trong nhóm), nên chúng ta chuyển đến khối else.

  5. Trước hết, chúng tôi so sánh phần tử được thêm với phần tử đầu tiên của danh sách được liên kết bên trong nhóm:

    (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

    При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:

    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
      e.value = value;
      afterNodeAccess(e);
       return oldValue;
 }

    В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

  6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

  7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

    if ((e = p.next) == null){
	p.next = newNode(hash, key, value, null)
... };

    Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

    Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))

    Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

    После добавления второго element наш an object HashMap графически выглядит так:

    Phân tích chi tiết lớp HashMap - 5

    В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

    • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
    • если ключи одинаковы, заменить текущее meaning новым.
    • иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

  8. После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

    for (int binCount = 0; ; ++binCount)

    До тех пор, пока их количество не станет равно or больше 7:

    binCount >= TREEIFY_THRESHOLD – 1

    В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

    Thay vì đi vào cấu trúc cây, một phương thức sẽ được gọi resize()để tăng kích thước của bảng băm, phân phối lại các phần tử. treeify()lần lượt, danh sách liên kết TreeNodechuyển đổi thành cây đỏ đen. Phương thức resize()lặp qua tất cả các phần tử của bộ lưu trữ hiện tại, tính toán lại chỉ số của chúng (có tính đến kích thước mới) và phân phối lại các phần tử thành một mảng mới.

    Tóm lại, không đi sâu vào chi tiết cấu trúc của cây đỏ đen, điều sau sẽ xảy ra:

    1. Phần tử đầu tiên của danh sách được viết dưới dạng gốc của toàn bộ cây (màu đen):

      if (root == null) {
    x.parent = null;
    x.red = false;
    root = x;
}

    2. Đối với các yếu tố khác:

      phân phối chúng sang trái hoặc phải tùy thuộc vào giá trị băm:

      if ((ph = p.hash) > h)
    dir = -1;
else if (ph < h)
    dir = 1;

      Tất cả các nút con bên trái phải nhỏ hơn (hoặc bằng) nút gốc của chúng, trong khi tất cả các nút con bên phải phải lớn hơn.

    3. Nếu hai phần tử có cùng giá trị băm và không thể so sánh theo bất kỳ cách nào khác (chúng không triển khai giao diện Comparable), chúng tôi sẽ gián đoạn việc xây dựng cây và gọi phương thức tieBreakOrder(), do đó phương thức này sử dụng phương thức gốc System.identityHashCode()để tính toán mã băm duy nhất trên toàn cầu .

      Xem thêm chi tiết tại đây: link bài viết

    4. Chúng tôi kiểm tra các phần tử cây (đối tượng TreeNode) cho đến khi tìm thấy phần tử con (trái hoặc phải).

      if ((p = (dir <= 0) ? p.left : p.right) == null)

    5. Thêm một nút con (trái hoặc phải tùy theo thư mục):

      x.parent = xp;
if (dir <= 0)
    xp.left = x;
else
    xp.right = x;

    6. Vì việc thêm một phần tử mới có thể làm mất cân bằng của cây nên chúng ta gọi phương thức tái cân bằng:

      root = balanceInsertion(root, x);

      Bạn có thể đọc về cách cân bằng CCH tại đây: habr

    7. Sau khi cân bằng, phần tử gốc có thể thay đổi. Chúng tôi khắc phục điều này bằng cách gọi một phương thức đảm bảo rằng nút gốc được truyền tới nó sẽ là nút đầu tiên:

      moveRootToFront(tab, root)

      Bạn có thể thấy rõ cây đỏ đen được xây dựng và tự cân bằng như thế nào tại đây: trực quan

Về nguyên tắc, đó là tất cả và sử dụng một ví dụ, giả sử rằng chúng ta muốn thêm các tên sau làm khóa: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Và giả sử rằng chúng ta có ít nhất 64 nhóm trong bảng băm và tất cả các phần tử này đã được tích lũy trong một nhóm. Về mặt cấu trúc, nhóm này sẽ trông như thế này (các phần tử được sắp xếp theo mã băm): Loại CCHD:
Phân tích chi tiết lớp HashMap - 6
Xem bên trong thùng:
Phân tích chi tiết lớp HashMap - 7
Truy xuất phần tử (truy xuất giá trị bằng key) Về thao tác thêm thì khá đơn giản. Thuật toán (khi có danh sách liên kết trong nhóm) có thể được viết như sau:
  1. Tính mã băm của khóa.
  2. Tính chỉ số xô.
  3. Đi qua chỉ mục và so sánh khóa của phần tử đầu tiên với giá trị hiện có. Nếu chúng bằng nhau, trả về giá trị, nếu không thì kiểm tra phần tử tiếp theo nếu nó tồn tại.
  4. Nếu đối tượng Node tiếp theo là null, trả về null.
  5. Nếu đối tượng Node tiếp theo không phải là null, hãy đi tới nó và lặp lại ba bước đầu tiên cho đến khi tìm thấy phần tử đó hoặc đối tượng Node tiếp theo là null.
Sử dụng phương pháp này, get()chúng ta nhận được giá trị cho khóa “KING”: 
map.get("KING");
Bên trong, phương thức được gọi getNode(int hash, Object key), trong đó chính khóa (“KING”) và hàm băm của nó (2306996) được truyền vào, được tính toán trước theo cách tương tự như trong quá trình hoạt động put().

  1. Chung ta kiểm tra:

    1. bảng băm có tồn tại không:(tab = table) != null

      Hãy để tôi nhắc bạn rằng khi tạo HashMap, một mảng cho bảng không được tạo trong hàm tạo; điều này xảy ra sau trong phương thức resize(), phương thức này luôn được gọi khi thêm phần tử đầu tiên vào bảng băm. Do đó, nếu không có phần tử nào được thêm vào HashMap thì đơn giản là không có mảng bên trong để lưu trữ các phần tử.

    2. nếu biểu thức trước trả về true, bạn cần đảm bảo rằng độ dài của mảng bên trong lớn hơn 0:(n = tab.length) > 0;

    3. nếu biểu thức trước đó cũng trả về giá trị đúng, hãy đi tới nhóm tại chỉ mục (trong trường hợp 4 của chúng tôi), đã được tính toán trước đó và kiểm tra xem nó có xuất hiện các phần tử không:

      (first = tab[(n - 1) & hash]) != null)

    4. Chúng tôi so sánh khóa mà chúng tôi đang tìm kiếm với khóa của phần tử đầu tiên trong danh sách bên trong nhóm, vì trong hầu hết các nhóm sẽ chỉ có (không phải nơi nào chúng tôi có xung đột) một phần tử (trường hợp của chúng tôi). Như trong trường hợp của phương thức put(), các giá trị băm được so sánh và nếu chúng khớp nhau, các khóa sẽ được so sánh bằng tham chiếu và chỉ sau đó bằng equals().

      if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))

      Vì trong trường hợp của chúng ta, khóa “KING” sẽ đứng trước khóa “BLAKE” (trong danh sách liên kết, các phần tử mới được thêm vào cuối và KING được thêm vào trước), chúng ta sẽ dừng lại ở điểm này và trả về đối tượng đầu tiên của gõ Node vào phương thức get(), phương thức này sẽ “lấy” từ anh ta một trường có giá trị (100):

      return (e = getNode(hash(key), key)) == null ? null : e.value;

  2. Nếu có nhiều hơn một phần tử bên trong nhóm thì:

    1. nếu nhóm là một danh sách được liên kết, chúng ta sẽ xem qua danh sách qua từng phần tử trong một vòng lặp do – whilecho đến khi tìm thấy kết quả khớp:

      do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);

    2. nếu nhóm là cấu trúc cây thì phương thức này sẽ được gọi bổ sung getTreeNode(), phương thức này sẽ sử dụng phương thức này để tìm khóa được yêu cầu find(). Chúng tôi thực hiện tìm kiếm dạng cây - các giá trị băm được so sánh và nút gốc bên trái hoặc bên phải để tìm kiếm được xác định. Nếu các khóa bằng nhau (theo tham chiếu hoặc theo equals), hãy trả về nút này. Nếu nút con bên trái hoặc bên phải là null, chúng tôi sẽ so sánh thêm các khóa bằng cách sử dụng so sánh (nếu các khóa triển khai giao diện Comparable), nếu không, chúng tôi thực hiện tìm kiếm đệ quy qua cây (cây con phải hoặc trái) cho đến khi tìm thấy kết quả khớp.

Xóa các đối tượng khỏi HashMap Vì không gian trong bài viết đã hết nên tôi sẽ mô tả ngắn gọn cách xóa xảy ra theo khóa. Thuật toán rất giống nhau:

  • đi đến nhóm mong muốn (một lần nữa, nó được tính toán trước);

  • nếu chỉ có một đối tượng trong nhóm (chúng tôi kiểm tra con trỏ null của nó), chúng tôi sẽ so sánh các giá trị băm, liên kết và equals(nếu đột nhiên các giá trị băm không bằng nhau). Tìm thấy một trận đấu? Tuyệt vời, đây là khóa của chúng tôi - hãy xóa nó (=null) và trả về giá trị của khóa này.

  • nếu có nhiều hơn một phần tử trong nhóm, chúng tôi sẽ kiểm tra từng phần tử trong một vòng lặp cho đến khi tìm thấy phần tử đó hoặc đến cuối danh sách.

  • nếu không tìm thấy phần tử, chúng tôi trả về null.

Trong tình huống với một cái cây, có một cách thực hiện khá phức tạp, tốt hơn hết là bạn không nên biết và ngủ ngon (mô tả về phương pháp này thậm chí còn nói rằng việc thực hiện phức tạp hơn so với thao tác xóa thông thường trong màu đỏ-đen. cây). Hơn nữa, khi xóa, số nút trong một nhóm có thể trở về 6 và sau đó cây sẽ được xây dựng lại thành danh sách liên kết. Nếu bạn không phải là nhà phát triển có nhiều năm kinh nghiệm thì không cần thiết phải biết và hiểu điều này (và đơn giản là không cần thiết).
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION