ก่อนที่จะไปยังการอภิปรายโดยละเอียดของชั้นเรียน เรามาเน้นที่แนวคิดพื้นฐานที่เกี่ยวข้องกับตารางแฮชกันก่อน บทความนี้จะไม่กล่าวถึงวิธีการทำงานกับการทำแผนที่แฮช เฉพาะการดำเนินการแทรก การค้นหา และการลบเท่านั้นที่จะได้รับการพิจารณาอย่างชัดเจนและละเอียด ฉันคิด ว่าการอ่านคำอธิบายวิธีการสำหรับHashMapจาก Schildt เดียวกันนั้น ไม่ใช่เรื่องยาก บางทีในอนาคตฉันจะเขียนบทความอื่นเกี่ยวกับวิธีการดังกล่าว แต่ตอนนี้ยังไม่มีข้อสงสัย เมื่อเปรียบเทียบกับ Java 7 คลาส HashMap ใน Java 8 มีการเปลี่ยนแปลงที่สำคัญ (โค้ด +1,000 บรรทัด) คุณสามารถอ่านเกี่ยวกับการนำไปใช้ใน Java 7 ได้ที่นี่ (แต่ไม่เกี่ยวข้องอีกต่อไป): ตารางแฮชhabr เป็นโครงสร้างข้อมูลที่ใช้อินเทอร์เฟซอาเรย์แบบเชื่อมโยง (โมเดลคีย์ - ค่านามธรรมหรือรายการ) ซึ่งให้การแทรกและการค้นหาที่รวดเร็วมาก: โดยไม่คำนึงถึง ของการแทรกและการค้นหาองค์ประกอบตัวเลข (และบางครั้งการลบ) จะดำเนินการในเวลาที่ใกล้เคียงกับค่าคงที่ - O(1) โดยพื้นฐานแล้ว นี่คืออาร์เรย์ปกติ โดยที่ตำแหน่งขององค์ประกอบขึ้นอยู่กับค่าขององค์ประกอบนั้นเอง ความสัมพันธ์ระหว่างค่าขององค์ประกอบและตำแหน่งขององค์ประกอบในตารางแฮชจะถูกระบุโดยฟังก์ชันแฮช ฟังก์ชันแฮชรับข้อมูลอินพุตซึ่งเราเรียกว่าคีย์และเอาต์พุตจะสร้างจำนวนเต็มที่เรียกว่าค่าแฮช (หรือรหัสแฮช ) ค่าแฮชจะผูกคีย์ของเรากับดัชนีตารางแฮชเฉพาะ สำหรับการดำเนินการพื้นฐาน: การแทรก การค้นหา และการลบ เราใช้ฟังก์ชันแฮชเดียวกัน ดังนั้นการดำเนินการเหล่านี้จึงดำเนินการได้ค่อนข้างรวดเร็ว ด้วยเหตุนี้ จึงเป็นสิ่งสำคัญที่ฟังก์ชันแฮชจะต้องทำงานอย่างสม่ำเสมอและส่งออกดัชนีเดียวกันสำหรับข้อมูลอินพุตเดียวกัน เป็นที่น่าสังเกตว่ารหัสแฮชที่ได้อาจเป็นค่าตัวเลขจำนวนมากและอาร์เรย์ดั้งเดิมได้รับการออกแบบตามเงื่อนไขสำหรับองค์ประกอบเพียง 16 รายการเท่านั้น ทำไมไม่สร้างอาร์เรย์ที่มีองค์ประกอบนับพันล้านองค์ประกอบเพื่อที่จะเพิ่มเพียงสิบรายการล่ะ ดังนั้นเราจึงต้องแปลงรหัสแฮชนี้เป็นค่าตั้งแต่ 0 ถึง 15 (หากขนาดอาร์เรย์คือ 16) และสำหรับสิ่งนี้ จะใช้การแปลงเพิ่มเติม ดังนั้นเราจึงสร้างดัชนีเพื่อลดขนาดของอาร์เรย์ให้เล็กที่สุด ตัวอย่างเช่น ใน HashMap ก่อน Java 8 วิธีการเพิ่มเติมนี้ใช้ในการค้นหาเซลล์ที่ต้องการ: 
static int indexFor(int h, int length) {
        return h & (length-1);
}
เมื่อป้อนข้อมูล จะใช้รหัสแฮชที่ได้รับจากการทำงานhashCode()และความยาวของอาร์เรย์ภายใน (จำนวนเซลล์) และส่งคืนผลลัพธ์เป็น “รหัสแฮช” -> ระดับบิต “และ” -> (ความยาวของอาร์เรย์ – 1) คลาสHashMapสืบทอดมาจากคลาส และใช้อินเทอร์เฟซ ต่อAbstractMapไปนี้: Map, Cloneable, Serializable.method มีหน้าที่รับผิดชอบฟังก์ชันแฮชในhashCode()Java การใช้งานเริ่มต้นhashCode()จะส่งคืนค่าที่เรียกว่ารหัสแฮชข้อมูลประจำตัว แม้ว่าคลาสจะแทนที่hashCode()คุณก็สามารถรับแฮช ID ของอ็อบเจ็กต์ได้เสมอโดยการSystem.identityHashCode(Object o)เรียก การใช้งานเริ่มต้นhashCode()ใน OpenJDK ไม่เกี่ยวข้องกับที่อยู่หน่วยความจำ ดังที่บางครั้งเชื่อกัน รายละเอียดเพิ่มเติมที่นี่: habr ใน HashMap ตารางแฮชจะถูกนำมาใช้โดยอิงตามอาร์เรย์ (หรือที่เจาะจงกว่านั้นคือไดนามิก เนื่องจากตารางสามารถขยายได้) ของรายการที่ลิงก์เดี่ยวๆ โดยพื้นฐานแล้วเราได้รับรหัสแฮชของคีย์อันเป็นผลมาจากวิธีการhashCode()ซึ่งได้รับการแก้ไขแล้ว (ตามที่เราจะพิจารณาในภายหลัง) และภายในโดยใช้วิธีเพิ่มเติมค่าผลลัพธ์จะถูกกระจายไปยังเซลล์ที่ต้องการ องค์ประกอบอาร์เรย์ (เซลล์) เรียกอีกอย่างว่าที่เก็บข้อมูลซึ่งใช้เพื่อจัดเก็บแต่ละโหนด แต่ละที่เก็บข้อมูลเป็นคอลเลกชัน (รายการหรือแผนผัง) โหนดเป็นวัตถุของคลาสที่ซ้อนกันNode(หรือTreeNodeในโครงสร้างต้นไม้) ในความเป็นจริงภายในเซลล์อาเรย์มีLinkedListเพียงรายการที่เชื่อมโยงเพียงรายการเดียวหรือต้นไม้สีแดงดำซึ่งรองรับการใช้งานคลาสอื่นTreeMap-
การวิเคราะห์โดยละเอียดของคลาส HashMap - 1
ตัวเลือกที่มีต้นไม้สีแดงดำไม่ได้เกิดขึ้นบ่อยนัก (อย่างไร อะไร และที่ไหน - ด้านล่าง) และโครงสร้างนี้ค่อนข้างเข้าใจยาก ดังนั้นการเน้นจะอยู่ที่โหนดประเภทโหนด Nodeเป็นคลาสที่ซ้อนกันภายในHashMapซึ่งมีฟิลด์ต่อไปนี้:
การวิเคราะห์โดยละเอียดของคลาส HashMap - 2
  • final int hash— แฮชขององค์ประกอบปัจจุบัน ซึ่งเราได้รับจากการแฮชคีย์
  • final K key— กุญแจสำคัญขององค์ประกอบปัจจุบัน นี่คือที่ที่คุณระบุว่าเป็นออบเจ็กต์แรกในเมธอดที่ถูกเขียนไปที่put();
  • V value— ค่าขององค์ประกอบปัจจุบัน และสิ่งที่คุณระบุเป็นวัตถุที่สองในวิธีการเขียนไว้ที่put()นี่
  • Node < K, V> next— เชื่อมโยงไปยังโหนดถัดไปภายในตะกร้าเดียวกัน รายการเชื่อมต่ออยู่ ดังนั้นจึงจำเป็นต้องมีลิงก์ไม่ใช่โหนดถัดไป ถ้ามี
ตอนนี้เรามาดูฟิลด์ของคลาส HashMap กัน:
  • transient Node < K, V> [] table– ตารางแฮชนั้นใช้งานบนพื้นฐานของอาร์เรย์ เพื่อจัดเก็บคู่คีย์-ค่าในรูปแบบของโหนด นี่คือที่จัดเก็บโหนดของเรา
  • transient int size— จำนวนคู่คีย์-ค่า
  • int threshold— จำนวนองค์ประกอบสูงสุด เมื่อถึงขนาดของตารางแฮชจะเพิ่มเป็นสองเท่า คำนวณโดยใช้สูตร (ความจุ * loadFactor)
  • final float loadFactor— พารามิเตอร์นี้กำหนดว่าตารางแฮชปัจจุบันต้องโหลดในระดับใดเพื่อสร้างตารางแฮชใหม่ เช่น ทันทีที่ตารางแฮชเต็ม 75% ตารางแฮชใหม่จะถูกสร้างขึ้นและองค์ประกอบปัจจุบันจะถูกย้ายเข้าไปที่นั้น (การดำเนินการที่มีค่าใช้จ่ายสูง เนื่องจากองค์ประกอบทั้งหมดจะต้องได้รับการแฮชใหม่)
  • transient Set< Map.Entry< K,V>> entrySet- มีแคชentrySet()ซึ่งเราสามารถวนซ้ำHashMapได้
และค่าคงที่:
Frontend-университет
  • static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— ความจุตารางแฮชเริ่มต้น (16)
  • static final int MAXIMUM_CAPACITY = 1 << 30— ความจุสูงสุดที่เป็นไปได้ของตารางแฮช (ประมาณ 1 พันล้าน)
  • static final float DEFAULT_LOAD_FACTOR = 0.75f— ปัจจัยโหลดเริ่มต้น;
  • static final int TREEIFY_THRESHOLD = 8คือ “เกณฑ์” ของจำนวนองค์ประกอบในหนึ่งถัง เมื่อถึงนั้น รายการลิงก์ภายในจะถูกแปลงเป็นโครงสร้างแบบต้นไม้ (ต้นไม้สีแดง-ดำ)
  • static final int UNTREEIFY_THRESHOLD = 6— หากจำนวนองค์ประกอบในตะกร้าหนึ่งลดลงเหลือ 6 การเปลี่ยนแบบย้อนกลับจากแผนผังไปยังรายการที่เชื่อมโยงจะเกิดขึ้น
  • static final int MIN_TREEIFY_CAPACITY = 64— ความจุขั้นต่ำ (จำนวนที่เก็บข้อมูล) ของตารางแฮชที่สามารถเปลี่ยนเป็นโครงสร้างแบบต้นไม้ได้ เหล่านั้น. หากมีที่เก็บข้อมูลอย่างน้อย 64 รายการในตารางแฮชและมีองค์ประกอบ 8 รายการขึ้นไปในที่เก็บข้อมูลเดียว การเปลี่ยนไปใช้โครงสร้างแบบต้นไม้จะเกิดขึ้น
ตัวสร้างคลาส:
  1. public HashMap()— สร้างการแสดงแฮชตามค่าเริ่มต้น: ตามปริมาตร(capacity) = 16และด้วยปัจจัยโหลด(load factor) = 0.75;
  2. public HashMap(Map< ? extends K, ? extends V> m)- สร้างการแมปแฮชที่เริ่มต้นโดยองค์ประกอบของการแมปที่กำหนดอื่นด้วยความจุเริ่มต้นที่เพียงพอที่จะรองรับองค์ประกอบของการแมปอื่น
  3. public HashMap(int initialCapacity)— สร้างแผนที่แฮชด้วยความจุเริ่มต้นที่กำหนด เพื่อให้ HashMap ทำงานอย่างถูกต้องและถูกต้อง ขนาดของอาเรย์ภายในต้องเป็นกำลังสอง (เช่น 16, 64, 128 เป็นต้น)
  4. public HashMap(int initialCapacity, float loadFactor)— สร้างแผนที่แฮชด้วยพารามิเตอร์ที่ระบุ: ความจุเริ่มต้นและปัจจัยโหลด
คลาสใช้อินเทอร์เฟซMapและขยายคลาสAbstractMapโดยไม่ต้องเพิ่มวิธีการของตัวเอง แผนที่แฮชไม่รับประกันลำดับขององค์ประกอบ ดังนั้นลำดับที่องค์ประกอบถูกป้อนลงในแมปแฮชจึงไม่จำเป็นต้องเป็นลำดับที่ตัววนซ้ำดึงข้อมูลองค์ประกอบเหล่านั้น การเพิ่มออบเจ็กต์ การเพิ่มคู่คีย์-ค่าทำได้โดยใช้ส่วนขยายput(). มาดูขั้นตอนที่เกี่ยวข้องเมื่อเพิ่มวัตถุ:

  1. ค่าแฮชของคีย์ของออบเจ็กต์ที่ป้อนถูกคำนวณ แฮชคีย์คำนวณโดยวิธีการstatic final int hash(Object key)ที่เข้าถึงhashCode()วิธีคีย์ที่เรารู้จัก อยู่แล้ว hashCode()เมื่อต้องการทำเช่นนี้ ใช้วิธีการแทนที่ หรือการใช้งานเริ่มต้น การเปลี่ยนแปลงเพิ่มเติมในวิธีการ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. ในเวลาเดียวกันเราคำนวณดัชนีของที่เก็บข้อมูลที่จะวางวัตถุของเราและตรวจสอบว่ามีองค์ประกอบอยู่ในนั้นหรือไม่ เราคำนวณ:

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

      ตรวจสอบ:

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

    6. เนื่องจากผลของการตรวจสอบเราเป็นจริง (ไม่มีองค์ประกอบในที่เก็บข้อมูล) จึงจะสร้างออบเจ็กต์โหนดที่มีฟิลด์ต่อไปนี้:

      
{
int hash = 2306996 — сгенерированный хеш-code
String key = {"KING"} — ключ
Integer value = 100 — meaning
Node next = null — link на следующий узел
}
      การวิเคราะห์โดยละเอียดของคลาส HashMap - 3

      วัตถุโหนดที่เราสร้างขึ้นจะถูกเพิ่มลงในที่ฝากข้อมูลภายใต้ดัชนี [4]:

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

      newNode()เป็นวิธีการที่ส่งคืนอ็อบเจ็กต์ของคลาส Node

    7. หลังจากเพิ่มแล้ว จะมีการตรวจสอบเพื่อดูว่าจำนวนองค์ประกอบปัจจุบันเกินพารามิเตอร์หรือไม่threshold:

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

      ถ้าเกิน จะมีการเรียกเมธอดresize()เพื่อเพิ่มขนาดของตารางแฮช

      ณ จุดนี้ วิธีการputVal()(และ ตามลำดับput()) จะทำงานให้เสร็จสิ้น

      ผลลัพธ์สามารถแสดงเป็นกราฟิกได้ดังนี้:

      การวิเคราะห์โดยละเอียดของคลาส HashMap - 4

      โดยทั่วไป นี่คือสิ่งที่การเพิ่มโหนด (คู่คีย์-ค่า) ลงในตารางแฮชจะดูเหมือนว่าที่เก็บข้อมูลที่ต้องการว่างเปล่า ตอนนี้เรามาลองเพิ่มองค์ประกอบที่จะนำไปสู่การชนกัน (เมื่อมีองค์ประกอบมากกว่าหนึ่งองค์ประกอบในที่เก็บข้อมูลเดียว)

เกร็ดเล็กเกร็ดน้อยเกี่ยวกับการชนกัน สถานการณ์ที่คีย์ที่แตกต่างกันไปอยู่ในที่เก็บข้อมูลเดียวกัน (แม้ว่าจะมีแฮชต่างกันก็ตาม) เรียกว่าการชนกันหรือการชนกัน แม้ว่าตารางแฮชจะมีขนาดใหญ่กว่าชุดข้อมูลและเลือกฟังก์ชันแฮชที่ดีแล้ว แต่ก็ไม่ได้รับประกันว่าจะไม่เกิดการชนกัน และค่าแฮชนั้นจำกัดอยู่ที่ช่วงของค่า int (ประมาณ 4 พันล้าน) ค่าใหม่ที่ได้จะต้องเขียนไว้ที่ใดที่หนึ่งด้วยและด้วยเหตุนี้คุณต้องพิจารณาว่าจะเขียนที่ใดอย่างแน่นอน สิ่งนี้เรียกว่าการแก้ไขข้อขัดแย้ง มีสองแนวทาง:
  • การผูกมัดภายนอกหรือวิธีการผูกมัด (ใช้งานใน HashMap) - เช่น เซลล์มีรายการ (ลูกโซ่) จริงๆ และรายการอาจมีหลายค่าอยู่แล้ว (ไม่จำเป็นต้องใช้รหัสแฮชเดียวกัน)
  • วิธีการตรวจสอบเชิงเส้นหรือการกำหนดที่อยู่แบบเปิด (ใช้งานใน IdentityHashMap) - ประกอบด้วยการค้นหาเซลล์ว่างเซลล์แรกหลังจากเซลล์ที่ชี้โดยฟังก์ชันแฮช
คุณสามารถอ่านเกี่ยวกับการชนได้ที่นี่:คลิก

  1. โดยใช้วิธีการนี้put()เราจะเพิ่มคู่คีย์-ค่าอีกคู่หนึ่งในการแมปแฮช:

    map.put("BLAKE", 10);

  2. เราคำนวณ “แฮชเบื้องต้น” – 63281361 เราแก้ไขมันและด้วยเหตุนี้เราจึงได้รหัสแฮชสุดท้าย – 63281940

  3. เนื่องจากการตรวจสอบ "ความว่างเปล่า" ครั้งแรกจะคืนค่าเท็จ (ไม่จำเป็นต้องสร้างตาราง) เราจึงคำนวณดัชนีของที่เก็บข้อมูลที่จะวางวัตถุของเราทันที:

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

  4. ที่เก็บข้อมูลที่ดัชนีที่ระบุจะถูกตรวจสอบว่ามีองค์ประกอบอยู่หรือไม่ และเนื่องจากif ((p = tab[i = (n - 1) & hash]) == null)ไม่ตรงตามเงื่อนไขในกรณีนี้ (มีองค์ประกอบในที่เก็บข้อมูลอยู่แล้ว) เราจึงไปที่บล็อกelse.

  5. ก่อนอื่น เราเปรียบเทียบองค์ประกอบที่ถูกเพิ่มเข้ากับองค์ประกอบแรกของรายการที่เชื่อมโยงภายในที่เก็บข้อมูล:

    (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 графически выглядит так:

    การวิเคราะห์โดยละเอียดของคลาส 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)

    แทนที่จะไปที่โครงสร้างแบบต้นไม้ จะมีการเรียกใช้เมธอดresize()เพื่อเพิ่มขนาดของตารางแฮช โดยกระจายองค์ประกอบใหม่ treeify()ในทางกลับกันรายชื่อTreeNodeผู้เปลี่ยนใจเลื่อมใสกลายเป็นต้นไม้สีแดงดำ วิธีการนี้resize()จะวนซ้ำองค์ประกอบทั้งหมดของที่จัดเก็บข้อมูลปัจจุบัน คำนวณดัชนีใหม่ (โดยคำนึงถึงขนาดใหม่) และแจกจ่ายองค์ประกอบใหม่ลงในอาร์เรย์ใหม่

    สั้นๆ โดยไม่ต้องลงรายละเอียดโครงสร้างของต้นแดง-ดำ จะเกิดสิ่งต่อไปนี้:

    1. องค์ประกอบแรกของรายการเขียนเป็นรากของต้นไม้ทั้งหมด (สีดำ):

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

    2. สำหรับองค์ประกอบอื่นๆ:

      กระจายไปทางซ้ายหรือขวาขึ้นอยู่กับค่าแฮช:

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

      ลูกที่เหลือทั้งหมดจะต้องมีน้อยกว่า (หรือเท่ากับ) โหนดรูท ในขณะที่ลูกที่ถูกต้องทั้งหมดจะต้องมีมากกว่า

    3. หากองค์ประกอบทั้งสองมีแฮชที่เหมือนกันและไม่สามารถเปรียบเทียบด้วยวิธีอื่นได้ (ไม่ได้ใช้อินเทอร์เฟซComparable) เราจะขัดจังหวะการสร้างแผนผังและเรียกเมธอดtieBreakOrder()ซึ่งจะใช้วิธีการดั้งเดิมSystem.identityHashCode()ในการคำนวณรหัสแฮชที่ไม่ซ้ำกันทั่วโลก .

      รายละเอียดเพิ่มเติมที่นี่: ลิงก์ไปยังบทความ

    4. เราตรวจสอบองค์ประกอบต้นไม้ (วัตถุTreeNode) จนกระทั่งพบองค์ประกอบศูนย์ลูก (ซ้ายหรือขวา)

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

    5. เพิ่มโหนดลูก (ซ้ายหรือขวาขึ้นอยู่กับ dir):

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

    6. เนื่องจากการเพิ่มองค์ประกอบใหม่อาจทำให้สมดุลของแผนผังไม่สมดุล เราจึงเรียกวิธีการปรับสมดุลใหม่:

      root = balanceInsertion(root, x);

      คุณสามารถอ่านเกี่ยวกับการปรับสมดุล CCH ได้ที่นี่: habr

    7. หลังจากปรับสมดุลแล้ว องค์ประกอบรูทอาจมีการเปลี่ยนแปลง เราแก้ไขปัญหานี้โดยการเรียกเมธอดที่รับประกันว่ารูทที่ส่งไปให้จะเป็นโหนดแรก:

      moveRootToFront(tab, root)

      คุณจะเห็นได้อย่างชัดเจนว่าต้นไม้สีแดงดำถูกสร้างขึ้นและปรับสมดุลในตัวเองได้อย่างไรที่นี่: การแสดงภาพ

Java-университет
โดยหลักการแล้วทั้งหมดและใช้ตัวอย่าง สมมติว่าเราต้องการเพิ่มชื่อต่อไปนี้เป็นคีย์: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE และสมมติว่าเรามีอย่างน้อย 64 ที่เก็บข้อมูลในตารางแฮช และองค์ประกอบทั้งหมดเหล่านี้ได้สะสมไว้ในที่เก็บข้อมูลเดียว ตามโครงสร้างที่เก็บข้อมูลนี้จะมีลักษณะเช่นนี้ (องค์ประกอบจะถูกจัดเรียงตามรหัสแฮช): ประเภทของ CCHD:
การวิเคราะห์โดยละเอียดของคลาส HashMap - 6
ดูภายในถัง:
การวิเคราะห์โดยละเอียดของคลาส HashMap - 7
การดึงองค์ประกอบ (การรับค่าด้วยคีย์) การดำเนินการเพิ่มนั้นค่อนข้างง่าย อัลกอริทึม (เมื่อมีรายการลิงก์ในที่เก็บข้อมูล) สามารถเขียนได้ดังนี้:
  1. คำนวณรหัสแฮชของคีย์
  2. คำนวณดัชนีถัง
  3. ดูดัชนีและเปรียบเทียบคีย์ขององค์ประกอบแรกกับค่าที่มีอยู่ หากเท่ากัน ให้ส่งคืนค่า หรือไม่เช่นนั้นให้ตรวจสอบองค์ประกอบถัดไป หากมี
  4. หากวัตถุโหนดถัดไปเป็นโมฆะ ให้ส่งกลับค่าโมฆะ
  5. หากวัตถุโหนดถัดไปไม่เป็นโมฆะ ให้ไปที่วัตถุนั้นและทำซ้ำสามขั้นตอนแรกจนกว่าจะพบองค์ประกอบหรือวัตถุโหนดถัดไปเป็นโมฆะ
เมื่อใช้วิธีการนี้get()เราจะได้ค่าของคีย์ "KING": 
map.get("KING");
ภายในวิธีการนี้เรียกว่าgetNode(int hash, Object key)ซึ่งคีย์นั้น (“ KING”) และแฮชของมัน (2306996) จะถูกส่งผ่านไปยังซึ่งคำนวณล่วงหน้าในลักษณะเดียวกับระหว่างการดำเนินการput().

  1. เราตรวจสอบ:

    1. มีตารางแฮชอยู่ด้วยหรือไม่:(tab = table) != null

      ฉันขอเตือนคุณว่าเมื่อสร้าง HashMap อาร์เรย์สำหรับตารางจะไม่ถูกสร้างขึ้นในตัวสร้าง สิ่งนี้จะเกิดขึ้นในภายหลังในเมธอดresize()ซึ่งจะถูกเรียกเสมอเมื่อเพิ่มองค์ประกอบแรกลงในตารางแฮช ดังนั้นหากไม่มีการเพิ่มองค์ประกอบลงใน HashMap ก็ไม่มีอาร์เรย์ภายในที่จะจัดเก็บองค์ประกอบ

    2. หากนิพจน์ก่อนหน้านี้คืนค่าเป็นจริง คุณต้องแน่ใจว่าความยาวของอาร์เรย์ภายในมากกว่า 0:(n = tab.length) > 0;

    3. หากนิพจน์ก่อนหน้านี้คืนค่าเป็นจริง ให้ไปที่บัคเก็ตที่ดัชนี (ในกรณีของเรา 4) ซึ่งคำนวณไว้ก่อนหน้านี้ และตรวจสอบว่ามีองค์ประกอบอยู่หรือไม่:

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

    4. เราเปรียบเทียบคีย์ที่เรากำลังมองหากับคีย์ขององค์ประกอบแรกในรายการภายในบัคเก็ต เนื่องจากในบัคเก็ตส่วนใหญ่จะมีเพียงองค์ประกอบเดียวเท่านั้น (ในกรณีของเรา) เช่นเดียวกับใน กรณีของ method put()แฮชจะถูกเปรียบเทียบ และหากตรงกัน คีย์จะถูกเปรียบเทียบโดยการอ้างอิง และหลังจากนั้นเท่านั้นequals()

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

      เนื่องจากในกรณีของเรา คีย์ “KING” จะนำหน้าคีย์ “BLAKE” (ภายในรายการที่เชื่อมโยง องค์ประกอบใหม่จะถูกเพิ่มที่ส่วนท้าย และเพิ่ม KING ก่อน) เราจะหยุดที่จุดนี้และส่งคืนอ็อบเจ็กต์แรกของ พิมพ์ Node ให้กับเมธอด get() ซึ่ง "ฉก" ฟิลด์ที่มีค่า (100) จากเขา:

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

  2. หากมีมากกว่าหนึ่งองค์ประกอบภายในบัคเก็ต ดังนั้น:

    1. หากที่เก็บข้อมูลเป็นรายการที่เชื่อมโยง เราจะดูรายการผ่านแต่ละองค์ประกอบในลูปdo – whileจนกว่าจะพบรายการที่ตรงกัน:

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

    2. หากที่ฝากข้อมูลเป็นโครงสร้าง แบบต้นไม้ วิธีการนั้นจะถูกเรียกเพิ่มเติมgetTreeNode()ซึ่งจะใช้วิธีการค้นหาคีย์ที่ต้องการ find()เราทำการค้นหาแบบต้นไม้ - เปรียบเทียบแฮชและกำหนดโหนดรูทด้านซ้ายหรือขวาเพื่อค้นหา หากคีย์เท่ากัน (โดยการอ้างอิงหรือโดยequals) ให้ส่งคืนโหนดนี้ หากโหนดลูกด้านซ้ายหรือขวาเป็นโมฆะ เราจะเปรียบเทียบคีย์เพิ่มเติมโดยใช้ comparisonTo (หากคีย์ใช้อินเทอร์เฟซComparable) มิฉะนั้น เราจะทำการค้นหาแบบเรียกซ้ำผ่านแผนผัง (ทรีย่อยด้านขวาหรือซ้าย) จนกว่าจะพบรายการที่ตรงกัน

การลบวัตถุออกจาก HashMap เนื่องจากพื้นที่ในบทความกำลังจะหมด ฉันจะอธิบายโดยย่อว่าการลบเกิดขึ้นอย่างไรโดยคีย์ อัลกอริทึมคล้ายกันมาก:

  • ไปที่ถังที่ต้องการ (คำนวณไว้ล่วงหน้าอีกครั้ง)

  • หากมีเพียงวัตถุเดียวในที่เก็บข้อมูล (เราตรวจสอบตัวชี้ว่าง) เราจะเปรียบเทียบแฮช ลิงก์ และequals(หากจู่ๆ แฮชไม่เท่ากัน) พบการแข่งขัน? เยี่ยมมาก นี่คือคีย์ของเรา - ลบออก (=null) และส่งคืนค่าของคีย์นี้

  • หากมีมากกว่าหนึ่งองค์ประกอบในที่เก็บข้อมูล เราจะตรวจสอบแต่ละองค์ประกอบในวงวนจนกว่าเราจะพบองค์ประกอบหรือไปถึงจุดสิ้นสุดของรายการ

  • หากไม่พบองค์ประกอบ เราจะคืนค่า null

ในสถานการณ์ที่มีต้นไม้มีการใช้งานที่ค่อนข้างยุ่งยากซึ่งไม่ควรรู้และนอนหลับสนิท (คำอธิบายของวิธีการยังบอกด้วยว่าการใช้งานนั้นซับซ้อนกว่าการดำเนินการลบปกติในสีแดงดำ ต้นไม้). นอกจากนี้ เมื่อลบออก จำนวนโหนดในหนึ่งบัคเก็ตสามารถกลับไปเป็น 6 และจากนั้นทรีจะถูกสร้างขึ้นใหม่กลับเป็นรายการที่เชื่อมโยง หากคุณไม่ใช่นักพัฒนาที่มีประสบการณ์มาหลายปี ไม่จำเป็นต้องรู้และเข้าใจสิ่งนี้เลย (และก็ไม่จำเป็นเลย)