>> Rob Bowden: হাই.
আমি রব, এবং ধরা যাক এর হ্যাশ এই সমাধান খুঁজে.
তাই আমরা এখানে বাস্তবায়ন করতে যাচ্ছেন একটি সাধারণ হ্যাশ টেবিল.
আমরা দেখতে যে আমাদের হ্যাশ এর struct নোড টেবিল ভালো চেহারা যাচ্ছে.
সুতরাং এটি একটি গৃহস্থালি শব্দ আছে যাচ্ছে আকার দৈর্ঘ্য প্লাস 1 অ্যারে.
সর্বাধিক সাল 1 ভুলবেন না অভিধানে শব্দ 45 হয়
অক্ষর, এবং তারপর আমরা চলুন জন্য এক অতিরিক্ত অক্ষর প্রয়োজন
ব্যাকস্ল্যাশ 0.
>> এবং তারপর প্রতিটি আমাদের হ্যাশ টেবিল বালতি সংরক্ষণ করতে যাচ্ছে একটি
নোড যুক্ত তালিকা.
আমরা এখানে অনুসন্ধান রৈখিক কাজ করছি না.
তাই যাতে পরবর্তী লিঙ্ক বালতি উপাদান, আমরা একটি প্রয়োজন
struct নোড * পরবর্তী.
সুতরাং যে একটি নোডের মতো দেখতে কি.
এখন, এখানে ঘোষণা হল আমাদের হ্যাশ টেবিল.
এটা 16.384 buckets আছে যাচ্ছে, কিন্তু এর যে সংখ্যা সত্যিই কোন ব্যাপার না.
এবং পরিশেষে, আমরা আছে চলুন বিশ্বব্যাপী পরিবর্তনশীল hashtable_size, যা
0 হিসাবে চলতে শুরু করা যাচ্ছে, এবং এটা করা হয় ট্র্যাক রাখতে যাচ্ছে কতগুলি শব্দ
আমাদের অভিধানে ছিল.
ঠিক আছে.
>> সুতরাং আসুন লোড কটাক্ষপাত করা যাক.
সুতরাং যে চাপের লক্ষ্য করা, এটি একটি bool ফেরৎ.
এটি সফলভাবে যদি আপনি সত্য ফিরে অন্যথায় লোড এবং মিথ্যা.
এবং এটি একটি const গৃহস্থালি * তারকা লাগে অভিধান যা অভিধান,
আমরা খোলার ব্যাপারে.
তাই প্রথম যে জিনিস আমরা কি করতে যাচ্ছেন.
আমরা জন্য অভিধান fopen চলুন পড়া, এবং আমরা আছে চলুন
তাই যদি সফল নিশ্চিত যে এটি শূন্য ফিরে আসেন, তাহলে আমরা না
সফলভাবে অভিধান খুলতে এবং আমরা মিথ্যা ফিরে প্রয়োজন.
>> কিন্তু এটা সফলভাবে যে অভিমানী খোলা, তাহলে আমরা পড়তে চাই
অভিধান.
আমরা কিছু খুঁজে না হওয়া পর্যন্ত তাই looping রাখা এই আউট বিরতি কারণে
আমরা দেখতে পাবেন যা লুপ.
সুতরাং looping রাখা, এবং এখন আমরা চলুন একটি নোডের malloc করতে.
এবং অবশ্যই, আমরা চেক ত্রুটি প্রয়োজন আবার mallocing সফল হয়নি তাই যদি
এবং আমরা যে আমরা কোনো নোড আন চান আগে malloc ঘটেছে, বন্ধ করুন
অভিধান এবং মিথ্যা ফিরে.
>> কিন্তু যে উপেক্ষা, অভিমানী আমরা সফল, তাহলে আমরা fscanf ব্যবহার করতে চান
থেকে একটি একক শব্দ পড়তে আমাদের আমাদের নোড অভিধান.
সুতরাং যে এন্ট্রি-> শব্দ মনে রাখতে গৃহস্থালি শব্দ মাপ দৈর্ঘ্য বাফার প্লাস
আমরা চলুন যে এক ইন শব্দ সংরক্ষণ
সুতরাং fscanf 1 যতদিন ফিরে যাচ্ছে এটি সফলভাবে একটি পড়তে সক্ষম ছিল
ফাইল থেকে শব্দ.
>> একটি ত্রুটি হয় সেটা হয় বা আমরা পৌঁছতে হলে ফাইলের শেষে, এটা না করবে না
যদি না হয় যে ক্ষেত্রে 1 ফিরে 1 ফিরে, আমরা অবশেষে বিরতি চলুন
এই সময় লুপ আউট.
সুতরাং আমরা দেখতে যে আমরা সফলভাবে আছে একবার মধ্যে একটি শব্দ পড়া
এন্ট্রি-> শব্দ, তারপর আমরা হ্যাশ চলুন আমাদের হ্যাশ ফাংশন ব্যবহার করে যে শব্দ.
এর কটাক্ষপাত করা যাক হ্যাশ ফাংশন.
>> সুতরাং আপনি সত্যিই প্রয়োজন নেই এই বুঝতে.
এবং প্রকৃতপক্ষে, আমরা শুধু এই টানা ইন্টারনেট থেকে ফাংশন হ্যাশ.
আপনি স্বীকার করা প্রয়োজন শুধুমাত্র জিনিস এই একটি const গৃহস্থালি * শব্দ লাগে যে,
তাই এটা ইনপুট হিসেবে একটি পংক্তি গ্রহণ এবং এর আউটপুট হিসাবে একটি স্বাক্ষরবিহীন int-ফেরার.
তাই যে সমস্ত একটি হ্যাশ ফাংশন হয়, এটা হয় একটি ইনপুট মধ্যে লাগে, এটা আপনি একটি দেয়
হ্যাশ টেবিল মধ্যে সূচী.
আমরা NUM_BUCKETS দ্বারা modding করছি যে লক্ষ্য করুন তাই হ্যাশ মান ফিরে
আসলে হ্যাশ টেবিল মধ্যে একটি সূচক এবং না অতিক্রম না সূচক
অ্যারের কোট.
>> সুতরাং হ্যাশ ফাংশন, আমরা চলুন যে দেওয়া আমরা পড়তে যে শব্দ হ্যাশ করার
অভিধান থেকে এবং তারপর আমরা চলুন যে ব্যবহার সন্নিবেশ আছে
হ্যাশ টেবিল ঢোকা.
এখন, hashtable হ্যাশ বর্তমান লিঙ্ক হ্যাশ টেবিল তালিকা, এবং
এটি শুধু শূন্য যে খুবই সম্ভব.
আমরা আমাদের এন্ট্রি সন্নিবেশ করতে চান এই লিঙ্ক তালিকা শুরু, এবং তাই
আমরা আমাদের বর্তমান এন্ট্রি আছে চলুন বর্তমানে কি হ্যাশ টেবিল নির্দেশ
পয়েন্ট এবং তারপর আমরা সংরক্ষণ চলুন হ্যাশ এ হ্যাশ টেবিল
বর্তমান এন্ট্রি.
>> তাই এই দুটি লাইন সফলভাবে সন্নিবেশ শুরুতে এন্ট্রি
যে সূচিতে যুক্ত তালিকা হ্যাশ টেবিল.
আমরা যে সঙ্গে সম্পন্ন হলে, আমরা জানি আমরা অন্য শব্দ পাওয়া যে
অভিধান এবং আমরা আবার বাড়ায়.
সুতরাং আমরা করছেন রাখা যে fscanf যতক্ষণ অবশেষে এ অ কিছু 1 প্রদান
যা বিন্দু আমরা প্রয়োজন মনে রাখা বিনামূল্যে এন্ট্রি, তাই এখানে, আমরা একটি malloced
এন্ট্রি এবং আমরা কিছু পড়ার চেষ্টা অভিধান থেকে.
এবং আমরা সফলভাবে পড়তে হয়নি অভিধান থেকে কিছু যা
ক্ষেত্রে আমরা যে আমরা এন্ট্রি মুক্ত করতে হবে আসলে হ্যাশ টেবিল পুরা না
এবং পরিশেষে বিরতি.
>> আমরা আউট বিরতি পরে, আমরা ভাল,, দেখাতে আমরা, কারণ সেখানে আউট বিরতি নি
একটি ত্রুটি ফাইল থেকে পড়া, অথবা ছিল আমরা পৌঁছেছেন, কারণ আমরা আউট বিরতি নি
ফাইলের শেষে?
একটি ত্রুটি ছিল, তাহলে আমরা চাই লোড না, কারণ মিথ্যা ফিরে
সফল, এবং এই প্রক্রিয়ায়, আমরা চাই আমরা পড়তে যে সব শব্দ আন
এবং মধ্যে অভিধান ফাইলটি বন্ধ করুন.
আমরা সফল হয়নি Assuming, তারপর আমরা ঠিক এখনও অভিধান বন্ধ করতে হবে
ফাইল, এবং পরিশেষে, যেহেতু সত্য ফিরে আমরা সফলভাবে লোড করেছি
অভিধান.
এবং যে চাপের জন্য এটি.
>> তাই এখন একটি লোড হ্যাশ টেবিল দেওয়া, চেক, এই মত দেখতে যাচ্ছে.
সুতরাং, এটি একটি bool ফেরৎ, চেক যা ইঙ্গিত যাচ্ছে কিনা
পাশ ইন গৃহস্থালি * শব্দ, কিনা পাশ ইন স্ট্রিং আমাদের অভিধান আছে.
এটি অভিধানে হয় সুতরাং, এটা যদি আমাদের হ্যাশ টেবিল, আমরা ফিরে আসবে
সত্য, এবং এটা না হলে, আমরা মিথ্যা ফিরে আসবে.
এই পাস ইন শব্দ দেওয়া, আমরা করছি শব্দ হ্যাশ যাচ্ছে.
>> এখন, চিনতে একটি গুরুত্বপূর্ণ জিনিস লোড, আমরা জানতাম যে যে সব
শব্দ ছোট হাতের হবে ছিল, কিন্তু এখানে, আমরা তাই নিশ্চিত না হন.
আমরা আমাদের হ্যাশ ফাংশন কটাক্ষপাত করা হলে, আসলে আমাদের হ্যাশ ফাংশন
প্রতিটি অক্ষর lowercasing হয় শব্দের.
সুতরাং নির্বিশেষে ক্যাপিটালাইজেশন এর শব্দ, আমাদের হ্যাশ ফাংশন যাচ্ছে
যাই হোক না কেন জন্য একই সূচক ফিরে ক্যাপিটালাইজেশন এটা হবে হিসাবে হয়
একটি সম্পূর্ণ ছোট হাতের জন্য ফিরে শব্দের সংস্করণ.
ঠিক আছে.
>> সুতরাং যে আমাদের ইনডেক্স এর.
এটা এই শব্দ জন্য হ্যাশ টেবিল এর.
এখন, লুপ জন্য এই যাচ্ছে লিঙ্ক তালিকা উপর থেকে
যে যে সূচিতে ছিল.
সুতরাং আমরা এন্ট্রি আরম্ভ করা হয় বিজ্ঞপ্তি যে সূচক নির্দেশ.
আমরা এন্ট্রি আছে, যখন চালিয়ে যাচ্ছেন না সমান শূন্য, এবং মনে রাখবেন যে
আমাদের লিঙ্ক তালিকায় পয়েন্টার আপডেট এন্ট্রি পরবর্তী এন্ট্রি-> সমান, তাই আছে
আমাদের বর্তমান এন্ট্রি পয়েন্ট লিঙ্ক তালিকায় পরবর্তী আইটেম.
ঠিক আছে.
>> তাই লিঙ্ক তালিকায় প্রতিটি এন্ট্রির জন্য, আমরা strcasecmp ব্যবহার করতে যাচ্ছেন.
এটা strcmp না, কারণ আবার, আমরা জন্মভূমিতে জিনিস ক্ষেত্রে কাজ করতে চান.
সুতরাং আমরা শব্দের তুলনা strcasecmp ব্যবহার যে এই ফাংশন প্রেরণ করা হত
শব্দ বিরুদ্ধে যে এই এন্ট্রি হয়.
এটা 0 প্রদান করে, যে ছিল মানে আমরা চাই যে ক্ষেত্রে একটি ম্যাচ,
সত্য ফিরে.
আমরা সফলভাবে পাওয়া আমাদের হ্যাশ টেবিল শব্দ.
>> একটি ম্যাচ ছিল না, তাহলে আমরা করছি আবার লুপ যাচ্ছে এবং তাকান
পরের এন্ট্রি.
এবং আমরা যখন সেখানে looping চালিয়ে যাব এই লিঙ্ক তালিকায় এন্ট্রি হয়.
আমরা বিরতি তাহলে কি হবে লুপ জন্য এই আউট?
আমরা একটি এন্ট্রি খুঁজে পান না মানে যে ক্ষেত্রে, এই শব্দ মিলেছে
আমরা ইঙ্গিত মিথ্যা ফিরে যে আমাদের হ্যাশ টেবিল এই শব্দ ধারণ করা হয়নি.
এবং যে চেক জন্য এটি.
ঠিক আছে.
>> তাই এর আকার কটাক্ষপাত করা যাক.
এখন, আকার বেশ সহজ হবে যেহেতু প্রতিটি শব্দের জন্য, চাপের মধ্যে স্মরণ
আমরা একটি আন্তর্জাতিক মান বৃদ্ধি পাওয়া পরিবর্তনশীল hashtable_size.
তাই মাপ ফাংশন ঠিক হয় যে বৈশ্বিক ফিরে যাচ্ছে
পরিবর্তনশীল, এবং যে এটি.
>> এখন পরিশেষে, আমরা মাল খালাস করতে হবে অভিধান সবকিছু সম্পন্ন এর একবার.
তাই কিভাবে আমরা তা করতে যাচ্ছে?
এখানে ডান, আমরা সর্বাঙ্গে looping করছি আমাদের হ্যাশ টেবিল buckets.
সুতরাং NUM_BUCKETS buckets আছে.
এবং আমাদের হ্যাশ প্রতিটি লিঙ্ক তালিকা জন্য টেবিল, আমরা ধরে লুপ চলুন
লিঙ্ক তালিকা সম্পূর্ণতা প্রতিটি উপাদান freeing.
এখন, আমরা সচেতন হওয়া প্রয়োজন, তাই আমরা এখানে যে একটি অস্থায়ী ভেরিয়েবল আছে
পরবর্তী পয়েন্টার জমা করার লিঙ্ক তালিকায় উপাদান.
এবং তারপর আমরা বিনামূল্যে চলুন বর্তমান উপাদান.
>> আমরা আমরা আমরা যেহেতু এই কাজ নিশ্চিত করা প্রয়োজন শুধু বর্তমান উপাদান মুক্ত করতে পারবেন না
এবং তারপর পরবর্তী পয়েন্টার অ্যাক্সেস করতে চেষ্টা যেহেতু একবার আমরা এটি মুক্ত
স্মৃতি হয়ে অবৈধ.
সুতরাং আমরা একটি পয়েন্টার কাছাকাছি রাখা প্রয়োজন পরবর্তী উপাদান, তাহলে আমরা মুক্ত করতে পারেন
বর্তমান উপাদান, এবং তারপর আমরা আপডেট করতে পারেন নির্দেশ আমাদের বর্তমান উপাদান
পরবর্তী উপাদান.
>> আমরা উপাদান লুপ আছে করব, যখন এই লিঙ্ক তালিকায়.
আমরা সব লিঙ্ক তালিকা জন্য যে চেষ্টা করবো হ্যাশ টেবিল, এবং আমরা কাজ সম্পন্ন হয় একবার
যে সঙ্গে, আমরা সম্পূর্ণ unloaded করেছি হ্যাশ টেবিল, এবং আমরা কাজ সম্পন্ন হয়.
সুতরাং unloads জন্য কখনও অসম্ভব মিথ্যা ফিরে, এবং আমরা কাজ সম্পন্ন হয়, আমরা
শুধু সত্য ফিরে.