1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [เล่นเพลง] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> DOUG LLOYD: ตอนนี้คุณ รู้มากเกี่ยวกับอาร์เรย์ที่ 5 00:00:09,150 --> 00:00:11,610 และคุณรู้มากเกี่ยวกับรายการที่เชื่อมโยง 6 00:00:11,610 --> 00:00:13,650 และเราได้หารือเกี่ยวกับ ข้อดีและข้อเสียเราได้ 7 00:00:13,650 --> 00:00:16,620 กล่าวถึงการเชื่อมโยงที่รายการ สามารถรับใหญ่และขนาดเล็ก 8 00:00:16,620 --> 00:00:18,630 แต่พวกเขาใช้เวลาขนาดมากขึ้น 9 00:00:18,630 --> 00:00:22,359 อาร์เรย์มีมากตรงไปตรงมา ใช้ แต่พวกเขากำลังเข้มงวดในเท่า 10 00:00:22,359 --> 00:00:24,900 ในขณะที่เราต้องกำหนดขนาดของ อาร์เรย์ที่จุดเริ่มต้น 11 00:00:24,900 --> 00:00:26,910 และจากนั้นเรากำลังติดอยู่กับมัน 12 00:00:26,910 --> 00:00:30,470 >> แต่ที่เราได้สวยมาก หมดทุกหัวข้อของเรา 13 00:00:30,470 --> 00:00:33,040 เกี่ยวกับรายการที่เชื่อมโยงและอาร์เรย์ 14 00:00:33,040 --> 00:00:34,950 หรือมีเรา? 15 00:00:34,950 --> 00:00:37,720 บางทีเราสามารถทำสิ่งที่ แม้กระทั่งความคิดสร้างสรรค์มากขึ้น 16 00:00:37,720 --> 00:00:40,950 และการจัดเรียงของที่ยืม ความคิดของตารางแฮช 17 00:00:40,950 --> 00:00:46,680 >> ดังนั้นในตารางแฮชที่เรากำลังจะพยายาม รวมอาร์เรย์ที่มีรายการที่เชื่อมโยง 18 00:00:46,680 --> 00:00:49,520 เรากำลังจะใช้ข้อได้เปรียบ ของอาร์เรย์เช่นการเข้าถึงแบบสุ่ม 19 00:00:49,520 --> 00:00:53,510 ความสามารถในการเพียงแค่ไปที่อาร์เรย์ องค์ประกอบ 4 องค์ประกอบหรืออาร์เรย์ 8 20 00:00:53,510 --> 00:00:55,560 โดยไม่ต้องย้ำข้าม 21 00:00:55,560 --> 00:00:57,260 นั่นเป็นอย่างรวดเร็วใช่มั้ย? 22 00:00:57,260 --> 00:01:00,714 >> แต่เรายังต้องการที่จะมีข้อมูลของเรา โครงสร้างสามารถเติบโตและหดตัว 23 00:01:00,714 --> 00:01:02,630 เราไม่จำเป็นที่เราทำไม่ได้ ต้องการที่จะถูก จำกัด 24 00:01:02,630 --> 00:01:04,588 และเราต้องการที่จะสามารถ การเพิ่มและเอาสิ่งที่ 25 00:01:04,588 --> 00:01:08,430 ได้อย่างง่ายดายมากซึ่งถ้าคุณจำได้ มีความซับซ้อนมากกับอาร์เรย์ 26 00:01:08,430 --> 00:01:11,650 และเราสามารถเรียกสิ่งนี้ สิ่งใหม่ตารางแฮช 27 00:01:11,650 --> 00:01:15,190 >> และหากดำเนินการอย่างถูกต้อง เรากำลังจัดเรียงของการ 28 00:01:15,190 --> 00:01:18,150 ข้อได้เปรียบของข้อมูลทั้งสอง โครงสร้างที่คุณเคยเห็นแล้ว 29 00:01:18,150 --> 00:01:19,880 อาร์เรย์และรายการที่เชื่อมโยง 30 00:01:19,880 --> 00:01:23,070 แทรกสามารถเริ่ม มีแนวโน้มไปที 1 31 00:01:23,070 --> 00:01:26,207 ทีเรายังไม่ได้พูดคุยกันจริงๆ แต่ทีเป็นเพียงกรณีเฉลี่ย 32 00:01:26,207 --> 00:01:27,540 สิ่งที่เป็นจริงที่จะเกิดขึ้น 33 00:01:27,540 --> 00:01:29,680 คุณไม่ได้เสมอไป มีสถานการณ์กรณีที่เลวร้ายที่สุด 34 00:01:29,680 --> 00:01:32,555 และคุณไม่ได้เสมอไปที่จะมี สถานการณ์กรณีที่ดีที่สุดเพื่อให้สิ่งที่ 35 00:01:32,555 --> 00:01:33,900 สถานการณ์เฉลี่ย? 36 00:01:33,900 --> 00:01:36,500 >> กันแทรกเฉลี่ย ลงในตารางแฮช 37 00:01:36,500 --> 00:01:39,370 สามารถเริ่มต้นที่จะได้รับใกล้เคียงกับเวลาอย่างต่อเนื่อง 38 00:01:39,370 --> 00:01:41,570 และการลบจะได้รับ ใกล้เคียงกับเวลาอย่างต่อเนื่อง 39 00:01:41,570 --> 00:01:44,440 และจะได้รับการค้นหา ใกล้เคียงกับเวลาอย่างต่อเนื่อง 40 00:01:44,440 --> 00:01:48,600 That's-- เราไม่ได้มีข้อมูลที่ โครงสร้างที่ยังไม่สามารถทำเช่นนั้น 41 00:01:48,600 --> 00:01:51,180 และเพื่อให้เสียงอย่างนี้แล้ว เหมือนเป็นสิ่งที่ดีงาม 42 00:01:51,180 --> 00:01:57,010 เราได้ลดลงจริงๆ ข้อเสียของแต่ละตัวของมันเอง 43 00:01:57,010 --> 00:01:59,160 >> เพื่อให้ได้ประสิทธิภาพการทำงานนี้ อัพเกรดแม้ว่าเรา 44 00:01:59,160 --> 00:02:03,580 ต้องคิดใหม่ว่าเราเพิ่ม ข้อมูลลงในโครงสร้าง 45 00:02:03,580 --> 00:02:07,380 โดยเฉพาะที่เราต้องการ ข้อมูลที่ตัวเองที่จะบอกเรา 46 00:02:07,380 --> 00:02:09,725 ที่มันควรจะไปในโครงสร้าง 47 00:02:09,725 --> 00:02:12,850 และถ้าเรานั้นต้องดูว่ามันอยู่ใน โครงสร้างถ้าเราต้องการที่จะหามัน 48 00:02:12,850 --> 00:02:16,610 เราต้องการที่จะดูข้อมูล อีกครั้งและจะสามารถได้อย่างมีประสิทธิภาพ 49 00:02:16,610 --> 00:02:18,910 โดยใช้ข้อมูลที่สุ่มเข้าถึงได้ 50 00:02:18,910 --> 00:02:20,700 เพียงแค่มองไปที่ ข้อมูลที่เราควรจะมี 51 00:02:20,700 --> 00:02:25,890 ความคิดในการที่ว่าเรากำลัง จะพบว่าในตารางแฮช 52 00:02:25,890 --> 00:02:28,770 >> ตอนนี้ข้อเสียของกัญชา ตารางที่พวกเขากำลังจริงๆ 53 00:02:28,770 --> 00:02:31,770 ไม่ดีงามในการสั่งซื้อหรือการเรียงลำดับข้อมูล 54 00:02:31,770 --> 00:02:34,970 และในความเป็นจริงถ้าคุณเริ่มต้น ที่จะใช้พวกเขาในการสั่งซื้อหรือการจัดเรียง 55 00:02:34,970 --> 00:02:37,990 ข้อมูลที่คุณสูญเสียทั้งหมดของ ก่อนหน้านี้คุณได้เปรียบ 56 00:02:37,990 --> 00:02:40,710 มีในแง่ของการแทรกและลบ 57 00:02:40,710 --> 00:02:44,060 กลายเป็นช่วงเวลาที่ใกล้ชิดกับ ทีของ n และเราได้โดยทั่วไป 58 00:02:44,060 --> 00:02:45,530 ถดถอยลงในรายการที่เชื่อมโยง 59 00:02:45,530 --> 00:02:48,850 และเพื่อให้เราเพียง แต่ต้องการที่จะใช้กัญชา ตารางถ้าเราไม่สนใจเกี่ยวกับ 60 00:02:48,850 --> 00:02:51,490 ไม่ว่าจะเป็นข้อมูลที่ถูกจัดเรียง 61 00:02:51,490 --> 00:02:54,290 สำหรับบริบทที่ คุณจะใช้พวกเขาใน CS50 62 00:02:54,290 --> 00:02:58,900 คุณอาจไม่สนใจ ว่าข้อมูลที่ถูกจัดเรียง 63 00:02:58,900 --> 00:03:03,170 >> ดังนั้นตารางแฮชคือการรวมกัน สองชิ้นที่แตกต่างกัน 64 00:03:03,170 --> 00:03:04,980 ที่เราคุ้นเคย 65 00:03:04,980 --> 00:03:07,930 ที่แรกก็คือฟังก์ชั่นที่ เรามักจะเรียกใช้ฟังก์ชันแฮช 66 00:03:07,930 --> 00:03:11,760 และฟังก์ชั่นแฮชที่เป็นไปได้ กลับบางจำนวนเต็มไม่เป็นเชิงลบซึ่ง 67 00:03:11,760 --> 00:03:14,870 เรามักจะเรียก hashcode ที่ OK? 68 00:03:14,870 --> 00:03:20,230 ชิ้นที่สองเป็นอาร์เรย์ซึ่งเป็น ความสามารถในการจัดเก็บข้อมูลประเภทพวกเรา 69 00:03:20,230 --> 00:03:22,190 ต้องการที่จะวางลงในโครงสร้างข้อมูล 70 00:03:22,190 --> 00:03:24,310 เราจะถือปิดบน เชื่อมโยงองค์ประกอบรายการสำหรับตอนนี้ 71 00:03:24,310 --> 00:03:27,810 และเพียงแค่เริ่มต้นด้วยพื้นฐานของการที่ สับตารางที่จะได้รับหัวของรอบนั้น 72 00:03:27,810 --> 00:03:30,210 และจากนั้นเราอาจจะระเบิด ความคิดของคุณเล็กน้อยเมื่อเรา 73 00:03:30,210 --> 00:03:32,920 รวมอาร์เรย์และการเชื่อมโยงเข้าด้วยกันรายการ 74 00:03:32,920 --> 00:03:35,590 >> ความคิดพื้นฐานว่า คือเราจะใช้ข้อมูลบางส่วน 75 00:03:35,590 --> 00:03:37,860 เราทำงานข้อมูลผ่านว่า ฟังก์ชั่นแฮช 76 00:03:37,860 --> 00:03:41,980 และเพื่อให้ข้อมูลที่มีการประมวลผล และถ่มน้ำลายออกหมายเลข OK? 77 00:03:41,980 --> 00:03:44,890 และจากนั้นก็มีตัวเลขที่ เราก็เก็บข้อมูล 78 00:03:44,890 --> 00:03:48,930 เราต้องการที่จะเก็บใน อาร์เรย์ที่ตำแหน่งนั้น 79 00:03:48,930 --> 00:03:53,990 ดังนั้นตัวอย่างเช่นเราอาจจะมี ตารางแฮชนี้ของสตริง 80 00:03:53,990 --> 00:03:57,350 มันมี 10 องค์ประกอบในมันดังนั้น เราสามารถให้พอดีกับ 10 สายในนั้น 81 00:03:57,350 --> 00:03:59,320 >> สมมติว่าเราต้องการที่จะสับจอห์น 82 00:03:59,320 --> 00:04:02,979 ดังนั้นจอห์นเป็นข้อมูลที่เราต้องการแทรก ลงในตารางแฮชนี้อยู่ที่ไหนสักแห่ง 83 00:04:02,979 --> 00:04:03,770 อะไรคือสิ่งที่เราใส่มันได้หรือไม่ 84 00:04:03,770 --> 00:04:05,728 มักจะดีด้วย อาร์เรย์จนถึงขณะนี้เราอาจจะ 85 00:04:05,728 --> 00:04:07,610 จะวางไว้ในตำแหน่งอาร์เรย์ 0 86 00:04:07,610 --> 00:04:09,960 แต่ตอนนี้เรามีฟังก์ชันแฮชใหม่นี้ 87 00:04:09,960 --> 00:04:13,180 >> และขอบอกว่าเราทำงานจอห์น ผ่านฟังก์ชันแฮชนี้ 88 00:04:13,180 --> 00:04:15,417 และก็ถ่มน้ำลายออก 4 89 00:04:15,417 --> 00:04:17,500 ดีนั่นคือสิ่งที่เรา จะต้องการที่จะนำจอห์น 90 00:04:17,500 --> 00:04:22,050 เราต้องการที่จะนำจอห์นในตำแหน่งอาร์เรย์ 4 เพราะถ้าเราสับจอห์น again-- 91 00:04:22,050 --> 00:04:23,810 สมมติว่าต่อมาเรา ต้องการที่จะค้นหาและดู 92 00:04:23,810 --> 00:04:26,960 ถ้าจอห์นที่มีอยู่ในกัญชานี้ table-- ทั้งหมดที่เราต้องทำ 93 00:04:26,960 --> 00:04:30,310 มีการเรียกใช้มันผ่านแฮชเดียวกัน ฟังก์ชั่นได้รับหมายเลข 4 ออก 94 00:04:30,310 --> 00:04:33,929 และสามารถที่จะพบกับจอห์น ทันทีในโครงสร้างข้อมูลของเรา 95 00:04:33,929 --> 00:04:34,720 นั่นเป็นสิ่งที่ดีงาม 96 00:04:34,720 --> 00:04:36,928 >> สมมติว่าตอนนี้เราทำเช่นนี้ อีกครั้งที่เราต้องการที่จะสับพอล 97 00:04:36,928 --> 00:04:39,446 เราต้องการที่จะเพิ่มพอล ลงในตารางแฮชนี้ 98 00:04:39,446 --> 00:04:42,070 ขอบอกว่าเวลานี้เราทำงาน พอลผ่านฟังก์ชั่นแฮช, 99 00:04:42,070 --> 00:04:44,600 hashcode ที่สร้างขึ้นคือ 6 100 00:04:44,600 --> 00:04:47,340 ดีตอนนี้เราสามารถใส่พอล ในตำแหน่งอาร์เรย์ 6 101 00:04:47,340 --> 00:04:50,040 และถ้าเราต้องการที่จะมองขึ้นไม่ว่าจะเป็น พอลอยู่ในตารางแฮชนี้ 102 00:04:50,040 --> 00:04:53,900 ทั้งหมดที่เราต้องทำคือการเรียกพอล ผ่านฟังก์ชันแฮชอีกครั้ง 103 00:04:53,900 --> 00:04:55,830 และเรากำลังจะได้รับ 6 ออกมาอีกครั้ง 104 00:04:55,830 --> 00:04:57,590 >> แล้วเราเพียงแค่มอง ที่ตำแหน่ง 6 อาร์เรย์ 105 00:04:57,590 --> 00:04:58,910 พอลมี? 106 00:04:58,910 --> 00:05:00,160 ถ้าเป็นเช่นนั้นเขาอยู่ในตารางแฮช 107 00:05:00,160 --> 00:05:01,875 พอลไม่ได้มี? 108 00:05:01,875 --> 00:05:03,000 เขาเป็นคนที่ไม่ได้อยู่ในตารางแฮช 109 00:05:03,000 --> 00:05:05,720 มันตรงไปตรงสวย 110 00:05:05,720 --> 00:05:07,770 >> ตอนนี้วิธีที่คุณจะกำหนดฟังก์ชันแฮชหรือไม่? 111 00:05:07,770 --> 00:05:11,460 ดีมีจริงๆ จำกัด ไม่มี จำนวนฟังก์ชันแฮชที่เป็นไปได้ 112 00:05:11,460 --> 00:05:14,350 ในความเป็นจริงมีจำนวนจริงๆ คนที่ดีจริงๆบนอินเทอร์เน็ต 113 00:05:14,350 --> 00:05:17,560 มีจำนวนของจริงๆ คนไม่ดีจริงๆบนอินเทอร์เน็ต 114 00:05:17,560 --> 00:05:21,080 นอกจากนี้ยังเป็นเรื่องง่ายสวย ที่จะเขียนไม่ดีหนึ่ง 115 00:05:21,080 --> 00:05:23,760 >> ดังนั้นสิ่งที่ทำให้ดีขึ้น ฟังก์ชันแฮชใช่มั้ย? 116 00:05:23,760 --> 00:05:27,280 ด้วยฟังก์ชั่นแฮชที่ดีควร ใช้เฉพาะข้อมูลที่ถูกแฮช, 117 00:05:27,280 --> 00:05:29,420 และทั้งหมดของข้อมูลที่ถูกแฮช 118 00:05:29,420 --> 00:05:32,500 ดังนั้นเราจึงไม่ต้องการที่จะใช้อะไรเลย เราไม่ได้รวมอะไร 119 00:05:32,500 --> 00:05:35,560 อื่นนอกเหนือจากข้อมูล 120 00:05:35,560 --> 00:05:37,080 และเราต้องการที่จะใช้ข้อมูลทั้งหมด 121 00:05:37,080 --> 00:05:39,830 เราไม่ต้องการที่จะใช้เพียงชิ้นส่วน ของมันเราต้องการที่จะใช้ทั้งหมดของมัน 122 00:05:39,830 --> 00:05:41,710 ฟังก์ชั่นกัญชาควร นอกจากนี้ยังจะกำหนด 123 00:05:41,710 --> 00:05:42,550 นั่นหมายความว่าอย่างไร? 124 00:05:42,550 --> 00:05:46,200 ดีมันหมายความว่าเวลาที่เราทุกคน ผ่านชิ้นเดียวกันแน่นอนของข้อมูล 125 00:05:46,200 --> 00:05:50,040 ในการทำงานกัญชาเราเสมอ ได้รับ hashcode เดียวกันออก 126 00:05:50,040 --> 00:05:52,870 ถ้าผมผ่านเข้าไปในจอห์น ฟังก์ชันแฮชที่ฉันได้รับจาก 4 127 00:05:52,870 --> 00:05:56,110 ฉันควรจะสามารถที่จะทำ 10,000 ครั้งและฉันมักจะได้รับ 4 128 00:05:56,110 --> 00:06:00,810 จึงไม่มีตัวเลขสุ่มได้อย่างมีประสิทธิภาพ สามารถมีส่วนร่วมในความยุ่งเหยิงของเรา tables-- 129 00:06:00,810 --> 00:06:02,750 ในฟังก์ชั่นแฮชของเรา 130 00:06:02,750 --> 00:06:05,750 >> ฟังก์ชันแฮชควรยัง สม่ำเสมอกระจายข้อมูล 131 00:06:05,750 --> 00:06:09,700 ถ้าเวลาที่คุณเรียกใช้ข้อมูลผ่านทุก ฟังก์ชันแฮชคุณได้รับ hashcode 0, 132 00:06:09,700 --> 00:06:11,200 ที่อาจไม่ดีอย่างนั้นใช่มั้ย? 133 00:06:11,200 --> 00:06:14,600 คุณอาจต้องการที่จะมีขนาดใหญ่ ช่วงของรหัสกัญชา 134 00:06:14,600 --> 00:06:17,190 นอกจากนี้ยังมีสิ่งที่สามารถแพร่กระจาย ออกไปทั่วโต๊ะ 135 00:06:17,190 --> 00:06:23,210 และยังจะดีถ้าจริงๆ ข้อมูลที่คล้ายกันเช่นเดียวกับจอห์นและโจนาธาน 136 00:06:23,210 --> 00:06:26,320 อาจจะถูกกระจายออกไปในการชั่งน้ำหนัก สถานที่แตกต่างกันในตารางแฮช 137 00:06:26,320 --> 00:06:28,750 ที่จะเป็นประโยชน์ที่ดี 138 00:06:28,750 --> 00:06:31,250 >> นี่คือตัวอย่างของฟังก์ชันแฮชหนึ่ง 139 00:06:31,250 --> 00:06:33,150 ที่ผมเขียนนี้ขึ้นมาก่อนหน้านี้ 140 00:06:33,150 --> 00:06:35,047 มันไม่ได้เป็นอย่างยิ่ง ฟังก์ชันแฮชดี 141 00:06:35,047 --> 00:06:37,380 เหตุผลที่ว่าทำไม่ได้จริงๆ แบกไปลงในขณะนี้ 142 00:06:37,380 --> 00:06:41,040 แต่คุณจะเห็นสิ่งที่เกิดขึ้นที่นี่? 143 00:06:41,040 --> 00:06:44,420 ดูเหมือนว่าเรากำลังประกาศตัวแปร เรียกว่าผลรวมและการตั้งค่าเท่ากับ 0 144 00:06:44,420 --> 00:06:50,010 และจากนั้นก็เห็นได้ชัดว่าผมกำลังทำอะไรบางอย่าง ตราบใดที่ strstr [เจ] ไม่เท่ากับ 145 00:06:50,010 --> 00:06:52,490 เพื่อเครื่องหมาย 0 146 00:06:52,490 --> 00:06:54,870 ฉันกำลังทำอะไรอยู่ที่นั่น? 147 00:06:54,870 --> 00:06:57,440 >> นี้เป็นเพียงอีก วิธีการในการดำเนินการ [? STRL?] 148 00:06:57,440 --> 00:06:59,773 และการตรวจสอบเมื่อคุณได้ ถึงจุดสิ้นสุดของสตริง 149 00:06:59,773 --> 00:07:02,480 ดังนั้นผมจึงไม่ได้มีจริง คำนวณความยาวของสตริง 150 00:07:02,480 --> 00:07:05,640 ฉันเพียงแค่ใช้เมื่อฉันตี เครื่องหมาย 0 ตัวละครที่ฉันรู้ 151 00:07:05,640 --> 00:07:07,185 ฉันได้มาถึงจุดสิ้นสุดของสตริง 152 00:07:07,185 --> 00:07:09,560 และแล้วฉันจะให้ iterating ผ่านสตริงที่ 153 00:07:09,560 --> 00:07:15,310 เพิ่ม strstr [เจ] เพื่อสรุปแล้วที่ ท้ายของวันที่จะกลับมา mod ผลรวม 154 00:07:15,310 --> 00:07:16,200 HASH_MAX 155 00:07:16,200 --> 00:07:18,700 >> โดยทั่วไปกัญชาทั้งหมดนี้ ฟังก์ชั่นที่จะทำคือการเพิ่มขึ้น 156 00:07:18,700 --> 00:07:23,450 ทั้งหมดของค่า ASCII ของ สตริงของฉันแล้วมันเป็น 157 00:07:23,450 --> 00:07:26,390 กลับ hashcode บาง modded โดย HASH_MAX 158 00:07:26,390 --> 00:07:29,790 มันอาจจะมีขนาด ของอาเรย์ของฉันใช่มั้ย? 159 00:07:29,790 --> 00:07:33,160 ฉันไม่ต้องการที่จะได้รับกัญชา รหัสถ้าอาร์เรย์ของฉันมีขนาด 10 160 00:07:33,160 --> 00:07:35,712 ฉันไม่ต้องการที่จะได้รับ รหัสกัญชาออก 11, 12, 161 00:07:35,712 --> 00:07:38,690 13 ฉันไม่สามารถนำสิ่งที่เป็น สถานที่เหล่านั้นของอาเรย์, 162 00:07:38,690 --> 00:07:39,790 ว่าจะผิดกฎหมาย 163 00:07:39,790 --> 00:07:42,130 ฉันต้องทนทุกข์ทรมานความผิดของการแบ่งส่วน 164 00:07:42,130 --> 00:07:45,230 >> ตอนนี้ที่นี่เป็นอีกหนึ่งกันอย่างรวดเร็ว 165 00:07:45,230 --> 00:07:48,470 โดยทั่วไปคุณอาจไม่ได้ไป ต้องการที่จะเขียนฟังก์ชันแฮชของคุณเอง 166 00:07:48,470 --> 00:07:50,997 มันเป็นจริงบิตของ ศิลปะไม่ใช่วิทยาศาสตร์ 167 00:07:50,997 --> 00:07:52,580 และมีจำนวนมากที่จะเข้าสู่พวกเขา 168 00:07:52,580 --> 00:07:55,288 อินเทอร์เน็ตเช่นฉันกล่าวว่าเป็นเต็มรูปแบบ ฟังก์ชั่นแฮชที่ดีจริงๆ 169 00:07:55,288 --> 00:07:58,470 และคุณควรจะใช้อินเทอร์เน็ตไปยัง พบฟังก์ชันแฮชเพราะมันเป็นจริงๆ 170 00:07:58,470 --> 00:08:03,230 เพียงแค่ชนิดของที่ไม่จำเป็น เสียเวลาในการสร้างของคุณเอง 171 00:08:03,230 --> 00:08:05,490 >> คุณสามารถเขียนคนง่าย เพื่อการทดสอบ 172 00:08:05,490 --> 00:08:08,323 แต่เมื่อคุณจริงจะไป เริ่มต้น hashing ข้อมูลและการจัดเก็บ 173 00:08:08,323 --> 00:08:10,780 ลงในตารางแฮชคุณ อาจจะต้องการ 174 00:08:10,780 --> 00:08:14,580 ที่จะใช้ฟังก์ชั่นบางอย่างที่ถูกสร้างขึ้น สำหรับคุณที่มีอยู่บนอินเทอร์เน็ต 175 00:08:14,580 --> 00:08:17,240 หากคุณไม่เพียงให้แน่ใจว่า เพื่ออ้างอิงแหล่งที่มาของคุณ 176 00:08:17,240 --> 00:08:21,740 ไม่มีเหตุผลที่จะไม่ ขโมยความคิดอะไรที่นี่ 177 00:08:21,740 --> 00:08:25,370 >> ชุมชนวิทยาศาสตร์คอมพิวเตอร์ แน่นอนที่เพิ่มขึ้นและจริงๆค่า 178 00:08:25,370 --> 00:08:28,796 เปิดแหล่งที่มาและมันเป็นสิ่งสำคัญมาก เพื่ออ้างอิงแหล่งที่มาของคุณเพื่อให้ผู้คน 179 00:08:28,796 --> 00:08:30,670 จะได้รับการแสดงที่มาสำหรับ การทำงานที่พวกเขากำลัง 180 00:08:30,670 --> 00:08:32,312 ทำเพื่อประโยชน์ของชุมชน 181 00:08:32,312 --> 00:08:34,020 จึงมักจะ sure-- และไม่เพียง แต่สำหรับกัญชา 182 00:08:34,020 --> 00:08:37,270 ฟังก์ชั่น แต่โดยทั่วไปเมื่อคุณ ใช้รหัสจากแหล่งภายนอก 183 00:08:37,270 --> 00:08:38,299 มักจะอ้างอิงแหล่งที่มาของ 184 00:08:38,299 --> 00:08:43,500 ให้เครดิตกับคนที่ทำ บางส่วนของงานเพื่อให้คุณไม่ต้อง 185 00:08:43,500 --> 00:08:46,720 >> ตกลงจึงขอทบทวนนี้ ตารางแฮชเป็นครั้งที่สอง 186 00:08:46,720 --> 00:08:48,780 ซึ่งเป็นที่ที่เราทิ้ง หลังจากที่เราใส่ 187 00:08:48,780 --> 00:08:53,300 จอห์นและพอลเข้ามาในตารางแฮชนี้ 188 00:08:53,300 --> 00:08:55,180 คุณเห็นปัญหาที่นี่? 189 00:08:55,180 --> 00:08:58,410 คุณอาจจะเห็นสอง 190 00:08:58,410 --> 00:09:02,240 แต่โดยเฉพาะอย่างยิ่งที่คุณทำ เห็นปัญหานี้เป็นไปได้? 191 00:09:02,240 --> 00:09:06,770 >> ถ้าฉันสับริงโก้และมัน ปรากฎว่าหลังจากการประมวลผล 192 00:09:06,770 --> 00:09:14,000 ว่าข้อมูลผ่านฟังก์ชั่นแฮช ริงโก้ยังสร้าง hashcode 6 193 00:09:14,000 --> 00:09:16,810 ผมมีข้อมูลอยู่ที่ สถานที่ตั้งของอาร์เรย์ hashcode-- 6 194 00:09:16,810 --> 00:09:22,000 ดังนั้นจึงอาจเป็นไปได้น้อย ของปัญหาสำหรับฉันตอนนี้ใช่มั้ย? 195 00:09:22,000 --> 00:09:23,060 >> เราเรียกวิธีนี้การปะทะกัน 196 00:09:23,060 --> 00:09:26,460 และการปะทะกันเกิดขึ้นเมื่อสอง ชิ้นส่วนของข้อมูลที่วิ่งผ่านแฮชเดียวกัน 197 00:09:26,460 --> 00:09:29,200 ฟังก์ชั่นให้ผลผลิต hashcode เดียวกัน 198 00:09:29,200 --> 00:09:32,850 สมมุติเรายังคงต้องการที่จะได้รับทั้ง ชิ้นส่วนของข้อมูลลงในตารางแฮช, 199 00:09:32,850 --> 00:09:36,330 มิฉะนั้นเราจะไม่ได้รับการเรียกใช้ริงโก้ พลผ่านฟังก์ชั่นแฮช 200 00:09:36,330 --> 00:09:40,870 เราน่าจะต้องการได้รับ ริงโก้เป็น array ที่ 201 00:09:40,870 --> 00:09:46,070 >> ทำอย่างไรเราจะทำมันได้ แต่ถ้าเขา และพอลทั้งผลผลิต hashcode 6? 202 00:09:46,070 --> 00:09:49,520 เราไม่ต้องการที่จะเขียนทับพอล เราต้องการพอที่จะมีมากเกินไป 203 00:09:49,520 --> 00:09:52,790 ดังนั้นเราจึงจำเป็นที่จะหาวิธีที่จะได้รับ องค์ประกอบในตารางแฮชที่ 204 00:09:52,790 --> 00:09:56,550 ยังคงเก็บรักษาอย่างรวดเร็วของเรา แทรกและมองขึ้นอย่างรวดเร็ว 205 00:09:56,550 --> 00:10:01,350 และเป็นหนึ่งในวิธีการที่จะจัดการกับมันคือการ ทำสิ่งที่เรียกว่าละเอียดเชิงเส้น 206 00:10:01,350 --> 00:10:04,170 >> ใช้วิธีนี้ถ้าเรามี ชนกันทำในสิ่งที่เราจะทำอย่างไร 207 00:10:04,170 --> 00:10:08,580 ดีที่เราไม่สามารถทำให้เขาอยู่ในสถานที่อาร์เรย์ 6 หรือสิ่งที่ถูกสร้างขึ้น hashcode, 208 00:10:08,580 --> 00:10:10,820 ขอใส่เขาที่ hashcode บวก 1 209 00:10:10,820 --> 00:10:13,670 และหากที่เต็มรูปแบบช่วยให้ ทำให้เขาอยู่ใน hashcode บวก 2 210 00:10:13,670 --> 00:10:17,420 ประโยชน์ของการเป็นอยู่นี้ถ้าเขา ไม่ตรงกับที่เราคิดว่าเขาคือ 211 00:10:17,420 --> 00:10:20,850 และเราจะต้องเริ่มต้นการค้นหา, บางทีเราจะได้ไม่ต้องไปไกลเกินไป 212 00:10:20,850 --> 00:10:23,900 บางทีเราไม่ต้องค้นหา องค์ประกอบทั้งหมด n ของตารางแฮช 213 00:10:23,900 --> 00:10:25,790 บางทีเราต้องค้นหา คู่ของพวกเขา 214 00:10:25,790 --> 00:10:30,680 >> และเพื่อให้เรายังคงพุ่งต่อ กรณีที่เฉลี่ยอยู่ใกล้ 1 VS 215 00:10:30,680 --> 00:10:34,280 ใกล้กับ n ดังนั้นบางทีที่จะทำงาน 216 00:10:34,280 --> 00:10:38,010 ดังนั้นเรามาดูวิธีนี้ อาจจะทำงานออกมาในความเป็นจริง 217 00:10:38,010 --> 00:10:41,460 และให้ดูว่าบางทีเราสามารถตรวจสอบได้ ปัญหาที่อาจเกิดขึ้นที่นี่ 218 00:10:41,460 --> 00:10:42,540 >> สมมติว่าเราสับบาร์ต 219 00:10:42,540 --> 00:10:45,581 ดังนั้นตอนนี้เรากำลังจะไปทำงานชุดใหม่ ของสตริงผ่านฟังก์ชั่นแฮช, 220 00:10:45,581 --> 00:10:48,460 และเราทำงานบาร์ตผ่านแฮช ฟังก์ชั่นที่เราได้รับ hashcode 6 221 00:10:48,460 --> 00:10:52,100 เราดูเราจะเห็น 6 ที่ว่างเปล่าเพื่อให้เราสามารถใส่บาร์ตมี 222 00:10:52,100 --> 00:10:55,410 >> ตอนนี้เราสับลิซ่าและว่า นอกจากนี้ยังสร้าง hashcode 6 223 00:10:55,410 --> 00:10:58,330 อย่างตอนนี้ที่เรากำลังใช้นี้ วิธีการเชิงเส้นละเอียดเราจะเริ่มต้นที่ 6, 224 00:10:58,330 --> 00:10:59,330 เราจะเห็นว่า 6 เต็ม 225 00:10:59,330 --> 00:11:00,990 เราไม่สามารถใส่ในลิซ่า 6 226 00:11:00,990 --> 00:11:02,090 เพื่อที่เราจะไป? 227 00:11:02,090 --> 00:11:03,280 ลองไปที่ 7 228 00:11:03,280 --> 00:11:04,610 7 ที่ว่างเปล่าเพื่อให้งาน 229 00:11:04,610 --> 00:11:06,510 ดังนั้นขอใส่ลิซ่ามี 230 00:11:06,510 --> 00:11:10,200 >> ตอนนี้เราสับโฮเมอร์และเราได้รับ 7 231 00:11:10,200 --> 00:11:13,380 ตกลงที่ดีที่เรารู้ว่า 7 เต็มรูปแบบ ตอนนี้เราจึงไม่สามารถใส่โฮเมอร์มี 232 00:11:13,380 --> 00:11:14,850 ถ้าอย่างนั้นเราไปที่ 8 233 00:11:14,850 --> 00:11:15,664 8 เป็นอยู่? 234 00:11:15,664 --> 00:11:18,330 ใช่และ 8 ใกล้กับ 7 ดังนั้นหาก เราจะต้องเริ่มต้นการค้นหาเรา 235 00:11:18,330 --> 00:11:20,020 จะไม่ต้องไปไกลเกินไป 236 00:11:20,020 --> 00:11:22,860 และเพื่อขอใส่โฮเมอร์ที่ 8 237 00:11:22,860 --> 00:11:25,151 >> ตอนนี้เราสับและแม็กกี้ ผลตอบแทนที่ 3 ขอบคุณพระเจ้า 238 00:11:25,151 --> 00:11:26,650 เราสามารถที่จะเพียงแค่ใส่แม็กกี้มี 239 00:11:26,650 --> 00:11:29,070 เราไม่ได้มีการดำเนินการใด ๆ การเรียงลำดับของละเอียดที่ 240 00:11:29,070 --> 00:11:32,000 ตอนนี้เราสับร์จและ มาร์จยังผลตอบแทน 6 241 00:11:32,000 --> 00:11:39,560 >> ดี 6 เต็ม 7 เต็ม 8 เต็ม 9 สิ่งที่ถูกต้องขอบคุณพระเจ้าที่ 9 เป็นที่ว่างเปล่า 242 00:11:39,560 --> 00:11:41,600 ผมจะสามารถนำมาร์จที่ 9 243 00:11:41,600 --> 00:11:45,280 แล้วเราจะเห็นว่าเราจะเริ่มต้น จะมีปัญหาที่ตอนนี้เราอยู่นี้ 244 00:11:45,280 --> 00:11:48,780 เริ่มต้นที่จะยืดชนิดสิ่ง ของที่อยู่ห่างไกลจากรหัสกัญชาของพวกเขา 245 00:11:48,780 --> 00:11:52,960 และที 1 นั้นเฉลี่ย กรณีเป็นเวลาอย่างต่อเนื่อง 246 00:11:52,960 --> 00:11:56,560 เริ่มที่จะได้รับ more-- เล็ก ๆ น้อย ๆ เริ่มที่จะมีแนวโน้มน้อยมาก 247 00:11:56,560 --> 00:11:58,050 ต่อทีของ n 248 00:11:58,050 --> 00:12:01,270 เรากำลังเริ่มที่จะสูญเสีย ประโยชน์ของตารางแฮช 249 00:12:01,270 --> 00:12:03,902 >> ปัญหาที่เราเพิ่งเห็นนี้ เป็นสิ่งที่เรียกว่าการจัดกลุ่ม 250 00:12:03,902 --> 00:12:06,360 และสิ่งที่ไม่ดีจริงๆเกี่ยวกับ การจัดกลุ่มคือว่าเมื่อคุณในขณะนี้ 251 00:12:06,360 --> 00:12:09,606 มีสององค์ประกอบที่มีเคียง อีกด้านหนึ่งก็จะทำให้มันยิ่งมีโอกาสมากขึ้น 252 00:12:09,606 --> 00:12:11,480 คุณมีคู่ โอกาสที่คุณจะ 253 00:12:11,480 --> 00:12:13,516 ที่จะมีการปะทะกันอีก กับกลุ่มที่ 254 00:12:13,516 --> 00:12:14,890 และคลัสเตอร์จะเติบโตโดยหนึ่ง 255 00:12:14,890 --> 00:12:19,640 และคุณจะทำให้การเจริญเติบโตและการเจริญเติบโต ความน่าจะเป็นของการมีการปะทะกัน 256 00:12:19,640 --> 00:12:24,470 และในที่สุดก็จะเป็นเพียงไม่ดีเท่า ที่จะไม่จัดเรียงข้อมูลที่ทุกคน 257 00:12:24,470 --> 00:12:27,590 >> ปัญหาอื่น ๆ ก็คือเรา ยังคงและเพื่อให้ห่างไกลได้ถึงจุดนี้ 258 00:12:27,590 --> 00:12:30,336 เราได้รับเพียงแค่การจัดเรียงของ เข้าใจสิ่งที่ตารางแฮชคือ 259 00:12:30,336 --> 00:12:31,960 เรายังคงมีเพียง 10 ห้องพักสำหรับสตริง 260 00:12:31,960 --> 00:12:37,030 ถ้าเราต้องการที่จะยังคงสับ พลเมืองของสปริงฟิลด์, 261 00:12:37,030 --> 00:12:38,790 เราเท่านั้นที่จะได้รับ 10 ของพวกเขาในการมี 262 00:12:38,790 --> 00:12:42,619 และถ้าเราพยายามเพิ่ม 11 หรือ 12 เราไม่ได้มีสถานที่ที่จะนำพวกเขา 263 00:12:42,619 --> 00:12:45,660 เราก็อาจจะมีการหมุนไปรอบ ๆ ใน วงการพยายามที่จะหาจุดที่ว่างเปล่า 264 00:12:45,660 --> 00:12:49,000 และเราอาจจะได้รับการติด ในวง จำกัด 265 00:12:49,000 --> 00:12:51,810 >> ดังนั้นการจัดเรียงของยืมกับความคิดนี้ ของสิ่งที่เรียกว่าการผูกมัด 266 00:12:51,810 --> 00:12:55,790 และนี่คือที่ที่เรากำลังจะนำมา รายการที่เชื่อมโยงกลับเข้ามาในภาพ 267 00:12:55,790 --> 00:13:01,300 เกิดอะไรขึ้นถ้าแทนการจัดเก็บเพียง ข้อมูลตัวเองในอาร์เรย์ 268 00:13:01,300 --> 00:13:04,471 ทุกองค์ประกอบของอาร์เรย์จะทำได้ ถือหลายชิ้นของข้อมูล? 269 00:13:04,471 --> 00:13:05,970 ดีที่ไม่ได้ทำให้รู้สึกใช่มั้ย? 270 00:13:05,970 --> 00:13:09,280 เรารู้ว่าอาร์เรย์สามารถ hold-- แต่ละองค์ประกอบของอาร์เรย์ 271 00:13:09,280 --> 00:13:12,930 สามารถเก็บชิ้นเดียว ข้อมูลของชนิดข้อมูลที่ 272 00:13:12,930 --> 00:13:16,750 >> แต่ถ้าว่าชนิดข้อมูล เป็นรายการที่เชื่อมโยงใช่มั้ย? 273 00:13:16,750 --> 00:13:19,830 ดังนั้นสิ่งที่ถ้าทุกคน องค์ประกอบของอาร์เรย์เป็น 274 00:13:19,830 --> 00:13:22,790 ชี้ไปที่หัวของรายการที่เชื่อมโยงหรือไม่ 275 00:13:22,790 --> 00:13:24,680 และจากนั้นเราสามารถสร้าง บรรดารายการที่เชื่อมโยง 276 00:13:24,680 --> 00:13:27,120 และการเติบโตของพวกเขาโดยพล เพราะช่วยให้รายการที่เชื่อมโยง 277 00:13:27,120 --> 00:13:32,090 เราเติบโตและหดตัวมากขึ้น มีความยืดหยุ่นกว่าอาร์เรย์ไม่ 278 00:13:32,090 --> 00:13:34,210 ดังนั้นสิ่งที่ถ้าตอนนี้เราใช้ เราใช้ประโยชน์จากนี้ใช่มั้ย? 279 00:13:34,210 --> 00:13:37,760 เราเริ่มที่จะเติบโตโซ่เหล่านี้ ออกจากสถานที่เหล่านี้อาร์เรย์ 280 00:13:37,760 --> 00:13:40,740 >> ตอนนี้เราสามารถให้พอดีกับที่ไม่มีที่สิ้นสุด ปริมาณของข้อมูลหรือไม่ได้ไม่มีที่สิ้นสุด 281 00:13:40,740 --> 00:13:44,170 จำนวนข้อของ ข้อมูลลงในตารางแฮชของเรา 282 00:13:44,170 --> 00:13:47,760 โดยที่ไม่เคยทำงานเป็น ปัญหาที่เกิดขึ้นจากการปะทะกัน 283 00:13:47,760 --> 00:13:50,740 เราได้ตัดออกยัง การจัดกลุ่มโดยการทำเช่นนี้ 284 00:13:50,740 --> 00:13:54,380 และที่ดีที่เรารู้ว่าเมื่อเราใส่ เข้าไปในรายการที่เชื่อมโยงถ้าคุณจำได้ 285 00:13:54,380 --> 00:13:57,779 จากวิดีโอของเราในรายการที่เชื่อมโยงโดยลำพัง รายการที่เชื่อมโยงและรายการที่เชื่อมโยงทวีคูณ 286 00:13:57,779 --> 00:13:59,070 จะดำเนินการอย่างต่อเนื่องเวลา 287 00:13:59,070 --> 00:14:00,710 เราเพียงแค่เพิ่มไปด้านหน้า 288 00:14:00,710 --> 00:14:04,400 >> และสำหรับขึ้นดูดีเรารู้ ที่ดูในรายการที่เชื่อมโยง 289 00:14:04,400 --> 00:14:05,785 อาจจะมีปัญหาใช่มั้ย? 290 00:14:05,785 --> 00:14:07,910 เรามีการค้นหาผ่าน มันตั้งแต่ต้นจนจบ 291 00:14:07,910 --> 00:14:10,460 ไม่มีเป็นแบบสุ่ม ในการเข้าถึงรายการที่เชื่อมโยง 292 00:14:10,460 --> 00:14:15,610 แต่ถ้าแทนที่จะมีการเชื่อมโยงอย่างใดอย่างหนึ่ง รายการที่ค้นหาจะเป็นโอ n, 293 00:14:15,610 --> 00:14:19,590 ตอนนี้เรามี 10 รายการที่เชื่อมโยง หรือ 1,000 รายการที่เชื่อมโยง 294 00:14:19,590 --> 00:14:24,120 ตอนนี้ก็โอ n หารด้วย 10 หรือโอ n หารด้วย 1,000 295 00:14:24,120 --> 00:14:26,940 >> และในขณะที่เรากำลังพูดถึง ในทางทฤษฎีเกี่ยวกับความซับซ้อน 296 00:14:26,940 --> 00:14:30,061 เราคงไม่สนใจในความเป็นจริง โลกสิ่งเหล่านี้สำคัญจริง 297 00:14:30,061 --> 00:14:30,560 ใช่มั้ย? 298 00:14:30,560 --> 00:14:33,080 เราจริงจะแจ้งให้ทราบ ที่เกิดเหตุการณ์นี้ 299 00:14:33,080 --> 00:14:36,610 เพื่อให้ทำงานได้ 10 ครั้งได้เร็วขึ้น หรือ 1,000 ครั้งได้เร็วขึ้น 300 00:14:36,610 --> 00:14:41,570 เพราะเรากำลังกระจายยาว ห่วงโซ่ทั่ว 1,000 โซ่ขนาดเล็ก 301 00:14:41,570 --> 00:14:45,090 ดังนั้นเวลาที่เราต้องค้นหาแต่ละ ผ่านทางหนึ่งของกลุ่มคนที่เราสามารถ 302 00:14:45,090 --> 00:14:50,290 ไม่สนใจ 999 โซ่เราไม่ดูแล เกี่ยวกับและค้นหาเพียงหนึ่ง 303 00:14:50,290 --> 00:14:53,220 >> ซึ่งเป็นค่าเฉลี่ย จะสั้นกว่า 1,000 ครั้ง 304 00:14:53,220 --> 00:14:56,460 และเพื่อให้เรายังคงมีการจัดเรียงของ พุ่งไปทางนี้กรณีเฉลี่ย 305 00:14:56,460 --> 00:15:01,610 ของการเป็นเวลาอย่างต่อเนื่อง แต่ เพียงเพราะเราจะใช้ประโยชน์จาก 306 00:15:01,610 --> 00:15:03,730 หารด้วยปัจจัยคงที่ขนาดใหญ่ 307 00:15:03,730 --> 00:15:05,804 ลองดูวิธีนี้อาจจะ จริงการมองว่า 308 00:15:05,804 --> 00:15:08,720 ดังนั้นนี่คือตารางแฮชที่เรามี ก่อนที่เราจะประกาศตารางแฮชที่ 309 00:15:08,720 --> 00:15:10,270 มีความสามารถในการจัดเก็บสาย 10 310 00:15:10,270 --> 00:15:11,728 เราไม่ได้ไปทำอีกต่อไป 311 00:15:11,728 --> 00:15:13,880 เรารู้อยู่แล้ว ข้อ จำกัด ของวิธีการที่ 312 00:15:13,880 --> 00:15:20,170 ตอนนี้ตารางแฮชของเราเป็นไปได้ อาร์เรย์ของโหนด 10 ตัวชี้ 313 00:15:20,170 --> 00:15:22,120 หัวของรายการที่เชื่อมโยง 314 00:15:22,120 --> 00:15:23,830 >> และตอนนี้ก็เป็นโมฆะ 315 00:15:23,830 --> 00:15:26,170 แต่ละคนหนึ่งในบรรดา 10 ตัวชี้เป็นโมฆะ 316 00:15:26,170 --> 00:15:29,870 ไม่มีอะไรที่เป็นของเรา สับตารางในขณะนี้ 317 00:15:29,870 --> 00:15:32,690 >> ตอนนี้ขอเริ่มต้นที่จะนำบางส่วน สิ่งที่เป็นตารางแฮชนี้ 318 00:15:32,690 --> 00:15:35,440 และให้ดูว่าวิธีนี้คือ ไปเพื่อประโยชน์ของเรานิด ๆ หน่อย ๆ 319 00:15:35,440 --> 00:15:36,760 ตอนนี้ขอกัญชาโจอี้ 320 00:15:36,760 --> 00:15:40,210 เราจะจะทำงานสตริงโจอี้ผ่าน ฟังก์ชั่นและกัญชาเรากลับ 6 321 00:15:40,210 --> 00:15:41,200 ดีสิ่งที่เราจะทำตอนนี้หรือไม่ 322 00:15:41,200 --> 00:15:44,090 >> ดีตอนนี้ทำงานร่วมกับรายการที่เชื่อมโยง เราไม่ได้ทำงานกับอาร์เรย์ 323 00:15:44,090 --> 00:15:45,881 และเมื่อเรากำลังทำงาน รายการที่เชื่อมโยงกับเรา 324 00:15:45,881 --> 00:15:49,790 รู้ว่าเราจะต้องเริ่มต้นแบบไดนามิก การจัดสรรพื้นที่และการสร้างเครือข่าย 325 00:15:49,790 --> 00:15:54,020 นั่นคือการจัดเรียงของ how-- เหล่านั้นเป็นหลัก องค์ประกอบของการสร้างรายการที่เชื่อมโยง 326 00:15:54,020 --> 00:15:57,670 ดังนั้นขอแบบไดนามิก จัดสรรพื้นที่สำหรับโจอี้ 327 00:15:57,670 --> 00:16:00,390 และจากนั้นให้เพิ่มให้เขาห่วงโซ่ 328 00:16:00,390 --> 00:16:03,170 >> ดังนั้นตอนนี้ดูสิ่งที่เราทำ 329 00:16:03,170 --> 00:16:06,440 เมื่อเราสับโจอี้เราได้ hashcode 6 330 00:16:06,440 --> 00:16:11,790 ตอนนี้ตัวชี้ที่ตำแหน่ง 6 อาร์เรย์ ชี้ไปที่หัวของรายการที่เชื่อมโยง 331 00:16:11,790 --> 00:16:14,900 และตอนนี้มันเป็นเพียง องค์ประกอบของรายการที่เชื่อมโยง 332 00:16:14,900 --> 00:16:18,350 และโหนดในว่า รายการที่เชื่อมโยงเป็นโจอี้ 333 00:16:18,350 --> 00:16:22,300 >> ดังนั้นหากเราต้องการที่จะมองขึ้นโจอี้ ต่อมาเราก็สับโจอี้อีกครั้ง 334 00:16:22,300 --> 00:16:26,300 เราได้รับ 6 อีกครั้งเพราะเรา ฟังก์ชันแฮชคือกำหนด 335 00:16:26,300 --> 00:16:30,400 และจากนั้นเราเริ่มต้นที่หัว ของรายการที่เชื่อมโยงชี้ 336 00:16:30,400 --> 00:16:33,360 ไปตามสถานที่อาร์เรย์ 6 และเราสามารถย้ำ 337 00:16:33,360 --> 00:16:35,650 ข้ามที่พยายามที่จะหาโจอี้ 338 00:16:35,650 --> 00:16:37,780 และถ้าเราสร้างของเรา สับตารางได้อย่างมีประสิทธิภาพ 339 00:16:37,780 --> 00:16:41,790 และการทำงานของเราได้อย่างมีประสิทธิภาพกัญชา ในการเผยแพร่ข้อมูลที่ดี 340 00:16:41,790 --> 00:16:45,770 โดยเฉลี่ยแต่ละคนเชื่อมโยง รายชื่อที่ทุกสถานที่อาร์เรย์ 341 00:16:45,770 --> 00:16:50,110 จะเป็นขนาดของ 10/01 ถ้าเรา เพิ่งมีเป็นอย่างมากที่เดียว 342 00:16:50,110 --> 00:16:51,650 รายการที่เชื่อมโยงกับทุกสิ่งที่อยู่ในนั้น 343 00:16:51,650 --> 00:16:55,670 >> ถ้าเราจัดจำหน่ายที่ใหญ่เชื่อมโยง รายการใน 10 รายการที่เชื่อมโยง 344 00:16:55,670 --> 00:16:57,760 แต่ละรายการจะมีขนาด 1/10 345 00:16:57,760 --> 00:17:01,432 และทำให้เร็วขึ้น 10 เท่า การค้นหาผ่าน 346 00:17:01,432 --> 00:17:02,390 ถ้าอย่างนั้นเราทำเช่นนี้อีกครั้ง 347 00:17:02,390 --> 00:17:04,290 ตอนนี้ขอให้รอสส์สับ 348 00:17:04,290 --> 00:17:07,540 >> และขอบอกว่ารอสส์เมื่อเราทำอย่างนั้น รหัสกัญชาที่เราได้รับกลับมาคือ 2 349 00:17:07,540 --> 00:17:10,630 ดีตอนนี้เราแบบไดนามิกจัดสรร โหนดใหม่ที่เราใส่รอสส์ในโหนดที่ 350 00:17:10,630 --> 00:17:14,900 และเราบอกว่าตอนนี้สถานที่อาร์เรย์ 2 แทนการชี้ให้เป็นโมฆะ, 351 00:17:14,900 --> 00:17:18,579 ชี้ไปที่หัวของการเชื่อมโยง รายการที่มีโหนดเพียงอย่างเดียวคือรอสส์ 352 00:17:18,579 --> 00:17:22,660 และเราสามารถทำในครั้งนี้อีกหนึ่งเรา สามารถสับราเชลและได้รับ hashcode 4 353 00:17:22,660 --> 00:17:25,490 malloc โหนดใหม่ใส่ในราเชล โหนดและกล่าวตั้งแถว 354 00:17:25,490 --> 00:17:27,839 4 ในขณะนี้ชี้ไปที่หัว ของรายการที่เชื่อมโยงที่มี 355 00:17:27,839 --> 00:17:31,420 องค์ประกอบที่จะเกิดขึ้นจะเป็นราเชล 356 00:17:31,420 --> 00:17:33,470 >> ตกลง แต่สิ่งที่เกิดขึ้นถ้า เรามีการปะทะกันหรือไม่? 357 00:17:33,470 --> 00:17:38,560 ลองมาดูวิธีการที่เราจัดการกับการชนกัน โดยใช้วิธีการผูกมัดแยกต่างหาก 358 00:17:38,560 --> 00:17:39,800 ลองกัญชาพีบี 359 00:17:39,800 --> 00:17:41,094 เราได้รับ hashcode 6 360 00:17:41,094 --> 00:17:44,010 ในตัวอย่างก่อนหน้านี้ของเราที่เราเป็นเพียงแค่ การจัดเก็บสตริงในอาร์เรย์ 361 00:17:44,010 --> 00:17:45,980 นี่เป็นปัญหา 362 00:17:45,980 --> 00:17:48,444 >> เราไม่ต้องการที่จะบังคับ โจอี้และเราได้อยู่แล้ว 363 00:17:48,444 --> 00:17:51,110 เห็นได้ว่าเราจะได้รับการจัดกลุ่มบาง ปัญหาที่เกิดขึ้นถ้าเราพยายามและขั้นตอน 364 00:17:51,110 --> 00:17:52,202 และผ่านการสอบสวน 365 00:17:52,202 --> 00:17:54,660 แต่ถ้าเราเพียงแค่ชนิดของ การรักษาด้วยวิธีนี้เหมือนกันใช่มั้ย? 366 00:17:54,660 --> 00:17:57,440 ก็เช่นเดียวกับการเพิ่มองค์ประกอบ ไปที่หัวของรายการที่เชื่อมโยง 367 00:17:57,440 --> 00:18:00,220 ขอเพียงพื้นที่ malloc สำหรับพีบี 368 00:18:00,220 --> 00:18:04,764 >> เราจะบอกว่าพีบีจุดชี้ต่อไป ที่ศีรษะเก่าของรายการที่เชื่อมโยง 369 00:18:04,764 --> 00:18:07,180 และจากนั้นเพียง 6 ชี้ไปที่ หัวใหม่ของรายการที่เชื่อมโยง 370 00:18:07,180 --> 00:18:10,150 และตอนนี้ดูเราได้เปลี่ยนพีบีใน 371 00:18:10,150 --> 00:18:14,210 ตอนนี้เราสามารถเก็บสอง องค์ประกอบที่มี hashcode 6 372 00:18:14,210 --> 00:18:17,170 และเราไม่ได้มีปัญหาใด ๆ 373 00:18:17,170 --> 00:18:20,147 >> ที่สวยมากทั้งหมด มีความผูกพัน 374 00:18:20,147 --> 00:18:21,980 และผูกมัดแน่นอน วิธีการที่เป็น 375 00:18:21,980 --> 00:18:27,390 จะมีประสิทธิภาพมากที่สุดสำหรับคุณถ้า คุณกำลังจัดเก็บข้อมูลในตารางแฮช 376 00:18:27,390 --> 00:18:30,890 แต่การรวมกันนี้ อาร์เรย์และรายการที่เชื่อมโยง 377 00:18:30,890 --> 00:18:36,080 กันในรูปแบบตารางแฮชจริงๆ อย่างรวดเร็วช่วยเพิ่มความสามารถของคุณ 378 00:18:36,080 --> 00:18:40,550 ในการจัดเก็บข้อมูลจำนวนมากและ ได้อย่างรวดเร็วและมีประสิทธิภาพการค้นหา 379 00:18:40,550 --> 00:18:41,630 ผ่านข้อมูลนั้น 380 00:18:41,630 --> 00:18:44,150 >> ยังคงมีอีกหนึ่ง โครงสร้างข้อมูลออกมี 381 00:18:44,150 --> 00:18:48,700 ที่ยังอาจจะเล็กน้อย ที่ดีกว่าในแง่ของการรับประกัน 382 00:18:48,700 --> 00:18:51,920 ที่เราแทรกลบและ มองขึ้นเวลาได้เร็วยิ่งขึ้น 383 00:18:51,920 --> 00:18:55,630 และเราจะเห็นว่าในวิดีโอบนพยายาม 384 00:18:55,630 --> 00:18:58,930 ฉันลอยด์ดั๊กนี้เป็น CS50 385 00:18:58,930 --> 00:19:00,214