[เล่นเพลง]
>> 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