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
Theta δεν έχουμε πραγματικά συζητηθεί,
αλλά θήτα είναι μόνο η μέση περίπτωση,

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
Και έτσι θέλουμε μόνο να χρησιμοποιήσετε hash
πίνακες, αν εμείς δεν ενδιαφερόμαστε για

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
Και ότι η λειτουργία hash πρόκειται να
να επιστρέψει κάποια μη αρνητικός ακέραιος, η οποία

67
00:03:11,760 --> 00:03:14,870
που συνήθως ονομάζουμε μια hashCode, εντάξει;

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
και μόλις αρχίσουμε με τα βασικά ενός
hash πίνακα για να πάρει το κεφάλι σας γύρω από αυτό,

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
Και έτσι η επεξεργασία των δεδομένων είναι
και φτύνει έναν αριθμό, εντάξει;

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
>> Ας πούμε ότι θέλουμε να hash Ιωάννη.

82
00:03:59,320 --> 00:04:02,979
Έτσι ο Ιωάννης όσο και τα δεδομένα που θέλετε να εισάγετε
σε αυτό τον πίνακα hash κάπου.

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
>> Και ας πούμε ότι διατρέχουμε τον John
μέσω αυτής της συνάρτησης κατακερματισμού

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, γιατί αν hash John again--

91
00:04:22,050 --> 00:04:23,810
ας πούμε αργότερα
θέλετε να αναζητήσετε και να δείτε

92
00:04:23,810 --> 00:04:26,960
Γιάννης αν υπάρχει σε αυτό το hash
table-- το μόνο που χρειάζεται να κάνουμε

93
00:04:26,960 --> 00:04:30,310
είναι αυτό που τρέχει μέσα από το ίδιο hash
λειτουργία, να πάρει τον αριθμό 4 έξω,

94
00:04:30,310 --> 00:04:33,929
και να είναι σε θέση να βρείτε τον John
αμέσως στη δομή των δεδομένων μας.

95
00:04:33,929 --> 00:04:34,720
Αυτό είναι πολύ καλό.

96
00:04:34,720 --> 00:04:36,928
>> Ας πούμε ότι το κάνουμε τώρα αυτό
και πάλι, θέλουμε να hash Παύλου.

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
>> Έτσι, αυτό που κάνει ένα καλό
hash λειτουργία, σωστά;

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
Γι 'αυτό και δεν θέλετε να χρησιμοποιήσετε anything--
εμείς δεν περιλαμβάνουν τίποτα

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
Αν έχω περάσει Ιωάννη σε η
hash λειτουργία βγω 4.

127
00:05:52,870 --> 00:05:56,110
Θα πρέπει να είναι σε θέση να το κάνουμε αυτό 10.000
φορές και θα πάρω πάντα 4.

128
00:05:56,110 --> 00:06:00,810
Έτσι, δεν τυχαίων αριθμών αποτελεσματικά
μπορούν να συμμετέχουν σε hash μας tables--

129
00:06:00,810 --> 00:06:02,750
συναρτήσεις hash μας.

130
00:06:02,750 --> 00:06:05,750
>> Μια συνάρτηση κατακερματισμού θα πρέπει επίσης να
ομοιόμορφη κατανομή των δεδομένων.

131
00:06:05,750 --> 00:06:09,700
Εάν κάθε φορά που τρέχετε δεδομένων μέσω του
hash λειτουργία μπορείτε να πάρετε το hashCode 0,

132
00:06:09,700 --> 00:06:11,200
ότι δεν είναι πιθανώς τόσο μεγάλη, έτσι δεν είναι;

133
00:06:11,200 --> 00:06:14,600
Θέλετε πιθανώς σε μεγάλες
μια σειρά από κωδικούς hash.

134
00:06:14,600 --> 00:06:17,190
Επίσης, τα πράγματα μπορεί να εξαπλωθεί
καθ 'όλη τη τραπέζι.

135
00:06:17,190 --> 00:06:23,210
Και επίσης θα ήταν μεγάλη, αν πραγματικά
παρόμοια στοιχεία, όπως ο John και του Jonathan,

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
και την ανίχνευση όταν έχετε
φθάσει στο τέλος του string.

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
Έχω φτάσει στο τέλος του string.

152
00:07:07,185 --> 00:07:09,560
Και τότε θα πάω για να κρατήσει
επανάληψη μέσω αυτής της σειράς,

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
Δεν θέλω να πάρει hash
κωδικούς εφόσον σειρά μου είναι μεγέθους 10,

160
00:07:33,160 --> 00:07:35,712
Δεν θέλω να πάρει
από τους κωδικούς hash 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
Αλλά, όταν στην πραγματικότητα πρόκειται για
ξεκινήστε κατακερματισμός των δεδομένων και την αποθήκευσή του

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--
και όχι μόνο για hash

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
>> Εντάξει έτσι ας επανεξετάσουμε αυτό
hash πίνακα για ένα δευτερόλεπτο.

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
>> Τι θα συμβεί αν χασίς Ringo, και
Αποδεικνύεται ότι μετά την επεξεργασία

192
00:09:06,770 --> 00:09:14,000
ότι τα δεδομένα μέσω της συνάρτησης κατακερματισμού
Ringo παράγεται επίσης το 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
Και η σύγκρουση συμβαίνει όταν δύο
κομμάτια των δεδομένων που τρέχει μέσα από το ίδιο hash

197
00:09:26,460 --> 00:09:29,200
λειτουργία αποδώσει το ίδιο hashCode.

198
00:09:29,200 --> 00:09:32,850
Πιθανώς θα εξακολουθούν να θέλουν να πάρουν και οι δύο
κομμάτια των δεδομένων στον πίνακα hash,

199
00:09:32,850 --> 00:09:36,330
αλλιώς δεν θα έτρεχαν Ringo
αυθαίρετα μέσω της συνάρτησης κατακερματισμού.

200
00:09:36,330 --> 00:09:40,870
Εμείς προφανώς θέλουν να πάρουν
Ringo σε αυτή την σειρά.

201
00:09:40,870 --> 00:09:46,070
>> Πώς μπορούμε να το κάνουμε όμως, αν αυτός
και ο Paul τόσο απόδοση 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
>> Ας πούμε ότι έχουμε hash Bart.

219
00:10:42,540 --> 00:10:45,581
Έτσι, τώρα θα πάμε να τρέξει ένα νέο σύνολο
των χορδών μέσω της συνάρτησης κατακερματισμού,

220
00:10:45,581 --> 00:10:48,460
και τρέχουμε Bart μέσω του κατακερματισμού
λειτουργία, θα έχουμε hashCode 6.

221
00:10:48,460 --> 00:10:52,100
Θα ρίξουμε μια ματιά, βλέπουμε 6
άδειο, έτσι μπορούμε να βάλουμε εκεί Bart.

222
00:10:52,100 --> 00:10:55,410
>> Τώρα έχουμε hash Λίζα και ότι
δημιουργεί επίσης 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
Εμείς δεν μπορούμε να βάλουμε Lisa σε 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
>> Τώρα έχουμε hash Όμηρο και παίρνουμε 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
>> Τώρα έχουμε hash Μάγκι και
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
Τώρα έχουμε hash Μαρτζ, και
Marge επιστρέφει επίσης 6.

241
00:11:32,000 --> 00:11:39,560
>> Λοιπόν 6 είναι πλήρης, 7 είναι πλήρης, 8 είναι πλήρης,
9, εντάξει δόξα τω Θεώ, 9 είναι άδειο.

242
00:11:39,560 --> 00:11:41,600
Μπορώ να βάλω Marge στο 9.

243
00:11:41,600 --> 00:11:45,280
Ήδη μπορούμε να δούμε ότι αρχίζουμε
να έχουν αυτό το πρόβλημα, όπου τώρα είμαστε

244
00:11:45,280 --> 00:11:48,780
αρχίζουν να τεντώσει τα πράγματα είδος
του μακριά από τους κώδικες hash τους.

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
προς θήτα του ν.

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
Αν θέλουμε να συνεχίσουμε να hash
οι πολίτες του Σπρίνγκφιλντ,

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
Αλλά εάν αντί να έχουν ένα συνδεδεμένο
κατάλογο όπου η αναζήτηση θα είναι O Ν,

293
00:14:15,610 --> 00:14:19,590
τώρα έχουμε 10 συνδεδεμένες λίστες,
ή 1.000 συνδεδεμένες λίστες,

294
00:14:19,590 --> 00:14:24,120
τώρα είναι O Ν διαιρούμενο με το 10,
ή O Ν διαιρείται με 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
Τώρα πίνακα hash μας πρόκειται να είναι
μια σειρά από 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
Δεν υπάρχει τίποτα σε μας
hash πίνακα τώρα.

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
Ας τώρα hash Joey.

320
00:15:36,760 --> 00:15:40,210
Θα θα τρέξει το κορδόνι μέσα από Joey
μια συνάρτηση κατακερματισμού και επιστρέφουμε 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
Ας δυναμικά
διατεθεί χώρος για τον Joey,

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
Όταν hash Joey πήραμε το 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
Και ο κόμβος στο ότι
συνδεδεμένη λίστα είναι ο Joey.

333
00:16:18,350 --> 00:16:22,300
>> Έτσι, αν θα πρέπει να κοιτάζω προς τα πάνω τον Joey
αργότερα, εμείς απλά χασίς και πάλι Joey,

334
00:16:22,300 --> 00:16:26,300
έχουμε 6 και πάλι, επειδή μας
hash λειτουργία είναι αιτιοκρατική.

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
σε όλη ότι προσπαθεί να βρει τον Joey.

338
00:16:35,650 --> 00:16:37,780
Και αν χτίσουμε μας
hash πίνακα αποτελεσματικά,

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
θα είναι το 1/10 του μεγέθους του, αν
ακριβώς είχε ως ενιαίο τεράστιο

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
Ας τώρα hash Ross.

348
00:17:04,290 --> 00:17:07,540
>> Και ας πούμε Ross, όταν το κάνουμε αυτό
ο κώδικας κατακερματισμού παίρνουμε πίσω είναι 2.

349
00:17:07,540 --> 00:17:10,630
Καλά τώρα διαθέτουμε ένα δυναμικά
νέος κόμβος, βάζουμε Ross σε αυτόν τον κόμβο,

350
00:17:10,630 --> 00:17:14,900
και λέμε τώρα θέση πίνακα
2, αντί να δείχνουν σε null,

351
00:17:14,900 --> 00:17:18,579
επισημαίνει στο κεφάλι ενός συνδεδεμένου
κατάλογος των οποίων μόνο ο κόμβος είναι ο Ross.

352
00:17:18,579 --> 00:17:22,660
Και μπορούμε να το κάνουμε μία ακόμη φορά, εμείς
μπορεί hash Rachel και να πάρει hashCode 4.

353
00:17:22,660 --> 00:17:25,490
malloc ένα νέο κόμβο, βάλτε σε Rachel
ο κόμβος, και να πω μια θέση πίνακα

354
00:17:25,490 --> 00:17:27,839
4 σημεία τώρα στο κεφάλι
του οποίου η συνδεδεμένη λίστα

355
00:17:27,839 --> 00:17:31,420
μόνο στοιχείο που συμβαίνει να είναι Rachel.

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
Ας hash Φοίβη.

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
>> Δεν θέλουμε να κοπανάω
Joey, και έχουμε ήδη

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
μαζί για να σχηματίσουν έναν πίνακα hash πραγματικά
βελτιώνει δραματικά την ικανότητα σας

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
Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.

385
00:18:58,930 --> 00:19:00,214