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

2
00:00:11,856 --> 00:00:13,050
>> Rob Bowden: হাই.

3
00:00:13,050 --> 00:00:16,210
আমি রব, এবং ধরা যাক এর হ্যাশ
এই সমাধান খুঁজে.

4
00:00:16,210 --> 00:00:20,070
তাই আমরা এখানে বাস্তবায়ন করতে যাচ্ছেন
একটি সাধারণ হ্যাশ টেবিল.

5
00:00:20,070 --> 00:00:24,090
আমরা দেখতে যে আমাদের হ্যাশ এর struct নোড
টেবিল ভালো চেহারা যাচ্ছে.

6
00:00:24,090 --> 00:00:28,710
সুতরাং এটি একটি গৃহস্থালি শব্দ আছে যাচ্ছে
আকার দৈর্ঘ্য প্লাস 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
ব্যাকস্ল্যাশ 0.

10
00:00:37,070 --> 00:00:40,870
>> এবং তারপর প্রতিটি আমাদের হ্যাশ টেবিল
বালতি সংরক্ষণ করতে যাচ্ছে একটি

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
তাই যাতে পরবর্তী লিঙ্ক
বালতি উপাদান, আমরা একটি প্রয়োজন

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
এখন, এখানে ঘোষণা হল
আমাদের হ্যাশ টেবিল.

17
00:00:56,180 --> 00:01:01,910
এটা 16.384 buckets আছে যাচ্ছে, কিন্তু এর
যে সংখ্যা সত্যিই কোন ব্যাপার না.

18
00:01:01,910 --> 00:01:05,450
এবং পরিশেষে, আমরা আছে চলুন
বিশ্বব্যাপী পরিবর্তনশীল hashtable_size, যা

19
00:01:05,450 --> 00:01:08,640
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 গৃহস্থালি * তারকা লাগে
অভিধান যা অভিধান,

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
তাই যদি সফল নিশ্চিত যে
এটি শূন্য ফিরে আসেন, তাহলে আমরা না

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 রাখা
এই আউট বিরতি কারণে

34
00:01:46,210 --> 00:01:47,570
আমরা দেখতে পাবেন যা লুপ.

35
00:01:47,570 --> 00:01:51,780
সুতরাং looping রাখা, এবং এখন আমরা চলুন
একটি নোডের 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
সুতরাং যে এন্ট্রি-> শব্দ মনে রাখতে গৃহস্থালি
শব্দ মাপ দৈর্ঘ্য বাফার প্লাস

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
এই সময় লুপ আউট.

48
00:02:37,280 --> 00:02:42,770
সুতরাং আমরা দেখতে যে আমরা সফলভাবে আছে একবার
মধ্যে একটি শব্দ পড়া

49
00:02:42,770 --> 00:02:48,270
এন্ট্রি-> শব্দ, তারপর আমরা হ্যাশ চলুন
আমাদের হ্যাশ ফাংশন ব্যবহার করে যে শব্দ.

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 গৃহস্থালি * শব্দ লাগে যে,

55
00:03:04,010 --> 00:03:08,960
তাই এটা ইনপুট হিসেবে একটি পংক্তি গ্রহণ এবং এর
আউটপুট হিসাবে একটি স্বাক্ষরবিহীন int-ফেরার.

56
00:03:08,960 --> 00:03:12,360
তাই যে সমস্ত একটি হ্যাশ ফাংশন হয়, এটা হয়
একটি ইনপুট মধ্যে লাগে, এটা আপনি একটি দেয়

57
00:03:12,360 --> 00:03:14,490
হ্যাশ টেবিল মধ্যে সূচী.

58
00:03:14,490 --> 00:03:18,530
আমরা NUM_BUCKETS দ্বারা modding করছি যে লক্ষ্য করুন
তাই হ্যাশ মান ফিরে

59
00:03:18,530 --> 00:03:21,730
আসলে হ্যাশ টেবিল মধ্যে একটি সূচক
এবং না অতিক্রম না সূচক

60
00:03:21,730 --> 00:03:24,320
অ্যারের কোট.

61
00:03:24,320 --> 00:03:27,855
>> সুতরাং হ্যাশ ফাংশন, আমরা চলুন যে দেওয়া
আমরা পড়তে যে শব্দ হ্যাশ করার

62
00:03:27,855 --> 00:03:31,700
অভিধান থেকে এবং তারপর আমরা চলুন
যে ব্যবহার সন্নিবেশ আছে

63
00:03:31,700 --> 00:03:33,750
হ্যাশ টেবিল ঢোকা.

64
00:03:33,750 --> 00:03:38,830
এখন, hashtable হ্যাশ বর্তমান
লিঙ্ক হ্যাশ টেবিল তালিকা, এবং

65
00:03:38,830 --> 00:03:41,410
এটি শুধু শূন্য যে খুবই সম্ভব.

66
00:03:41,410 --> 00:03:45,640
আমরা আমাদের এন্ট্রি সন্নিবেশ করতে চান
এই লিঙ্ক তালিকা শুরু, এবং তাই

67
00:03:45,640 --> 00:03:48,910
আমরা আমাদের বর্তমান এন্ট্রি আছে চলুন
বর্তমানে কি হ্যাশ টেবিল নির্দেশ

68
00:03:48,910 --> 00:03:54,030
পয়েন্ট এবং তারপর আমরা সংরক্ষণ চলুন
হ্যাশ এ হ্যাশ টেবিল

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
যে সূচিতে যুক্ত তালিকা
হ্যাশ টেবিল.

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 প্রদান

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
ক্ষেত্রে আমরা যে আমরা এন্ট্রি মুক্ত করতে হবে
আসলে হ্যাশ টেবিল পুরা না

79
00:04:27,440 --> 00:04:29,110
এবং পরিশেষে বিরতি.

80
00:04:29,110 --> 00:04:32,750
>> আমরা আউট বিরতি পরে, আমরা ভাল,, দেখাতে
আমরা, কারণ সেখানে আউট বিরতি নি

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
আমরা সফল হয়নি Assuming, তারপর আমরা ঠিক
এখনও অভিধান বন্ধ করতে হবে

87
00:04:48,740 --> 00:04:51,970
ফাইল, এবং পরিশেষে, যেহেতু সত্য ফিরে
আমরা সফলভাবে লোড করেছি

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
>> তাই এখন একটি লোড হ্যাশ টেবিল দেওয়া, চেক,
এই মত দেখতে যাচ্ছে.

91
00:04:59,020 --> 00:05:02,690
সুতরাং, এটি একটি bool ফেরৎ, চেক যা
ইঙ্গিত যাচ্ছে কিনা

92
00:05:02,690 --> 00:05:07,530
পাশ ইন গৃহস্থালি * শব্দ, কিনা
পাশ ইন স্ট্রিং আমাদের অভিধান আছে.

93
00:05:07,530 --> 00:05:10,530
এটি অভিধানে হয় সুতরাং, এটা যদি
আমাদের হ্যাশ টেবিল, আমরা ফিরে আসবে

94
00:05:10,530 --> 00:05:13,380
সত্য, এবং এটা না হলে,
আমরা মিথ্যা ফিরে আসবে.

95
00:05:13,380 --> 00:05:17,770
এই পাস ইন শব্দ দেওয়া, আমরা করছি
শব্দ হ্যাশ যাচ্ছে.

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
এটা এই শব্দ জন্য হ্যাশ টেবিল এর.

106
00:05:49,790 --> 00:05:52,940
এখন, লুপ জন্য এই যাচ্ছে
লিঙ্ক তালিকা উপর থেকে

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
আমরা এন্ট্রি আছে, যখন চালিয়ে যাচ্ছেন
না সমান শূন্য, এবং মনে রাখবেন যে

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 না, কারণ আবার, আমরা
জন্মভূমিতে জিনিস ক্ষেত্রে কাজ করতে চান.

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
সত্য ফিরে.

119
00:06:36,630 --> 00:06:39,590
আমরা সফলভাবে পাওয়া
আমাদের হ্যাশ টেবিল শব্দ.

120
00:06:39,590 --> 00:06:43,040
>> একটি ম্যাচ ছিল না, তাহলে আমরা করছি
আবার লুপ যাচ্ছে এবং তাকান

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
আমরা বিরতি তাহলে কি হবে
লুপ জন্য এই আউট?

124
00:06:50,160 --> 00:06:55,110
আমরা একটি এন্ট্রি খুঁজে পান না মানে
যে ক্ষেত্রে, এই শব্দ মিলেছে

125
00:06:55,110 --> 00:07:00,220
আমরা ইঙ্গিত মিথ্যা ফিরে যে আমাদের
হ্যাশ টেবিল এই শব্দ ধারণ করা হয়নি.

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
আমরা একটি আন্তর্জাতিক মান বৃদ্ধি পাওয়া
পরিবর্তনশীল 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 করছি
আমাদের হ্যাশ টেবিল buckets.

136
00:07:30,440 --> 00:07:33,240
সুতরাং NUM_BUCKETS buckets আছে.

137
00:07:33,240 --> 00:07:37,490
এবং আমাদের হ্যাশ প্রতিটি লিঙ্ক তালিকা জন্য
টেবিল, আমরা ধরে লুপ চলুন

138
00:07:37,490 --> 00:07:41,070
লিঙ্ক তালিকা সম্পূর্ণতা
প্রতিটি উপাদান freeing.

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
>> আমরা উপাদান লুপ আছে করব, যখন
এই লিঙ্ক তালিকায়.

149
00:08:12,770 --> 00:08:16,450
আমরা সব লিঙ্ক তালিকা জন্য যে চেষ্টা করবো
হ্যাশ টেবিল, এবং আমরা কাজ সম্পন্ন হয় একবার

150
00:08:16,450 --> 00:08:20,180
যে সঙ্গে, আমরা সম্পূর্ণ unloaded করেছি
হ্যাশ টেবিল, এবং আমরা কাজ সম্পন্ন হয়.

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