1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> რობ Bowden: Hi.

3
00:00:13,050 --> 00:00:16,210
მე რობ, და მოდით hash
ეს გამოსავალი.

4
00:00:16,210 --> 00:00:20,070
ასე რომ, აქ ჩვენ ვაპირებთ განხორციელება
ზოგადი hash მაგიდასთან.

5
00:00:20,070 --> 00:00:24,090
ჩვენ ვხედავთ, რომ struct კვანძის ჩვენი hash
მაგიდა აპირებს გამოიყურებოდეს მოსწონს ეს.

6
00:00:24,090 --> 00:00:28,710
ასე რომ, ის აპირებს აქვს char სიტყვა
მასივი ზომა სიგრძე პლუს 1.

7
00:00:28,710 --> 00:00:32,259
ნუ დაგავიწყდებათ 1 წლიდან მაქსიმალური
სიტყვა ლექსიკონი 45

8
00:00:32,259 --> 00:00:35,110
პერსონაჟი, და შემდეგ ჩვენ ვაპირებთ
უნდა ერთი ზედმეტი ხასიათი

9
00:00:35,110 --> 00:00:37,070
backslash 0.

10
00:00:37,070 --> 00:00:40,870
>> და მაშინ ჩვენი hash table თითოეულ
bucket აპირებს შესანახად

11
00:00:40,870 --> 00:00:42,320
დაკავშირებული სიაში კვანძების.

12
00:00:42,320 --> 00:00:44,420
ჩვენ არ ვაკეთებთ ხაზოვანი საცდელი აქ.

13
00:00:44,420 --> 00:00:48,430
და რათა დააკავშიროს მომდევნო
ელემენტს bucket, ჩვენ გვჭირდება

14
00:00:48,430 --> 00:00:51,110
struct კვანძის * შემდეგი.

15
00:00:51,110 --> 00:00:53,090
ასე რომ რა კვანძის ჰგავს.

16
00:00:53,090 --> 00:00:56,180
ახლა, აქ არის დეკლარაცია
ჩვენი hash მაგიდასთან.

17
00:00:56,180 --> 00:01:01,910
ის აპირებს აქვს 16.384 თაიგულების, მაგრამ
რომ ნომერი ნამდვილად არ აქვს.

18
00:01:01,910 --> 00:01:05,450
და ბოლოს, ჩვენ ვაპირებთ აქვს
გლობალური ცვლადი hashtable_size, რომელიც

19
00:01:05,450 --> 00:01:08,640
აპირებს დაიწყოს off როგორც 0 და ეს
აპირებს ტრეკზე რამდენი სიტყვა

20
00:01:08,640 --> 00:01:10,080
იყო ჩვენი ლექსიკონი.

21
00:01:10,080 --> 00:01:10,760
ყველა უფლება.

22
00:01:10,760 --> 00:01:13,190
>> მოდით შევხედოთ დატვირთვა.

23
00:01:13,190 --> 00:01:16,390
ასე რომ შეამჩნია, რომ დატვირთვის,
ის დააბრუნებს bool.

24
00:01:16,390 --> 00:01:20,530
თქვენ დაბრუნდება ნამდვილი, თუ ეს იყო წარმატებით
დატვირთული და ცრუ სხვაგვარად.

25
00:01:20,530 --> 00:01:23,990
და ეს ხდება const char * star
ლექსიკონი, რომელიც ლექსიკონი

26
00:01:23,990 --> 00:01:25,280
რომ ჩვენ გვინდა გახსნა.

27
00:01:25,280 --> 00:01:27,170
ასე რომ, პირველი, რაც
ჩვენ ვაპირებთ, რომ გავაკეთოთ.

28
00:01:27,170 --> 00:01:30,420
ჩვენ ვაპირებთ fopen ლექსიკონი
კითხულობს, და ჩვენ ვაპირებთ აქვს

29
00:01:30,420 --> 00:01:34,700
დარწმუნდით, რომ ეს შეძლო ასე რომ, თუ
იგი დაბრუნდა NULL, მაშინ ჩვენ არ

30
00:01:34,700 --> 00:01:37,440
წარმატებით გახსნა ლექსიკონი
და ჩვენ გვჭირდება დაბრუნების ცრუ.

31
00:01:37,440 --> 00:01:41,580
>> მაგრამ თუ გავითვალისწინებთ, რომ ეს წარმატებით
ღია, მაშინ ჩვენ გვინდა წაიკითხოთ

32
00:01:41,580 --> 00:01:42,400
ლექსიკონი.

33
00:01:42,400 --> 00:01:46,210
გააგრძელეთ looping სანამ ჩვენ გამოძებნოს
მიზეზი შესვენება out ამ

34
00:01:46,210 --> 00:01:47,570
loop, რომელიც ჩვენ დავინახავთ.

35
00:01:47,570 --> 00:01:51,780
გააგრძელეთ looping, და ახლა ჩვენ ვაპირებთ
to malloc ერთი კვანძის.

36
00:01:51,780 --> 00:01:56,800
და რა თქმა უნდა, ჩვენ უნდა შეცდომა შემოწმება
ერთხელ ასე რომ, თუ mallocing არ გავიდა

37
00:01:56,800 --> 00:02:00,660
და გვინდა, რომ განიტვირთოს ნებისმიერი კვანძის რომ ჩვენ
მოხდა malloc ადრე, დახუროს

38
00:02:00,660 --> 00:02:02,590
ლექსიკონი და დაბრუნების ცრუ.

39
00:02:02,590 --> 00:02:07,440
>> მაგრამ იგნორირება, რომ ვთქვათ, ჩვენ
შეძლო, მაშინ ჩვენ გვინდა გამოვიყენოთ fscanf

40
00:02:07,440 --> 00:02:12,400
წაკითხვის ერთი სიტყვა ჩვენი
ლექსიკონი ჩვენს კვანძში.

41
00:02:12,400 --> 00:02:17,310
ასე მახსოვს, რომ შესვლის> სიტყვა არის char
სიტყვა ბუფერის ზომა სიგრძე პლუს

42
00:02:17,310 --> 00:02:20,300
ერთი, რომ ჩვენ ვაპირებთ
შესანახად სიტყვა შემოსული

43
00:02:20,300 --> 00:02:25,280
ასე fscanf დაბრუნებას აპირებს 1 მანამ,
რადგან შეძლო წარმატებით წაიკითხა

44
00:02:25,280 --> 00:02:26,750
სიტყვა ფაილი.

45
00:02:26,750 --> 00:02:31,030
>> თუ არც შეცდომა ხდება, ან ჩვენ მივაღწევთ
ბოლოს ფაილი, ის არ

46
00:02:31,030 --> 00:02:34,950
დაბრუნდება 1 ამ შემთხვევაში, თუ იგი არ
დაბრუნდება 1, ჩვენ საბოლოოდ აპირებს დაარღვიოს

47
00:02:34,950 --> 00:02:37,280
აქედან ხოლო loop.

48
00:02:37,280 --> 00:02:42,770
ასე რომ, ჩვენ ვხედავთ, რომ ერთხელ ჩვენ წარმატებით
წაიკითხა სიტყვა შევიდა

49
00:02:42,770 --> 00:02:48,270
შესვლის> სიტყვა, მაშინ ჩვენ ვაპირებთ hash
რომ სიტყვა ჩვენი ქეშირების ფუნქცია.

50
00:02:48,270 --> 00:02:49,580
მოდით შევხედოთ
ქეშირების ფუნქცია.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> ასე, რომ თქვენ ნამდვილად არ უნდა
ამის გაგება.

53
00:02:55,610 --> 00:02:59,460
და რეალურად, ჩვენ უბრალოდ გამოყვანილია ამ
ქეშირების ფუნქცია ინტერნეტში.

54
00:02:59,460 --> 00:03:04,010
ერთადერთი, რაც თქვენ უნდა აღიაროს არის
რომ ეს იღებს const char * სიტყვა,

55
00:03:04,010 --> 00:03:08,960
ამიტომ აღების სიმებიანი, როგორც შეყვანის და
დაბრუნების unsigned int როგორც გამომავალი.

56
00:03:08,960 --> 00:03:12,360
ასე რომ ყველა ქეშირების ფუნქცია, არის ის
იღებს შეყვანის, ეს გაძლევთ

57
00:03:12,360 --> 00:03:14,490
ინდექსი შევიდა hash მაგიდასთან.

58
00:03:14,490 --> 00:03:18,530
გაითვალისწინეთ, რომ ჩვენ მოდინგი მიერ NUM_BUCKETS
ასე რომ, hash ღირებულება დაბრუნდა

59
00:03:18,530 --> 00:03:21,730
რეალურად არის ინდექსი შევიდა hash table
და არ index მიღმა

60
00:03:21,730 --> 00:03:24,320
ფარგლებში მასივი.

61
00:03:24,320 --> 00:03:27,855
>> ასე რომ, თუ გავითვალისწინებთ, რომ ქეშირების ფუნქცია, ჩვენ ვაპირებთ
to hash სიტყვა, რომელიც ჩვენ ვკითხულობთ

62
00:03:27,855 --> 00:03:31,700
საწყისი ლექსიკონი და მაშინ ჩვენ ვაპირებთ
გამოყენება, რომელსაც აქვს ჩასასმელად

63
00:03:31,700 --> 00:03:33,750
შესვლის hash მაგიდასთან.

64
00:03:33,750 --> 00:03:38,830
ახლა, hashtable hash მიმდინარე
დაკავშირებული სიაში hash მაგიდა და

65
00:03:38,830 --> 00:03:41,410
ეს ძალიან შესაძლებელია, რომ მხოლოდ NULL.

66
00:03:41,410 --> 00:03:45,640
გვინდა ჩადეთ ჩვენი შესვლის დროს
დაწყებული ამ უკავშირდება სია, და ა.შ.

67
00:03:45,640 --> 00:03:48,910
ჩვენ ვაპირებთ, რომ ჩვენი დღევანდელი შესვლის
მიუთითებენ რა hash table გაკეთებული

68
00:03:48,910 --> 00:03:54,030
რაოდენობა და შემდეგ ჩვენ ვაპირებთ შესანახად
ამ hash მაგიდაზე hash

69
00:03:54,030 --> 00:03:55,350
მიმდინარე ჩანაწერი.

70
00:03:55,350 --> 00:03:59,320
>> ასე რომ, ეს ორი ხაზი წარმატებით ჩადეთ
შესვლის დასაწყისში

71
00:03:59,320 --> 00:04:02,270
უკავშირდება სია იმ ინდექსი
ამ hash მაგიდასთან.

72
00:04:02,270 --> 00:04:04,900
მას შემდეგ, რაც ჩვენ გავაკეთეთ, რომ, ჩვენ ვიცით,
რომ ჩვენ ვნახეთ ერთი სიტყვა

73
00:04:04,900 --> 00:04:07,800
ლექსიკონი და ჩვენ ნამატი ერთხელ.

74
00:04:07,800 --> 00:04:13,960
ასე რომ, ჩვენ აკეთეთ, რომ სანამ fscanf
საბოლოოდ ბრუნდება რაღაც არასამთავრობო 1 at

75
00:04:13,960 --> 00:04:18,560
სადაც წერტილი გვახსოვდეს, რომ ჩვენ უნდა
თავისუფალი შესვლის, ასე რომ აქ, ჩვენ malloced

76
00:04:18,560 --> 00:04:21,329
შესვლის და ჩვენ შევეცადეთ წავიკითხე რაღაც
საწყისი ლექსიკონი.

77
00:04:21,329 --> 00:04:24,110
და ჩვენ არ წარმატებით წაკითხული
რაღაც ლექსიკონი, რომელშიც

78
00:04:24,110 --> 00:04:27,440
წინააღმდეგ შემთხვევაში, ჩვენ უნდა გავათავისუფლოთ შესვლის, რომ ჩვენ
არასოდეს რეალურად ამოქმედებული hash table

79
00:04:27,440 --> 00:04:29,110
და საბოლოოდ დაარღვიოს.

80
00:04:29,110 --> 00:04:32,750
>> მას შემდეგ, რაც ჩვენ შესვენება out, ჩვენ უნდა დაინახოს, ასევე,
არც ჩვენ შესვენება out რადგან იქ

81
00:04:32,750 --> 00:04:35,840
შეცდომა კითხულობს საწყისი ფაილი, ან
არც ჩვენ შესვენება, რადგან ჩვენ მივაღწიეთ

82
00:04:35,840 --> 00:04:37,120
ბოლოს ფაილი?

83
00:04:37,120 --> 00:04:40,150
იყო თუ არა შეცდომა, მაშინ ჩვენ გვინდა
დაბრუნების ცრუ, რადგან დატვირთვა არ

84
00:04:40,150 --> 00:04:43,260
წარმატების მიღწევა, და ამ პროცესში, ჩვენ გვინდა
განიტვირთოს ყველა ის სიტყვა, ვკითხულობთ

85
00:04:43,260 --> 00:04:45,670
და დახუროს ლექსიკონი ფაილი.

86
00:04:45,670 --> 00:04:48,740
ვთქვათ, ჩვენ არ გამოუვათ, მაშინ ჩვენ უბრალოდ
მაინც უნდა დახუროს ლექსიკონი

87
00:04:48,740 --> 00:04:51,970
ფაილი, და საბოლოოდ იქნება TRUE, რადგან
ჩვენ წარმატებით დატვირთული

88
00:04:51,970 --> 00:04:53,040
ლექსიკონი.

89
00:04:53,040 --> 00:04:54,420
და რომ ეს დატვირთვა.

90
00:04:54,420 --> 00:04:59,020
>> ახლა შევამოწმოთ, თუ გავითვალისწინებთ დატვირთული hash მაგიდა,
აპირებს გამოიყურებოდეს მოსწონს ეს.

91
00:04:59,020 --> 00:05:02,690
ასე რომ, შემოწმება, ის დააბრუნებს bool, რომელიც
აპირებს მიუთითებს თუ არა

92
00:05:02,690 --> 00:05:07,530
გაიარა-in char * სიტყვა, თუ არა
გაიარა-in string არის ჩვენი ლექსიკონი.

93
00:05:07,530 --> 00:05:10,530
ასე რომ, თუ ეს ლექსიკონი, თუ ეს
ჩვენს hash table, ჩვენ დავბრუნდებით

94
00:05:10,530 --> 00:05:13,380
დიახ, და თუ ეს ასე არ არის,
დავიბრუნებთ ყალბი.

95
00:05:13,380 --> 00:05:17,770
აქედან გამომდინარე მიღებულ-in სიტყვით, ჩვენ
ვაპირებ hash სიტყვა.

96
00:05:17,770 --> 00:05:22,020
>> ახლა, მთავარია, რომ აღიარებენ,
რომ დატვირთვა, ვიცოდით, რომ ყველა

97
00:05:22,020 --> 00:05:25,820
სიტყვები იქნება ქვედა შემთხვევაში,
მაგრამ აქ, ჩვენ არ ვარ დარწმუნებული.

98
00:05:25,820 --> 00:05:29,510
თუ ჩვენ შევხედოთ ჩვენი ქეშირების ფუნქცია,
ჩვენი ქეშირების ფუნქცია რეალურად

99
00:05:29,510 --> 00:05:32,700
არის lowercasing თითოეული ხასიათი
სიტყვა.

100
00:05:32,700 --> 00:05:37,580
ასე რომ, მიუხედავად იმისა, კაპიტალიზაცია
სიტყვა, ჩვენი ქეშირების ფუნქცია აპირებს

101
00:05:37,580 --> 00:05:42,270
დაბრუნება იგივე მაჩვენებელი, რასაც
კაპიტალიზაცია არის, როგორც ეს იქნებოდა

102
00:05:42,270 --> 00:05:45,280
დაბრუნდა სრულიად ამას
მობილური სიტყვას.

103
00:05:45,280 --> 00:05:45,950
ყველა უფლება.

104
00:05:45,950 --> 00:05:47,410
>> ასე რომ ჩვენი ინდექსი.

105
00:05:47,410 --> 00:05:49,790
ის hash table ამ სიტყვას.

106
00:05:49,790 --> 00:05:52,940
ახლა, ამ for loop აპირებს
ზედმეტად უკავშირდება სიაში

107
00:05:52,940 --> 00:05:55,000
რომ იყო, რომ ინდექსი.

108
00:05:55,000 --> 00:05:59,630
ასე რომ შეამჩნია ჩვენ ინიციალიზებისას შესვლის
აღვნიშნო, რომ ინდექსი.

109
00:05:59,630 --> 00:06:03,480
ჩვენ ვაპირებთ გავაგრძელოთ ხოლო შესვლის აკეთებს
არ უდრის NULL, და გვახსოვდეს, რომ

110
00:06:03,480 --> 00:06:08,350
განახლების მაჩვენებელი ჩვენს უკავშირდება სიაში
შესვლის შეადგენს შესვლის> მომავალი, ასე აქვს

111
00:06:08,350 --> 00:06:13,840
ჩვენი დღევანდელი შესვლის წერტილი
მომდევნო ნივთის უკავშირდება სიაში.

112
00:06:13,840 --> 00:06:14,400
ყველა უფლება.

113
00:06:14,400 --> 00:06:19,150
>> ასე რომ, ყოველი შესვლის უკავშირდება სია,
ჩვენ ვაპირებთ გამოვიყენოთ strcasecmp.

114
00:06:19,150 --> 00:06:23,780
ეს არ არის strcmp, რადგან, კიდევ ერთხელ, ჩვენ
გსურთ რამ შემთხვევაში insensitively.

115
00:06:23,780 --> 00:06:28,830
ასე რომ, ჩვენ ვიყენებთ strcasecmp შედარების სიტყვა
რომ გადაეცა ეს ფუნქცია

116
00:06:28,830 --> 00:06:31,860
წინააღმდეგ სიტყვა, რომელიც
არის ამ ჩანაწერს.

117
00:06:31,860 --> 00:06:35,570
იმ შემთხვევაში, თუ ის დააბრუნებს 0, რაც იმას ნიშნავს, არ იყო
მატჩი, რომლის დროსაც ჩვენ გვინდა

118
00:06:35,570 --> 00:06:36,630
TRUE.

119
00:06:36,630 --> 00:06:39,590
ჩვენ წარმატებით ი
სიტყვა ჩვენი hash მაგიდასთან.

120
00:06:39,590 --> 00:06:43,040
>> იმ შემთხვევაში, თუ არ იყო მატჩი, მაშინ ჩვენ
აპირებს loop ერთხელ და შევხედოთ

121
00:06:43,040 --> 00:06:43,990
შემდეგი ჩანაწერი.

122
00:06:43,990 --> 00:06:47,640
და ჩვენ გავაგრძელებთ looping ხოლო არსებობს
არის მასალაა ამ უკავშირდება სიაში.

123
00:06:47,640 --> 00:06:50,160
რა მოხდება, თუ ჩვენ შესვენება
გარეთ ამ loop?

124
00:06:50,160 --> 00:06:55,110
ეს ნიშნავს, რომ ჩვენ ვერ ჩანაწერი, რომ
შესაბამისი სიტყვა, რომლის დროსაც

125
00:06:55,110 --> 00:07:00,220
ჩვენ დაბრუნების ცრუ მიუთითებს იმაზე, რომ ჩვენი
hash table არ შეიცავს ამ სიტყვას.

126
00:07:00,220 --> 00:07:01,910
და რომ ეს შემოწმება.

127
00:07:01,910 --> 00:07:02,540
ყველა უფლება.

128
00:07:02,540 --> 00:07:04,790
>> მოდით შევხედოთ ზომის.

129
00:07:04,790 --> 00:07:09,280
ახლავე, ზომა იქნება საკმაოდ მარტივია
მას შემდეგ, რაც მახსოვს დატვირთვა, თითოეული სიტყვა

130
00:07:09,280 --> 00:07:12,880
ჩვენ აღმოვაჩინეთ, ჩვენ incremented გლობალურ
ცვლადი hashtable_size.

131
00:07:12,880 --> 00:07:15,830
ასე რომ ზომით ფუნქცია მხოლოდ
დაბრუნებას აპირებს, რომ გლობალური

132
00:07:15,830 --> 00:07:18,150
ცვლადი, და რომ არის ის.

133
00:07:18,150 --> 00:07:22,300
>> ახლა საბოლოოდ, ჩვენ უნდა განიტვირთოს
ლექსიკონი ერთხელ ყველაფერი კეთდება.

134
00:07:22,300 --> 00:07:25,340
ასე რომ, თუ ჩვენ ვაპირებთ, რომ გავაკეთოთ?

135
00:07:25,340 --> 00:07:30,440
სწორედ აქ, ჩვენ looping ყველა
თაიგულების ჩვენი hash მაგიდასთან.

136
00:07:30,440 --> 00:07:33,240
ასე რომ, არსებობს NUM_BUCKETS თაიგულების.

137
00:07:33,240 --> 00:07:37,490
და თითოეული უკავშირდება სიაში ჩვენს hash
მაგიდა, ჩვენ ვაპირებთ loop მეტი

138
00:07:37,490 --> 00:07:41,070
მთლიანად უკავშირდება სია
გამონთავისუფლების თითოეულ ელემენტს.

139
00:07:41,070 --> 00:07:46,070
ახლა, ჩვენ უნდა ვიყოთ ფრთხილად, ასე რომ აქ ჩვენ
აქვს დროებითი ცვლადი, რომ

140
00:07:46,070 --> 00:07:49,740
შენახვის მომცეთ შემდეგი
ელემენტს უკავშირდება სიაში.

141
00:07:49,740 --> 00:07:52,140
და მაშინ ჩვენ ვაპირებთ უფასო
მიმდინარე ელემენტს.

142
00:07:52,140 --> 00:07:55,990
>> ჩვენ უნდა დავრწმუნდეთ, ჩვენ ამის გაკეთება, რადგან ჩვენ
არ შეგიძლიათ უბრალოდ გასათავისუფლებლად მიმდინარე ელემენტს

143
00:07:55,990 --> 00:07:59,260
და შემდეგ ცდილობენ, რათა შეამოწმონ მომდევნო მაჩვენებელი
მას შემდეგ, რაც კიდევ ერთხელ გაათავისუფლეს მას

144
00:07:59,260 --> 00:08:00,870
მეხსიერება არასწორია.

145
00:08:00,870 --> 00:08:04,990
ამიტომ, ჩვენ უნდა შევინარჩუნოთ გარშემო მომცეთ
შემდეგი ელემენტს, მაშინ ჩვენ შეგვიძლია გასათავისუფლებლად

146
00:08:04,990 --> 00:08:08,360
მიმდინარე ელემენტს, და შემდეგ შეგვიძლია განახლება
ჩვენი დღევანდელი ელემენტს აღვნიშნო

147
00:08:08,360 --> 00:08:09,590
მომდევნო ელემენტს.

148
00:08:09,590 --> 00:08:12,770
>> ჩვენ loop ხოლო არსებობს ელემენტები
ამ უკავშირდება სიაში.

149
00:08:12,770 --> 00:08:16,450
ჩვენ ყველაფერს გავაკეთებთ, რომ ყველა დაკავშირებული სიები
hash მაგიდასთან, და კიდევ ჩვენ გავაკეთეთ

150
00:08:16,450 --> 00:08:20,180
რომ, ჩვენ მთლიანად დაცალა
hash მაგიდასთან, და ჩვენ გავაკეთეთ.

151
00:08:20,180 --> 00:08:24,050
ასე რომ შეუძლებელია unloads ოდესმე
დაბრუნების ცრუ, და როდესაც ჩვენ გავაკეთეთ, ჩვენ

152
00:08:24,050 --> 00:08:25,320
უბრალოდ დააბრუნოს ჭეშმარიტი.

153
00:08:25,320 --> 00:08:27,563