Big-O ไม่สอดคล้องกันในการลบออกจาก ArrayList กับ Hash Table หรือไม่

ฉันกำลังดูเว็บไซต์นี้ที่แสดงรายการความซับซ้อนของ Big O สำหรับการดำเนินการต่างๆ สำหรับ Dynamic Arrays ความซับซ้อนในการลบคือ O(n) ในขณะที่สำหรับ Hash Tables คือ O(1)

เพื่อให้ Dynamic Arrays เช่น ArrayLists เป็น O(n) นั่นต้องหมายถึงการดำเนินการลบค่าบางส่วนออกจากจุดศูนย์กลาง จากนั้นจึงเลื่อนแต่ละดัชนีไปที่หนึ่งเพื่อให้บล็อกของข้อมูลอยู่ติดกัน เพราะถ้าเราแค่ลบค่าที่เก็บไว้ที่ดัชนี k และไม่ขยับ มันจะเท่ากับ O(1)

แต่ใน Hash Tables ที่มีการตรวจสอบเชิงเส้น การลบก็เหมือนกัน คุณเพียงเรียกใช้ค่าของคุณผ่านฟังก์ชัน Hash ไปที่ Dynamic Array ที่เก็บข้อมูลของคุณไว้ และลบค่าที่เก็บไว้ในนั้น

เหตุใด Hash Tables จึงได้รับเครดิต O(1) ในขณะที่ Dynamic Arrays ได้รับ O(n)


java data-structures computer-science time-complexity
person user1956609    schedule 11.12.2013    source แหล่งที่มา
comment
เหตุใดพวกเขาจึงควร 'สอดคล้อง'? คุณได้พิจารณาถึงความเป็นไปได้ที่สมมติฐานของคุณไม่ถูกต้องหรือไม่?   -  person user207421    schedule 11.12.2013
comment
ฉันขอแนะนำให้คุณลบแท็ก java และการกล่าวถึง ArrayList และแทนที่ด้วย ผู้ไม่เชื่อเรื่องภาษา หากคุณต้องการจริงๆ แต่เพียง ข้อมูล -structors ก็ใช้ได้เช่นกัน เว้นแต่คำถามนี้จะเกี่ยวกับการใช้งานตารางแฮชของ Java API โดยเฉพาะ (โปรดทราบว่านั่นไม่ได้ใช้การตรวจสอบเชิงเส้น แต่จะใช้การต่อสายแยกกันเป็น สตีเฟนชี้ให้เห็น)   -  person Bernhard Barker    schedule 11.12.2013

คำตอบ (4)


arrow_upward
4
arrow_downward

โปรดดูคำอธิบายที่นี่ สิ่งสำคัญคือจำนวนค่าต่ออาร์เรย์แบบไดนามิกจะถูกเก็บไว้ภายใต้ค่าคงที่

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

person Jelle Fresen    schedule 11.12.2013
comment
คำถามถามเกี่ยวกับการตรวจสอบเชิงเส้น ไม่ใช่การแยกสายโซ่ ฉันคิดว่าคุณกำลังพูดถึงการผูกมัดที่แยกจากกัน ไม่เช่นนั้นสิ่งที่คุณพูดก็ไม่สมเหตุสมผลเลย - person Bernhard Barker; 11.12.2013

arrow_upward
1
arrow_downward

จุดสำคัญของตารางแฮชคือให้ใกล้กับกรณีที่ดีที่สุด โดยที่กรณีที่ดีที่สุดหมายถึงรายการเดียวต่อที่เก็บข้อมูล เห็นได้ชัดว่าคุณไม่มีปัญหาในการยอมรับว่าการลบรายการเดียวออกจากที่เก็บข้อมูลต้องใช้เวลา O(1)

person Marko Topolnik    schedule 11.12.2013
comment
เป็นการยากที่จะบอกได้ว่าคุณกำลังพูดถึงการตรวจสอบเชิงเส้นหรือการโยงแบบแยกกัน (ดูเหมือนจะเป็นการโยงแบบแยกกัน แต่ในทางกลับกัน มันก็ค่อนข้างสมเหตุสมผลถ้าเป็นการตรวจสอบเชิงเส้นเช่นกัน) คำถามถามเกี่ยวกับการตรวจวัดเชิงเส้น ฉันคิดว่าฉันจะชี้ให้เห็นว่า - person Bernhard Barker; 11.12.2013
comment
ฉันกำลังพูดถึงทั้งสองอย่าง เนื่องจากการตรวจสอบเชิงเส้นไม่เกี่ยวข้องกับ HashMap ฉันจึงถือว่า OP ไม่สนใจความแตกต่างโดยละเอียด - person Marko Topolnik; 11.12.2013

arrow_upward
1
arrow_downward

เมื่อมีข้อขัดแย้งด้านแฮชมากมาย คุณจะต้องทำการเปลี่ยนแปลงอย่างมากอย่างแน่นอนเมื่อใช้การตรวจสอบเชิงเส้น

แต่ความซับซ้อนของตารางแฮชอยู่ภายใต้สมมติฐานของ Simply Uniform Hashing ซึ่งหมายความว่า โดยถือว่าจะมีข้อขัดแย้งเกี่ยวกับแฮชจำนวนน้อยที่สุด

เมื่อสิ่งนี้เกิดขึ้น เราเพียงแต่ต้องลบค่าบางส่วนออกและเลื่อนค่าใด ๆ ออกไปหรือเปลี่ยนค่าเพียงเล็กน้อย (โดยพื้นฐานแล้วคงที่)

person Bernhard Barker    schedule 11.12.2013

arrow_upward
0
arrow_downward

เมื่อคุณพูดถึงความซับซ้อนของอัลกอริธึม คุณจำเป็นต้องหารือเกี่ยวกับการใช้งานที่เป็นรูปธรรมจริงๆ

  • ไม่มีคลาส Java ที่เรียกว่า "Hash Table" (ชัด!) หรือ "HashTable"

  • มีคลาส Java ที่เรียกว่า HashMap และ Hashtable และคลาสเหล่านี้มีการลบ O(1) จริงๆ

แต่มันไม่ได้ทำงานอย่างที่คุณคิด (ทั้งหมด?) ตารางแฮชทำงาน โดยเฉพาะอย่างยิ่ง HashMap และ Hashtable ได้รับการจัดระเบียบเป็นอาร์เรย์ของพอยน์เตอร์ไปยัง "chains"

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

สาเหตุที่สายแฮชโดยเฉลี่ยสั้นก็คือคลาส HashMap และ Hashtable ปรับขนาดอาเรย์แฮชหลักโดยอัตโนมัติเมื่อ "ปัจจัยโหลด" (อัตราส่วนของขนาดอาเรย์ต่อจำนวนรายการ) เกินค่าที่กำหนดไว้ล่วงหน้า สมมติว่าฟังก์ชันแฮชกระจายคีย์ (จริง) ค่อนข้างเท่าๆ กัน คุณจะพบว่าเชนนั้นมีความยาวเท่ากันโดยประมาณ สมมติว่าขนาดอาร์เรย์เป็นสัดส่วนกับจำนวนรายการทั้งหมด ตัวประกอบการโหลดจริงจะเป็นความยาวของสายแฮชเฉลี่ย

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

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

person Stephen C    schedule 11.12.2013
comment
คลาส Java ไม่สามารถมีช่องว่างได้ ดังนั้นความคิดของฉันก็คือว่า OP ไม่ได้พูดถึงคลาส Java จริงๆ แต่เป็นเพียงตารางแฮชโดยทั่วไปโดยใช้การตรวจสอบเชิงเส้น (ซึ่งถูกกล่าวถึงอย่างชัดเจน) แทนที่จะแค่ทำข้อผิดพลาดในการพิมพ์ และไม่รู้ว่าคลาส Java ไม่ได้ใช้การตรวจสอบเชิงเส้น - person Bernhard Barker; 11.12.2013