লিনিয়ার অনুসন্ধান

লিনিয়ার অনুসন্ধান হচ্ছে ক্রস টেবিল, ডেটা কাঠামো তে ক্রস সংঘর্ষ সমাধান করার জন্য কম্পিউটার প্রোগ্রামিং এর প্রকল্প, যা কী ভ্যালু সংকলন পরিচালনার জন্য এবং মান খোঁজার জন্য ব্যবহৃত হয়। এটি ১৯৫৪ সালে জিন আমদাল, এলেইন এম. ম্যাকগ্রো এবং আর্থার স্যামুয়েল দ্বারা আবিস্কৃত হয়েছিল এবং প্রথম ১৯৬৩ সালে ডোনাল্ড নুথ দ্বারা বিশ্লেষণ করা হয়েছিল।

জন স্মিথ এবং সান্ড্রা ডি (উভয়ই সেল 873 ক্রস করে) মধ্যে সংঘর্ষ সমাধান করা হয়েছে পরবর্তী ফাঁকা স্থান সেল 874 এ স্যান্ড্রা ডি স্থাপন করে

চতুর্ঘাত অনুসন্ধান এবং ডাবল হ্যাশিং এর পাশাপাশি লিনিয়ার অনুসন্ধান হলো মুক্ত সম্ভাষণের নমুনা। এই প্রকল্পে, একটি হ্যাশ টেবিলের প্রতিটি সেল একটি কী কী-ভ্যালু জোড়া সংরক্ষণ করে। যখন হ্যাশ ফাংশন হ্যাশ টেবিলের একটি সেল এর একটি নতুন কী ম্যাপিং করে সংঘর্ষ ঘটায় যেটা ইতোমধ্যে অন্য কী দ্বারা পুর্ণ , লিনিয়ার অনুসন্ধান তখন নিকটবর্তী ফাঁকা অবস্থানের জন্য টেবিল অনুসন্ধান করে এবং সেখানে নতুন কী স্থাপন করায়। অনুরুপভাবে হ্যাশ ফাংশন দ্বারা প্রদত্ত অবস্থান থেকে শুরু করে ক্রমানুসারে টেবিল অনুসন্ধান করে লুকআপ সম্পন্ন করা হয় যতক্ষণ না একটি সদৃশ কী দ্বারা পূর্ণ সেল অথবা ফাঁকা সেল খুঁজে পাওয়া যায়।

থোরাপ এবং ঝাং (২০১২) লিখেন "হ্যাশ টেবিলগুলি সর্বাধিক ব্যবহৃত নথিভুক্ত ডেটা কাঠামো, এবং মানসম্মত হার্ডওয়্যারের লিনিয়ার বা রৈখিক অনুসন্ধানের ব্যবহারের সবচেয়ে জনপ্রিয় বাস্তবায়ন, যা একই সাথে দ্রুত এবং সহজ" লিনিয়ার অনুসন্ধান উচ্চ কর্মক্ষমতা প্রদান করতে পারে এর ভালো উল্লেখযোগ্য অবস্থান এর কারণে, কিন্তু এটি অন্যান্য প্রকল্পের সংঘর্ষের সমাধানের তুলনায় এটির হ্যাশ ফাংশনের প্রতি খুবই সংবেদনশীল। এটি অনুসন্ধান, সন্নিবেশন বা মুছে ফেলার ক্ষেত্রে একই সময় নেয় যখন বিচ্ছিন্ন হ্যাশ ফাংশন ব্যবহার করে সম্পাদন করা হয়, একটি ৫-স্বাধীন হ্যাশ ফাংশন অথবা তালিকাভুক্ত হ্যাশিং। অন্যান্যহ্যাশ ফাংশন যেমন মারমার হ্যাশ অনুশীলন করে ভালো ফলাফল অর্জন করা যেতে পারে।[১]

তথ্যসূত্র সম্পাদনা

  1. Richter, Stefan; Alvarez, Victor; Dittrich, Jens (২০১৫), "A seven-dimensional analysis of hashing methods and its implications on query processing" (পিডিএফ), Proceedings of the VLDB Endowment, 9 (3): 293–331 .