[เล่นเพลง] DOUG LLOYD: ตอนนี้คุณ รู้มากเกี่ยวกับอาร์เรย์ที่ และคุณรู้มากเกี่ยวกับรายการที่เชื่อมโยง และเราได้หารือเกี่ยวกับ ข้อดีและข้อเสียเราได้ กล่าวถึงการเชื่อมโยงที่รายการ สามารถรับใหญ่และขนาดเล็ก แต่พวกเขาใช้เวลาขนาดมากขึ้น อาร์เรย์มีมากตรงไปตรงมา ใช้ แต่พวกเขากำลังเข้มงวดในเท่า ในขณะที่เราต้องกำหนดขนาดของ อาร์เรย์ที่จุดเริ่มต้น และจากนั้นเรากำลังติดอยู่กับมัน 

แต่ที่เราได้สวยมาก หมดทุกหัวข้อของเรา เกี่ยวกับรายการที่เชื่อมโยงและอาร์เรย์ หรือมีเรา? บางทีเราสามารถทำสิ่งที่ แม้กระทั่งความคิดสร้างสรรค์มากขึ้น และการจัดเรียงของที่ยืม ความคิดของตารางแฮช 

ดังนั้นในตารางแฮชที่เรากำลังจะพยายาม รวมอาร์เรย์ที่มีรายการที่เชื่อมโยง เรากำลังจะใช้ข้อได้เปรียบ ของอาร์เรย์เช่นการเข้าถึงแบบสุ่ม ความสามารถในการเพียงแค่ไปที่อาร์เรย์ องค์ประกอบ 4 องค์ประกอบหรืออาร์เรย์ 8 โดยไม่ต้องย้ำข้าม นั่นเป็นอย่างรวดเร็วใช่มั้ย? 

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

และหากดำเนินการอย่างถูกต้อง เรากำลังจัดเรียงของการ ข้อได้เปรียบของข้อมูลทั้งสอง โครงสร้างที่คุณเคยเห็นแล้ว อาร์เรย์และรายการที่เชื่อมโยง แทรกสามารถเริ่ม มีแนวโน้มไปที 1 ทีเรายังไม่ได้พูดคุยกันจริงๆ แต่ทีเป็นเพียงกรณีเฉลี่ย สิ่งที่เป็นจริงที่จะเกิดขึ้น คุณไม่ได้เสมอไป มีสถานการณ์กรณีที่เลวร้ายที่สุด และคุณไม่ได้เสมอไปที่จะมี สถานการณ์กรณีที่ดีที่สุดเพื่อให้สิ่งที่ สถานการณ์เฉลี่ย? 

กันแทรกเฉลี่ย ลงในตารางแฮช สามารถเริ่มต้นที่จะได้รับใกล้เคียงกับเวลาอย่างต่อเนื่อง และการลบจะได้รับ ใกล้เคียงกับเวลาอย่างต่อเนื่อง และจะได้รับการค้นหา ใกล้เคียงกับเวลาอย่างต่อเนื่อง That's-- เราไม่ได้มีข้อมูลที่ โครงสร้างที่ยังไม่สามารถทำเช่นนั้น และเพื่อให้เสียงอย่างนี้แล้ว เหมือนเป็นสิ่งที่ดีงาม เราได้ลดลงจริงๆ ข้อเสียของแต่ละตัวของมันเอง 

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

ตอนนี้ข้อเสียของกัญชา ตารางที่พวกเขากำลังจริงๆ ไม่ดีงามในการสั่งซื้อหรือการเรียงลำดับข้อมูล และในความเป็นจริงถ้าคุณเริ่มต้น ที่จะใช้พวกเขาในการสั่งซื้อหรือการจัดเรียง ข้อมูลที่คุณสูญเสียทั้งหมดของ ก่อนหน้านี้คุณได้เปรียบ มีในแง่ของการแทรกและลบ กลายเป็นช่วงเวลาที่ใกล้ชิดกับ ทีของ n และเราได้โดยทั่วไป ถดถอยลงในรายการที่เชื่อมโยง และเพื่อให้เราเพียง แต่ต้องการที่จะใช้กัญชา ตารางถ้าเราไม่สนใจเกี่ยวกับ ไม่ว่าจะเป็นข้อมูลที่ถูกจัดเรียง สำหรับบริบทที่ คุณจะใช้พวกเขาใน CS50 คุณอาจไม่สนใจ ว่าข้อมูลที่ถูกจัดเรียง 

ดังนั้นตารางแฮชคือการรวมกัน สองชิ้นที่แตกต่างกัน ที่เราคุ้นเคย ที่แรกก็คือฟังก์ชั่นที่ เรามักจะเรียกใช้ฟังก์ชันแฮช และฟังก์ชั่นแฮชที่เป็นไปได้ กลับบางจำนวนเต็มไม่เป็นเชิงลบซึ่ง เรามักจะเรียก hashcode ที่ OK? ชิ้นที่สองเป็นอาร์เรย์ซึ่งเป็น ความสามารถในการจัดเก็บข้อมูลประเภทพวกเรา ต้องการที่จะวางลงในโครงสร้างข้อมูล เราจะถือปิดบน เชื่อมโยงองค์ประกอบรายการสำหรับตอนนี้ และเพียงแค่เริ่มต้นด้วยพื้นฐานของการที่ สับตารางที่จะได้รับหัวของรอบนั้น และจากนั้นเราอาจจะระเบิด ความคิดของคุณเล็กน้อยเมื่อเรา รวมอาร์เรย์และการเชื่อมโยงเข้าด้วยกันรายการ 

ความคิดพื้นฐานว่า คือเราจะใช้ข้อมูลบางส่วน เราทำงานข้อมูลผ่านว่า ฟังก์ชั่นแฮช และเพื่อให้ข้อมูลที่มีการประมวลผล และถ่มน้ำลายออกหมายเลข OK? และจากนั้นก็มีตัวเลขที่ เราก็เก็บข้อมูล เราต้องการที่จะเก็บใน อาร์เรย์ที่ตำแหน่งนั้น ดังนั้นตัวอย่างเช่นเราอาจจะมี ตารางแฮชนี้ของสตริง มันมี 10 องค์ประกอบในมันดังนั้น เราสามารถให้พอดีกับ 10 สายในนั้น 

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

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

สมมติว่าตอนนี้เราทำเช่นนี้ อีกครั้งที่เราต้องการที่จะสับพอล เราต้องการที่จะเพิ่มพอล ลงในตารางแฮชนี้ ขอบอกว่าเวลานี้เราทำงาน พอลผ่านฟังก์ชั่นแฮช, hashcode ที่สร้างขึ้นคือ 6 ดีตอนนี้เราสามารถใส่พอล ในตำแหน่งอาร์เรย์ 6 และถ้าเราต้องการที่จะมองขึ้นไม่ว่าจะเป็น พอลอยู่ในตารางแฮชนี้ ทั้งหมดที่เราต้องทำคือการเรียกพอล ผ่านฟังก์ชันแฮชอีกครั้ง และเรากำลังจะได้รับ 6 ออกมาอีกครั้ง 

แล้วเราเพียงแค่มอง ที่ตำแหน่ง 6 อาร์เรย์ พอลมี? ถ้าเป็นเช่นนั้นเขาอยู่ในตารางแฮช พอลไม่ได้มี? เขาเป็นคนที่ไม่ได้อยู่ในตารางแฮช มันตรงไปตรงสวย 

ตอนนี้วิธีที่คุณจะกำหนดฟังก์ชันแฮชหรือไม่? ดีมีจริงๆ จำกัด ไม่มี จำนวนฟังก์ชันแฮชที่เป็นไปได้ ในความเป็นจริงมีจำนวนจริงๆ คนที่ดีจริงๆบนอินเทอร์เน็ต มีจำนวนของจริงๆ คนไม่ดีจริงๆบนอินเทอร์เน็ต นอกจากนี้ยังเป็นเรื่องง่ายสวย ที่จะเขียนไม่ดีหนึ่ง 

ดังนั้นสิ่งที่ทำให้ดีขึ้น ฟังก์ชันแฮชใช่มั้ย? ด้วยฟังก์ชั่นแฮชที่ดีควร ใช้เฉพาะข้อมูลที่ถูกแฮช, และทั้งหมดของข้อมูลที่ถูกแฮช ดังนั้นเราจึงไม่ต้องการที่จะใช้อะไรเลย เราไม่ได้รวมอะไร อื่นนอกเหนือจากข้อมูล และเราต้องการที่จะใช้ข้อมูลทั้งหมด เราไม่ต้องการที่จะใช้เพียงชิ้นส่วน ของมันเราต้องการที่จะใช้ทั้งหมดของมัน ฟังก์ชั่นกัญชาควร นอกจากนี้ยังจะกำหนด นั่นหมายความว่าอย่างไร? ดีมันหมายความว่าเวลาที่เราทุกคน ผ่านชิ้นเดียวกันแน่นอนของข้อมูล ในการทำงานกัญชาเราเสมอ ได้รับ hashcode เดียวกันออก ถ้าผมผ่านเข้าไปในจอห์น ฟังก์ชันแฮชที่ฉันได้รับจาก 4 ฉันควรจะสามารถที่จะทำ 10,000 ครั้งและฉันมักจะได้รับ 4 จึงไม่มีตัวเลขสุ่มได้อย่างมีประสิทธิภาพ สามารถมีส่วนร่วมในความยุ่งเหยิงของเรา tables-- ในฟังก์ชั่นแฮชของเรา 

ฟังก์ชันแฮชควรยัง สม่ำเสมอกระจายข้อมูล ถ้าเวลาที่คุณเรียกใช้ข้อมูลผ่านทุก ฟังก์ชันแฮชคุณได้รับ hashcode 0, ที่อาจไม่ดีอย่างนั้นใช่มั้ย? คุณอาจต้องการที่จะมีขนาดใหญ่ ช่วงของรหัสกัญชา นอกจากนี้ยังมีสิ่งที่สามารถแพร่กระจาย ออกไปทั่วโต๊ะ และยังจะดีถ้าจริงๆ ข้อมูลที่คล้ายกันเช่นเดียวกับจอห์นและโจนาธาน อาจจะถูกกระจายออกไปในการชั่งน้ำหนัก สถานที่แตกต่างกันในตารางแฮช ที่จะเป็นประโยชน์ที่ดี 

นี่คือตัวอย่างของฟังก์ชันแฮชหนึ่ง ที่ผมเขียนนี้ขึ้นมาก่อนหน้านี้ มันไม่ได้เป็นอย่างยิ่ง ฟังก์ชันแฮชดี เหตุผลที่ว่าทำไม่ได้จริงๆ แบกไปลงในขณะนี้ แต่คุณจะเห็นสิ่งที่เกิดขึ้นที่นี่? ดูเหมือนว่าเรากำลังประกาศตัวแปร เรียกว่าผลรวมและการตั้งค่าเท่ากับ 0 และจากนั้นก็เห็นได้ชัดว่าผมกำลังทำอะไรบางอย่าง ตราบใดที่ strstr [เจ] ไม่เท่ากับ เพื่อเครื่องหมาย 0 ฉันกำลังทำอะไรอยู่ที่นั่น? 

นี้เป็นเพียงอีก วิธีการในการดำเนินการ [? STRL?] และการตรวจสอบเมื่อคุณได้ ถึงจุดสิ้นสุดของสตริง ดังนั้นผมจึงไม่ได้มีจริง คำนวณความยาวของสตริง ฉันเพียงแค่ใช้เมื่อฉันตี เครื่องหมาย 0 ตัวละครที่ฉันรู้ ฉันได้มาถึงจุดสิ้นสุดของสตริง และแล้วฉันจะให้ iterating ผ่านสตริงที่ เพิ่ม strstr [เจ] เพื่อสรุปแล้วที่ ท้ายของวันที่จะกลับมา mod ผลรวม HASH_MAX 

โดยทั่วไปกัญชาทั้งหมดนี้ ฟังก์ชั่นที่จะทำคือการเพิ่มขึ้น ทั้งหมดของค่า ASCII ของ สตริงของฉันแล้วมันเป็น กลับ hashcode บาง modded โดย HASH_MAX มันอาจจะมีขนาด ของอาเรย์ของฉันใช่มั้ย? ฉันไม่ต้องการที่จะได้รับกัญชา รหัสถ้าอาร์เรย์ของฉันมีขนาด 10 ฉันไม่ต้องการที่จะได้รับ รหัสกัญชาออก 11, 12, 13 ฉันไม่สามารถนำสิ่งที่เป็น สถานที่เหล่านั้นของอาเรย์, ว่าจะผิดกฎหมาย ฉันต้องทนทุกข์ทรมานความผิดของการแบ่งส่วน 

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

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

ชุมชนวิทยาศาสตร์คอมพิวเตอร์ แน่นอนที่เพิ่มขึ้นและจริงๆค่า เปิดแหล่งที่มาและมันเป็นสิ่งสำคัญมาก เพื่ออ้างอิงแหล่งที่มาของคุณเพื่อให้ผู้คน จะได้รับการแสดงที่มาสำหรับ การทำงานที่พวกเขากำลัง ทำเพื่อประโยชน์ของชุมชน จึงมักจะ sure-- และไม่เพียง แต่สำหรับกัญชา ฟังก์ชั่น แต่โดยทั่วไปเมื่อคุณ ใช้รหัสจากแหล่งภายนอก มักจะอ้างอิงแหล่งที่มาของ ให้เครดิตกับคนที่ทำ บางส่วนของงานเพื่อให้คุณไม่ต้อง 

ตกลงจึงขอทบทวนนี้ ตารางแฮชเป็นครั้งที่สอง ซึ่งเป็นที่ที่เราทิ้ง หลังจากที่เราใส่ จอห์นและพอลเข้ามาในตารางแฮชนี้ คุณเห็นปัญหาที่นี่? คุณอาจจะเห็นสอง แต่โดยเฉพาะอย่างยิ่งที่คุณทำ เห็นปัญหานี้เป็นไปได้? 

ถ้าฉันสับริงโก้และมัน ปรากฎว่าหลังจากการประมวลผล ว่าข้อมูลผ่านฟังก์ชั่นแฮช ริงโก้ยังสร้าง hashcode 6 ผมมีข้อมูลอยู่ที่ สถานที่ตั้งของอาร์เรย์ hashcode-- 6 ดังนั้นจึงอาจเป็นไปได้น้อย ของปัญหาสำหรับฉันตอนนี้ใช่มั้ย? 

เราเรียกวิธีนี้การปะทะกัน และการปะทะกันเกิดขึ้นเมื่อสอง ชิ้นส่วนของข้อมูลที่วิ่งผ่านแฮชเดียวกัน ฟังก์ชั่นให้ผลผลิต hashcode เดียวกัน สมมุติเรายังคงต้องการที่จะได้รับทั้ง ชิ้นส่วนของข้อมูลลงในตารางแฮช, มิฉะนั้นเราจะไม่ได้รับการเรียกใช้ริงโก้ พลผ่านฟังก์ชั่นแฮช เราน่าจะต้องการได้รับ ริงโก้เป็น array ที่ 

ทำอย่างไรเราจะทำมันได้ แต่ถ้าเขา และพอลทั้งผลผลิต hashcode 6? เราไม่ต้องการที่จะเขียนทับพอล เราต้องการพอที่จะมีมากเกินไป ดังนั้นเราจึงจำเป็นที่จะหาวิธีที่จะได้รับ องค์ประกอบในตารางแฮชที่ ยังคงเก็บรักษาอย่างรวดเร็วของเรา แทรกและมองขึ้นอย่างรวดเร็ว และเป็นหนึ่งในวิธีการที่จะจัดการกับมันคือการ ทำสิ่งที่เรียกว่าละเอียดเชิงเส้น 

ใช้วิธีนี้ถ้าเรามี ชนกันทำในสิ่งที่เราจะทำอย่างไร ดีที่เราไม่สามารถทำให้เขาอยู่ในสถานที่อาร์เรย์ 6 หรือสิ่งที่ถูกสร้างขึ้น hashcode, ขอใส่เขาที่ hashcode บวก 1 และหากที่เต็มรูปแบบช่วยให้ ทำให้เขาอยู่ใน hashcode บวก 2 ประโยชน์ของการเป็นอยู่นี้ถ้าเขา ไม่ตรงกับที่เราคิดว่าเขาคือ และเราจะต้องเริ่มต้นการค้นหา, บางทีเราจะได้ไม่ต้องไปไกลเกินไป บางทีเราไม่ต้องค้นหา องค์ประกอบทั้งหมด n ของตารางแฮช บางทีเราต้องค้นหา คู่ของพวกเขา 

และเพื่อให้เรายังคงพุ่งต่อ กรณีที่เฉลี่ยอยู่ใกล้ 1 VS ใกล้กับ n ดังนั้นบางทีที่จะทำงาน ดังนั้นเรามาดูวิธีนี้ อาจจะทำงานออกมาในความเป็นจริง และให้ดูว่าบางทีเราสามารถตรวจสอบได้ ปัญหาที่อาจเกิดขึ้นที่นี่ 

สมมติว่าเราสับบาร์ต ดังนั้นตอนนี้เรากำลังจะไปทำงานชุดใหม่ ของสตริงผ่านฟังก์ชั่นแฮช, และเราทำงานบาร์ตผ่านแฮช ฟังก์ชั่นที่เราได้รับ hashcode 6 เราดูเราจะเห็น 6 ที่ว่างเปล่าเพื่อให้เราสามารถใส่บาร์ตมี 

ตอนนี้เราสับลิซ่าและว่า นอกจากนี้ยังสร้าง hashcode 6 อย่างตอนนี้ที่เรากำลังใช้นี้ วิธีการเชิงเส้นละเอียดเราจะเริ่มต้นที่ 6, เราจะเห็นว่า 6 เต็ม เราไม่สามารถใส่ในลิซ่า 6 เพื่อที่เราจะไป? ลองไปที่ 7 7 ที่ว่างเปล่าเพื่อให้งาน ดังนั้นขอใส่ลิซ่ามี 

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

ตอนนี้เราสับและแม็กกี้ ผลตอบแทนที่ 3 ขอบคุณพระเจ้า เราสามารถที่จะเพียงแค่ใส่แม็กกี้มี เราไม่ได้มีการดำเนินการใด ๆ การเรียงลำดับของละเอียดที่ ตอนนี้เราสับร์จและ มาร์จยังผลตอบแทน 6 

ดี 6 เต็ม 7 เต็ม 8 เต็ม 9 สิ่งที่ถูกต้องขอบคุณพระเจ้าที่ 9 เป็นที่ว่างเปล่า ผมจะสามารถนำมาร์จที่ 9 แล้วเราจะเห็นว่าเราจะเริ่มต้น จะมีปัญหาที่ตอนนี้เราอยู่นี้ เริ่มต้นที่จะยืดชนิดสิ่ง ของที่อยู่ห่างไกลจากรหัสกัญชาของพวกเขา และที 1 นั้นเฉลี่ย กรณีเป็นเวลาอย่างต่อเนื่อง เริ่มที่จะได้รับ more-- เล็ก ๆ น้อย ๆ เริ่มที่จะมีแนวโน้มน้อยมาก ต่อทีของ n เรากำลังเริ่มที่จะสูญเสีย ประโยชน์ของตารางแฮช 

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

ปัญหาอื่น ๆ ก็คือเรา ยังคงและเพื่อให้ห่างไกลได้ถึงจุดนี้ เราได้รับเพียงแค่การจัดเรียงของ เข้าใจสิ่งที่ตารางแฮชคือ เรายังคงมีเพียง 10 ห้องพักสำหรับสตริง ถ้าเราต้องการที่จะยังคงสับ พลเมืองของสปริงฟิลด์, เราเท่านั้นที่จะได้รับ 10 ของพวกเขาในการมี และถ้าเราพยายามเพิ่ม 11 หรือ 12 เราไม่ได้มีสถานที่ที่จะนำพวกเขา เราก็อาจจะมีการหมุนไปรอบ ๆ ใน วงการพยายามที่จะหาจุดที่ว่างเปล่า และเราอาจจะได้รับการติด ในวง จำกัด 

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

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

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

และสำหรับขึ้นดูดีเรารู้ ที่ดูในรายการที่เชื่อมโยง อาจจะมีปัญหาใช่มั้ย? เรามีการค้นหาผ่าน มันตั้งแต่ต้นจนจบ ไม่มีเป็นแบบสุ่ม ในการเข้าถึงรายการที่เชื่อมโยง แต่ถ้าแทนที่จะมีการเชื่อมโยงอย่างใดอย่างหนึ่ง รายการที่ค้นหาจะเป็นโอ n, ตอนนี้เรามี 10 รายการที่เชื่อมโยง หรือ 1,000 รายการที่เชื่อมโยง ตอนนี้ก็โอ n หารด้วย 10 หรือโอ n หารด้วย 1,000 

และในขณะที่เรากำลังพูดถึง ในทางทฤษฎีเกี่ยวกับความซับซ้อน เราคงไม่สนใจในความเป็นจริง โลกสิ่งเหล่านี้สำคัญจริง ใช่มั้ย? เราจริงจะแจ้งให้ทราบ ที่เกิดเหตุการณ์นี้ เพื่อให้ทำงานได้ 10 ครั้งได้เร็วขึ้น หรือ 1,000 ครั้งได้เร็วขึ้น เพราะเรากำลังกระจายยาว ห่วงโซ่ทั่ว 1,000 โซ่ขนาดเล็ก ดังนั้นเวลาที่เราต้องค้นหาแต่ละ ผ่านทางหนึ่งของกลุ่มคนที่เราสามารถ ไม่สนใจ 999 โซ่เราไม่ดูแล เกี่ยวกับและค้นหาเพียงหนึ่ง 

ซึ่งเป็นค่าเฉลี่ย จะสั้นกว่า 1,000 ครั้ง และเพื่อให้เรายังคงมีการจัดเรียงของ พุ่งไปทางนี้กรณีเฉลี่ย ของการเป็นเวลาอย่างต่อเนื่อง แต่ เพียงเพราะเราจะใช้ประโยชน์จาก หารด้วยปัจจัยคงที่ขนาดใหญ่ ลองดูวิธีนี้อาจจะ จริงการมองว่า ดังนั้นนี่คือตารางแฮชที่เรามี ก่อนที่เราจะประกาศตารางแฮชที่ มีความสามารถในการจัดเก็บสาย 10 เราไม่ได้ไปทำอีกต่อไป เรารู้อยู่แล้ว ข้อ จำกัด ของวิธีการที่ ตอนนี้ตารางแฮชของเราเป็นไปได้ อาร์เรย์ของโหนด 10 ตัวชี้ หัวของรายการที่เชื่อมโยง 

และตอนนี้ก็เป็นโมฆะ แต่ละคนหนึ่งในบรรดา 10 ตัวชี้เป็นโมฆะ ไม่มีอะไรที่เป็นของเรา สับตารางในขณะนี้ 

ตอนนี้ขอเริ่มต้นที่จะนำบางส่วน สิ่งที่เป็นตารางแฮชนี้ และให้ดูว่าวิธีนี้คือ ไปเพื่อประโยชน์ของเรานิด ๆ หน่อย ๆ ตอนนี้ขอกัญชาโจอี้ เราจะจะทำงานสตริงโจอี้ผ่าน ฟังก์ชั่นและกัญชาเรากลับ 6 ดีสิ่งที่เราจะทำตอนนี้หรือไม่ 

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

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

ดังนั้นหากเราต้องการที่จะมองขึ้นโจอี้ ต่อมาเราก็สับโจอี้อีกครั้ง เราได้รับ 6 อีกครั้งเพราะเรา ฟังก์ชันแฮชคือกำหนด และจากนั้นเราเริ่มต้นที่หัว ของรายการที่เชื่อมโยงชี้ ไปตามสถานที่อาร์เรย์ 6 และเราสามารถย้ำ ข้ามที่พยายามที่จะหาโจอี้ และถ้าเราสร้างของเรา สับตารางได้อย่างมีประสิทธิภาพ และการทำงานของเราได้อย่างมีประสิทธิภาพกัญชา ในการเผยแพร่ข้อมูลที่ดี โดยเฉลี่ยแต่ละคนเชื่อมโยง รายชื่อที่ทุกสถานที่อาร์เรย์ จะเป็นขนาดของ 10/01 ถ้าเรา เพิ่งมีเป็นอย่างมากที่เดียว รายการที่เชื่อมโยงกับทุกสิ่งที่อยู่ในนั้น 

ถ้าเราจัดจำหน่ายที่ใหญ่เชื่อมโยง รายการใน 10 รายการที่เชื่อมโยง แต่ละรายการจะมีขนาด 1/10 และทำให้เร็วขึ้น 10 เท่า การค้นหาผ่าน ถ้าอย่างนั้นเราทำเช่นนี้อีกครั้ง ตอนนี้ขอให้รอสส์สับ 

และขอบอกว่ารอสส์เมื่อเราทำอย่างนั้น รหัสกัญชาที่เราได้รับกลับมาคือ 2 ดีตอนนี้เราแบบไดนามิกจัดสรร โหนดใหม่ที่เราใส่รอสส์ในโหนดที่ และเราบอกว่าตอนนี้สถานที่อาร์เรย์ 2 แทนการชี้ให้เป็นโมฆะ, ชี้ไปที่หัวของการเชื่อมโยง รายการที่มีโหนดเพียงอย่างเดียวคือรอสส์ และเราสามารถทำในครั้งนี้อีกหนึ่งเรา สามารถสับราเชลและได้รับ hashcode 4 malloc โหนดใหม่ใส่ในราเชล โหนดและกล่าวตั้งแถว 4 ในขณะนี้ชี้ไปที่หัว ของรายการที่เชื่อมโยงที่มี องค์ประกอบที่จะเกิดขึ้นจะเป็นราเชล 

ตกลง แต่สิ่งที่เกิดขึ้นถ้า เรามีการปะทะกันหรือไม่? ลองมาดูวิธีการที่เราจัดการกับการชนกัน โดยใช้วิธีการผูกมัดแยกต่างหาก ลองกัญชาพีบี เราได้รับ hashcode 6 ในตัวอย่างก่อนหน้านี้ของเราที่เราเป็นเพียงแค่ การจัดเก็บสตริงในอาร์เรย์ นี่เป็นปัญหา 

เราไม่ต้องการที่จะบังคับ โจอี้และเราได้อยู่แล้ว เห็นได้ว่าเราจะได้รับการจัดกลุ่มบาง ปัญหาที่เกิดขึ้นถ้าเราพยายามและขั้นตอน และผ่านการสอบสวน แต่ถ้าเราเพียงแค่ชนิดของ การรักษาด้วยวิธีนี้เหมือนกันใช่มั้ย? ก็เช่นเดียวกับการเพิ่มองค์ประกอบ ไปที่หัวของรายการที่เชื่อมโยง ขอเพียงพื้นที่ malloc สำหรับพีบี 

เราจะบอกว่าพีบีจุดชี้ต่อไป ที่ศีรษะเก่าของรายการที่เชื่อมโยง และจากนั้นเพียง 6 ชี้ไปที่ หัวใหม่ของรายการที่เชื่อมโยง และตอนนี้ดูเราได้เปลี่ยนพีบีใน ตอนนี้เราสามารถเก็บสอง องค์ประกอบที่มี hashcode 6 และเราไม่ได้มีปัญหาใด ๆ 

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

ยังคงมีอีกหนึ่ง โครงสร้างข้อมูลออกมี ที่ยังอาจจะเล็กน้อย ที่ดีกว่าในแง่ของการรับประกัน ที่เราแทรกลบและ มองขึ้นเวลาได้เร็วยิ่งขึ้น และเราจะเห็นว่าในวิดีโอบนพยายาม ฉันลอยด์ดั๊กนี้เป็น CS50