আমার প্রিয় ডেটা স্ট্রাকচারগুলির মধ্যে একটি হল হ্যাশ টেবিল কারণ এটি সহজ এবং শক্তিশালী।
আপনি সম্ভবত এটি আগে ব্যবহার করেছেন কারণ এটি কী-মান জোড়া সঞ্চয় করার একটি কার্যকর উপায়।
একটি হ্যাশ টেবিলের বাস্তবায়নের পিছনে কিছু আকর্ষণীয় কম্পিউটার বিজ্ঞানের ধারণা রয়েছে যা অধ্যয়নের যোগ্য, এবং আমরা এই নিবন্ধে ঠিক এটিই করতে যাচ্ছি!
বালতি এবং হ্যাশ ফাংশন
একটি হ্যাশ টেবিলের মূল ধারণা হল আমাদের দক্ষতার সাথে অনুমতি দেওয়া (O(1) এ ) একটি কী দ্বারা ইন্ডেক্স করা ডেটা পুনরুদ্ধার করুন৷
একটি দ্রুত রিফ্রেশার হিসাবে, একটি হ্যাশ টেবিল ব্যবহার করে রুবিতে এইরকম দেখায়:
দাম ={ আপেল:0.50, আইসক্রিম:3, স্টেক:10} একটি হ্যাশ টেবিল বাস্তবায়ন করতে আমাদের দুটি উপাদান প্রয়োজন:
- টেবিল এন্ট্রি সংরক্ষণ করার জায়গা
- এই ডেটা স্টোরের ভিতরে একটি নির্দিষ্ট অবস্থানে (সূচী) কী/মান জোড়া বরাদ্দ করার একটি উপায়
অন্য কথায়, আমাদের একটি অ্যারে এবং একটি হ্যাশ ফাংশন দরকার৷
একটি সাধারণ হ্যাশ ফাংশন বাস্তবায়ন
হ্যাশ ফাংশন হ্যাশ টেবিলের একটি গুরুত্বপূর্ণ উপাদান।
এই ফাংশনটি কীটিকে একটি সূচকে রূপান্তরিত করে যা এর সম্পর্কিত মান সন্ধান বা আপডেট করতে ব্যবহার করা যেতে পারে।
প্লেইন অ্যারে এবং হ্যাশ টেবিলের মধ্যে এটাই বড় পার্থক্য।
একটি অ্যারেতে, আপনি শুধুমাত্র তাদের সূচকের মাধ্যমে মানগুলি অ্যাক্সেস করতে পারেন এবং সূচকটি শুধুমাত্র একটি সংখ্যা হতে পারে। একটি হ্যাশ টেবিলে, আপনি তাদের কী-এর মাধ্যমে মানগুলি অ্যাক্সেস করেন এবং কী যেকোনো কিছু হতে পারে (স্ট্রিং, প্রতীক, পূর্ণসংখ্যা…), যতক্ষণ না আপনি এটির জন্য একটি হ্যাশ ফাংশন লিখতে পারেন।
আপনি স্ট্রিংগুলির জন্য একটি সাধারণ হ্যাশ ফাংশন লিখতে পারেন সমস্ত অক্ষরগুলিকে তাদের ASCII মানগুলিতে রূপান্তর করে তারপর সেগুলিকে যুক্ত করে৷
এখানে একটি উদাহরণ :
BUCKETS =32def হ্যাশ(ইনপুট) input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETSend
এই পদ্ধতিতে আমরা to_s ব্যবহার করি আমরা একটি স্ট্রিং দিয়ে কাজ করছি তা নিশ্চিত করতে।
এটি আমাদের 'অনির্ধারিত পদ্ধতি' ত্রুটিগুলি এড়াতে সাহায্য করবে৷ তারপর chars এর সংমিশ্রণ (স্ট্রিংটিকে একটি Array এ রূপান্তর করতে এর অক্ষর) এবং inject মান যোগ করার জন্য।
ব্লকের ভিতরে আমি ord ব্যবহার করেছি অক্ষরগুলিকে তাদের অর্ডিনাল মানগুলিতে রূপান্তর করার পদ্ধতি।
অবশেষে, আমি মডিউল অপারেটর % ব্যবহার করেছি নিশ্চিত করুন যে ফলাফলের মান অ্যারের মধ্যে ফিট করে। আমরা এই অ্যারের প্রতিটি এন্ট্রিকে একটি 'বালতি' বলি৷
বালতি বিতরণ
আদর্শভাবে আমরা চাই আমাদের সমস্ত বালতি সমানভাবে পূর্ণ হোক, এটি আমাদের সেরা কার্যক্ষমতা দেবে যখন আমাদের একটি মান পুনরুদ্ধার করতে হবে৷
এই কোডটি ব্যবহার করে আমরা আমাদের হ্যাশ ফাংশন পরীক্ষা করলে কী ঘটে তা দেখা যাক:
# 0table =Array.new(BUCKETS) { 0 } letters =Array('a'..'z')10_000.times do # একটি এলোমেলো স্ট্রিং ইনপুট তৈরি করুন =Array.new(5) { letters.sample }. join # কাউন্ট হ্যাশ ডিস্ট্রিবিউশন টেবিল[হ্যাশ(ইনপুট)] +=1এন্ড এটি নিম্নলিখিত ফলাফলগুলি তৈরি করে:
<প্রে>[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 321, 320, 338, 338, 292, 304, 315, 337, 325, 325, 331, 319, 291]দেখে মনে হচ্ছে আমাদের কীগুলি সমানভাবে বিতরণ করা হয়েছে...
…কিন্তু আমরা যদি বালতির সংখ্যা বাড়াই তাহলে কি হবে?
এই উদাহরণে আমি 128 এর একটি বালতি আকার ব্যবহার করেছি (এটি আগে 32 ছিল):
<প্রে>[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 417 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221,21,21,20,20,20,20,20 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32,31,20, 3 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]এটি আর একটি দুর্দান্ত বিতরণের মতো দেখায় না!
কি হচ্ছে?
সমস্যা হল আমাদের হ্যাশ ফাংশন যথেষ্ট ভাল নয় কারণ একই আকারের সমস্ত স্ট্রিং একটি নির্দিষ্ট পরিসরে থাকে। সেজন্য আমাদের মাঝখানে অনেক খালি বালতি আছে।
একটি উন্নত হ্যাশ ফাংশন
আমাদের স্ট্রিংকে একটি সূচকে রূপান্তর করার জন্য আমাদের আরও ভাল উপায় দরকার। আসুন একটি সম্ভাব্য বাস্তবায়ন দেখে নেওয়া যাক।
BUCKETS =256def হ্যাশ(ইনপুট) ইনপুট.to_s.each_char.inject(0) do |sum, ch| (সমষ্টি <<8) ^ (ch.ord) ^ (অর্থ>> 4) শেষ % BUCKETSend
এখানে যা ঘটছে তা কিছুটা পরিবর্তনশীল (>> সহ &<< অপারেটর)। মানগুলি "এক্সক্লুসিভ বা অপারেটর" (^) ব্যবহার করে একত্রিত করা হয় )।
এই বিট শিফটিং জিনিসগুলিকে মিশ্রিত করবে, যা আমাদের একটি আরও ভাল কী বিতরণ দেবে . নিখুঁত নয়, তবে এটি আমাদের সাধারণ ASCII-ভিত্তিক ফাংশনের চেয়ে ভাল 🙂
৷আপনি যদি একটি সঠিক হ্যাশ ফাংশন চান তবে আপনি MurmurHash এর মতো কিছু দেখবেন, যা আমি বিশ্বাস করি যে রুবি ব্যবহার করে।
সংঘর্ষ হ্যান্ডলিং
আমাদের কাছে এখনও একটি দরকারী হ্যাশ টেবিল নেই৷
৷কেন?
ঠিক আছে, আপনি হয়তো লক্ষ্য করেছেন যে দুটি কী একই সূচকে হ্যাশ করলে তারা পুরানো মানটি ওভাররাইট করবে এবং এটি ভাল নয়!
একে হ্যাশ সংঘর্ষ বলা হয় এবং এর সাথে মোকাবিলা করার জন্য কয়েকটি কৌশল রয়েছে।
উদাহরণস্বরূপ :
- ডাবল হ্যাশিং
- লিনিয়ার প্রোবিং
- পৃথক চেইনিং
আসুন আলাদা চেইনিং এর দিকে নজর দেওয়া যাক, যেখানে আমরা একটি নির্দিষ্ট "বালতি" এর জন্য এন্ট্রিগুলি সংরক্ষণ করতে একটি লিঙ্কযুক্ত তালিকা ব্যবহার করি৷
তাই যদি আমরা ধরে নিই যে :abc &:ccc একই সূচীতে হ্যাশ, আমাদের হ্যাশ টেবিলটি এরকম কিছু দেখাবে:
3:[:abc, 100] -> [:ccc, 200]4:nil5:[:yx, 50]
তারপর সঠিক কী খুঁজে পেতে আমাদের একটি রৈখিক অনুসন্ধানের প্রয়োজন হবে।
এটি আমাদের পারফরম্যান্সের উপর প্রভাব ফেলবে কারণ আমাদের সন্ধানের সময় ধীরে ধীরে O(n) এর দিকে হ্রাস পেতে পারে , প্রত্যাশিত O(1) এর পরিবর্তে .
আপনি যদি এই
O(something)এর সাথে পরিচিত না হন স্বরলিপি যাকে "বিগ-ও নোটেশন" বলা হয়।
লিঙ্ক করা তালিকাটি খুব গভীর থেকে বাড়তে এবং সেইজন্য হ্যাশ টেবিলের কর্মক্ষমতা হ্রাস এড়াতে, একটি বড় সংখ্যক বালতি ব্যবহার করে হ্যাশ টেবিলটি পুনরায় তৈরি করা প্রয়োজন৷
রুবি আপনার জন্য স্বয়ংক্রিয়ভাবে এটি করে, তবে এখনও জেনে রাখা ভাল৷
উপসংহার
এই নিবন্ধটির উদ্দেশ্য আপনি একটি হ্যাশ টেবিল বাস্তবায়ন লিখতে চান না, কিন্তু তারা আসলে কিভাবে কাজ করে তা বুঝতে আপনাকে সাহায্য করা, তাই আমি আশা করি আপনি এটি আকর্ষণীয় পেয়েছেন!
ব্লগটি চালু রাখতে এই পোস্টটি শেয়ার করতে ভুলবেন না 🙂
