>> რობ Bowden: Hi.
მე რობ, და მოდით hash ეს გამოსავალი.
ასე რომ, აქ ჩვენ ვაპირებთ განხორციელება ზოგადი hash მაგიდასთან.
ჩვენ ვხედავთ, რომ struct კვანძის ჩვენი hash მაგიდა აპირებს გამოიყურებოდეს მოსწონს ეს.
ასე რომ, ის აპირებს აქვს char სიტყვა მასივი ზომა სიგრძე პლუს 1.
ნუ დაგავიწყდებათ 1 წლიდან მაქსიმალური სიტყვა ლექსიკონი 45
პერსონაჟი, და შემდეგ ჩვენ ვაპირებთ უნდა ერთი ზედმეტი ხასიათი
backslash 0.
>> და მაშინ ჩვენი hash table თითოეულ bucket აპირებს შესანახად
დაკავშირებული სიაში კვანძების.
ჩვენ არ ვაკეთებთ ხაზოვანი საცდელი აქ.
და რათა დააკავშიროს მომდევნო ელემენტს bucket, ჩვენ გვჭირდება
struct კვანძის * შემდეგი.
ასე რომ რა კვანძის ჰგავს.
ახლა, აქ არის დეკლარაცია ჩვენი hash მაგიდასთან.
ის აპირებს აქვს 16.384 თაიგულების, მაგრამ რომ ნომერი ნამდვილად არ აქვს.
და ბოლოს, ჩვენ ვაპირებთ აქვს გლობალური ცვლადი hashtable_size, რომელიც
აპირებს დაიწყოს off როგორც 0 და ეს აპირებს ტრეკზე რამდენი სიტყვა
იყო ჩვენი ლექსიკონი.
ყველა უფლება.
>> მოდით შევხედოთ დატვირთვა.
ასე რომ შეამჩნია, რომ დატვირთვის, ის დააბრუნებს bool.
თქვენ დაბრუნდება ნამდვილი, თუ ეს იყო წარმატებით დატვირთული და ცრუ სხვაგვარად.
და ეს ხდება const char * star ლექსიკონი, რომელიც ლექსიკონი
რომ ჩვენ გვინდა გახსნა.
ასე რომ, პირველი, რაც ჩვენ ვაპირებთ, რომ გავაკეთოთ.
ჩვენ ვაპირებთ fopen ლექსიკონი კითხულობს, და ჩვენ ვაპირებთ აქვს
დარწმუნდით, რომ ეს შეძლო ასე რომ, თუ იგი დაბრუნდა NULL, მაშინ ჩვენ არ
წარმატებით გახსნა ლექსიკონი და ჩვენ გვჭირდება დაბრუნების ცრუ.
>> მაგრამ თუ გავითვალისწინებთ, რომ ეს წარმატებით ღია, მაშინ ჩვენ გვინდა წაიკითხოთ
ლექსიკონი.
გააგრძელეთ looping სანამ ჩვენ გამოძებნოს მიზეზი შესვენება out ამ
loop, რომელიც ჩვენ დავინახავთ.
გააგრძელეთ looping, და ახლა ჩვენ ვაპირებთ to malloc ერთი კვანძის.
და რა თქმა უნდა, ჩვენ უნდა შეცდომა შემოწმება ერთხელ ასე რომ, თუ mallocing არ გავიდა
და გვინდა, რომ განიტვირთოს ნებისმიერი კვანძის რომ ჩვენ მოხდა malloc ადრე, დახუროს
ლექსიკონი და დაბრუნების ცრუ.
>> მაგრამ იგნორირება, რომ ვთქვათ, ჩვენ შეძლო, მაშინ ჩვენ გვინდა გამოვიყენოთ fscanf
წაკითხვის ერთი სიტყვა ჩვენი ლექსიკონი ჩვენს კვანძში.
ასე მახსოვს, რომ შესვლის> სიტყვა არის char სიტყვა ბუფერის ზომა სიგრძე პლუს
ერთი, რომ ჩვენ ვაპირებთ შესანახად სიტყვა შემოსული
ასე fscanf დაბრუნებას აპირებს 1 მანამ, რადგან შეძლო წარმატებით წაიკითხა
სიტყვა ფაილი.
>> თუ არც შეცდომა ხდება, ან ჩვენ მივაღწევთ ბოლოს ფაილი, ის არ
დაბრუნდება 1 ამ შემთხვევაში, თუ იგი არ დაბრუნდება 1, ჩვენ საბოლოოდ აპირებს დაარღვიოს
აქედან ხოლო loop.
ასე რომ, ჩვენ ვხედავთ, რომ ერთხელ ჩვენ წარმატებით წაიკითხა სიტყვა შევიდა
შესვლის> სიტყვა, მაშინ ჩვენ ვაპირებთ hash რომ სიტყვა ჩვენი ქეშირების ფუნქცია.
მოდით შევხედოთ ქეშირების ფუნქცია.
>> ასე, რომ თქვენ ნამდვილად არ უნდა ამის გაგება.
და რეალურად, ჩვენ უბრალოდ გამოყვანილია ამ ქეშირების ფუნქცია ინტერნეტში.
ერთადერთი, რაც თქვენ უნდა აღიაროს არის რომ ეს იღებს const char * სიტყვა,
ამიტომ აღების სიმებიანი, როგორც შეყვანის და დაბრუნების unsigned int როგორც გამომავალი.
ასე რომ ყველა ქეშირების ფუნქცია, არის ის იღებს შეყვანის, ეს გაძლევთ
ინდექსი შევიდა hash მაგიდასთან.
გაითვალისწინეთ, რომ ჩვენ მოდინგი მიერ NUM_BUCKETS ასე რომ, hash ღირებულება დაბრუნდა
რეალურად არის ინდექსი შევიდა hash table და არ index მიღმა
ფარგლებში მასივი.
>> ასე რომ, თუ გავითვალისწინებთ, რომ ქეშირების ფუნქცია, ჩვენ ვაპირებთ to hash სიტყვა, რომელიც ჩვენ ვკითხულობთ
საწყისი ლექსიკონი და მაშინ ჩვენ ვაპირებთ გამოყენება, რომელსაც აქვს ჩასასმელად
შესვლის hash მაგიდასთან.
ახლა, hashtable hash მიმდინარე დაკავშირებული სიაში hash მაგიდა და
ეს ძალიან შესაძლებელია, რომ მხოლოდ NULL.
გვინდა ჩადეთ ჩვენი შესვლის დროს დაწყებული ამ უკავშირდება სია, და ა.შ.
ჩვენ ვაპირებთ, რომ ჩვენი დღევანდელი შესვლის მიუთითებენ რა hash table გაკეთებული
რაოდენობა და შემდეგ ჩვენ ვაპირებთ შესანახად ამ hash მაგიდაზე hash
მიმდინარე ჩანაწერი.
>> ასე რომ, ეს ორი ხაზი წარმატებით ჩადეთ შესვლის დასაწყისში
უკავშირდება სია იმ ინდექსი ამ hash მაგიდასთან.
მას შემდეგ, რაც ჩვენ გავაკეთეთ, რომ, ჩვენ ვიცით, რომ ჩვენ ვნახეთ ერთი სიტყვა
ლექსიკონი და ჩვენ ნამატი ერთხელ.
ასე რომ, ჩვენ აკეთეთ, რომ სანამ fscanf საბოლოოდ ბრუნდება რაღაც არასამთავრობო 1 at
სადაც წერტილი გვახსოვდეს, რომ ჩვენ უნდა თავისუფალი შესვლის, ასე რომ აქ, ჩვენ malloced
შესვლის და ჩვენ შევეცადეთ წავიკითხე რაღაც საწყისი ლექსიკონი.
და ჩვენ არ წარმატებით წაკითხული რაღაც ლექსიკონი, რომელშიც
წინააღმდეგ შემთხვევაში, ჩვენ უნდა გავათავისუფლოთ შესვლის, რომ ჩვენ არასოდეს რეალურად ამოქმედებული hash table
და საბოლოოდ დაარღვიოს.
>> მას შემდეგ, რაც ჩვენ შესვენება out, ჩვენ უნდა დაინახოს, ასევე, არც ჩვენ შესვენება out რადგან იქ
შეცდომა კითხულობს საწყისი ფაილი, ან არც ჩვენ შესვენება, რადგან ჩვენ მივაღწიეთ
ბოლოს ფაილი?
იყო თუ არა შეცდომა, მაშინ ჩვენ გვინდა დაბრუნების ცრუ, რადგან დატვირთვა არ
წარმატების მიღწევა, და ამ პროცესში, ჩვენ გვინდა განიტვირთოს ყველა ის სიტყვა, ვკითხულობთ
და დახუროს ლექსიკონი ფაილი.
ვთქვათ, ჩვენ არ გამოუვათ, მაშინ ჩვენ უბრალოდ მაინც უნდა დახუროს ლექსიკონი
ფაილი, და საბოლოოდ იქნება TRUE, რადგან ჩვენ წარმატებით დატვირთული
ლექსიკონი.
და რომ ეს დატვირთვა.
>> ახლა შევამოწმოთ, თუ გავითვალისწინებთ დატვირთული hash მაგიდა, აპირებს გამოიყურებოდეს მოსწონს ეს.
ასე რომ, შემოწმება, ის დააბრუნებს bool, რომელიც აპირებს მიუთითებს თუ არა
გაიარა-in char * სიტყვა, თუ არა გაიარა-in string არის ჩვენი ლექსიკონი.
ასე რომ, თუ ეს ლექსიკონი, თუ ეს ჩვენს hash table, ჩვენ დავბრუნდებით
დიახ, და თუ ეს ასე არ არის, დავიბრუნებთ ყალბი.
აქედან გამომდინარე მიღებულ-in სიტყვით, ჩვენ ვაპირებ hash სიტყვა.
>> ახლა, მთავარია, რომ აღიარებენ, რომ დატვირთვა, ვიცოდით, რომ ყველა
სიტყვები იქნება ქვედა შემთხვევაში, მაგრამ აქ, ჩვენ არ ვარ დარწმუნებული.
თუ ჩვენ შევხედოთ ჩვენი ქეშირების ფუნქცია, ჩვენი ქეშირების ფუნქცია რეალურად
არის lowercasing თითოეული ხასიათი სიტყვა.
ასე რომ, მიუხედავად იმისა, კაპიტალიზაცია სიტყვა, ჩვენი ქეშირების ფუნქცია აპირებს
დაბრუნება იგივე მაჩვენებელი, რასაც კაპიტალიზაცია არის, როგორც ეს იქნებოდა
დაბრუნდა სრულიად ამას მობილური სიტყვას.
ყველა უფლება.
>> ასე რომ ჩვენი ინდექსი.
ის hash table ამ სიტყვას.
ახლა, ამ for loop აპირებს ზედმეტად უკავშირდება სიაში
რომ იყო, რომ ინდექსი.
ასე რომ შეამჩნია ჩვენ ინიციალიზებისას შესვლის აღვნიშნო, რომ ინდექსი.
ჩვენ ვაპირებთ გავაგრძელოთ ხოლო შესვლის აკეთებს არ უდრის NULL, და გვახსოვდეს, რომ
განახლების მაჩვენებელი ჩვენს უკავშირდება სიაში შესვლის შეადგენს შესვლის> მომავალი, ასე აქვს
ჩვენი დღევანდელი შესვლის წერტილი მომდევნო ნივთის უკავშირდება სიაში.
ყველა უფლება.
>> ასე რომ, ყოველი შესვლის უკავშირდება სია, ჩვენ ვაპირებთ გამოვიყენოთ strcasecmp.
ეს არ არის strcmp, რადგან, კიდევ ერთხელ, ჩვენ გსურთ რამ შემთხვევაში insensitively.
ასე რომ, ჩვენ ვიყენებთ strcasecmp შედარების სიტყვა რომ გადაეცა ეს ფუნქცია
წინააღმდეგ სიტყვა, რომელიც არის ამ ჩანაწერს.
იმ შემთხვევაში, თუ ის დააბრუნებს 0, რაც იმას ნიშნავს, არ იყო მატჩი, რომლის დროსაც ჩვენ გვინდა
TRUE.
ჩვენ წარმატებით ი სიტყვა ჩვენი hash მაგიდასთან.
>> იმ შემთხვევაში, თუ არ იყო მატჩი, მაშინ ჩვენ აპირებს loop ერთხელ და შევხედოთ
შემდეგი ჩანაწერი.
და ჩვენ გავაგრძელებთ looping ხოლო არსებობს არის მასალაა ამ უკავშირდება სიაში.
რა მოხდება, თუ ჩვენ შესვენება გარეთ ამ loop?
ეს ნიშნავს, რომ ჩვენ ვერ ჩანაწერი, რომ შესაბამისი სიტყვა, რომლის დროსაც
ჩვენ დაბრუნების ცრუ მიუთითებს იმაზე, რომ ჩვენი hash table არ შეიცავს ამ სიტყვას.
და რომ ეს შემოწმება.
ყველა უფლება.
>> მოდით შევხედოთ ზომის.
ახლავე, ზომა იქნება საკმაოდ მარტივია მას შემდეგ, რაც მახსოვს დატვირთვა, თითოეული სიტყვა
ჩვენ აღმოვაჩინეთ, ჩვენ incremented გლობალურ ცვლადი hashtable_size.
ასე რომ ზომით ფუნქცია მხოლოდ დაბრუნებას აპირებს, რომ გლობალური
ცვლადი, და რომ არის ის.
>> ახლა საბოლოოდ, ჩვენ უნდა განიტვირთოს ლექსიკონი ერთხელ ყველაფერი კეთდება.
ასე რომ, თუ ჩვენ ვაპირებთ, რომ გავაკეთოთ?
სწორედ აქ, ჩვენ looping ყველა თაიგულების ჩვენი hash მაგიდასთან.
ასე რომ, არსებობს NUM_BUCKETS თაიგულების.
და თითოეული უკავშირდება სიაში ჩვენს hash მაგიდა, ჩვენ ვაპირებთ loop მეტი
მთლიანად უკავშირდება სია გამონთავისუფლების თითოეულ ელემენტს.
ახლა, ჩვენ უნდა ვიყოთ ფრთხილად, ასე რომ აქ ჩვენ აქვს დროებითი ცვლადი, რომ
შენახვის მომცეთ შემდეგი ელემენტს უკავშირდება სიაში.
და მაშინ ჩვენ ვაპირებთ უფასო მიმდინარე ელემენტს.
>> ჩვენ უნდა დავრწმუნდეთ, ჩვენ ამის გაკეთება, რადგან ჩვენ არ შეგიძლიათ უბრალოდ გასათავისუფლებლად მიმდინარე ელემენტს
და შემდეგ ცდილობენ, რათა შეამოწმონ მომდევნო მაჩვენებელი მას შემდეგ, რაც კიდევ ერთხელ გაათავისუფლეს მას
მეხსიერება არასწორია.
ამიტომ, ჩვენ უნდა შევინარჩუნოთ გარშემო მომცეთ შემდეგი ელემენტს, მაშინ ჩვენ შეგვიძლია გასათავისუფლებლად
მიმდინარე ელემენტს, და შემდეგ შეგვიძლია განახლება ჩვენი დღევანდელი ელემენტს აღვნიშნო
მომდევნო ელემენტს.
>> ჩვენ loop ხოლო არსებობს ელემენტები ამ უკავშირდება სიაში.
ჩვენ ყველაფერს გავაკეთებთ, რომ ყველა დაკავშირებული სიები hash მაგიდასთან, და კიდევ ჩვენ გავაკეთეთ
რომ, ჩვენ მთლიანად დაცალა hash მაგიდასთან, და ჩვენ გავაკეთეთ.
ასე რომ შეუძლებელია unloads ოდესმე დაბრუნების ცრუ, და როდესაც ჩვენ გავაკეთეთ, ჩვენ
უბრალოდ დააბრუნოს ჭეშმარიტი.