[সঙ্গীত বাজাচ্ছি] ডগ লয়েড: এখন আপনি অ্যারে সম্পর্কে অনেক জানি, এবং আপনি সংযুক্ত তালিকা সম্পর্কে অনেক জানেন. আর আমরা আলোচনা করেছি আগপাছ, আমরা করেছি তালিকা লিঙ্ক যে আলোচনা বড় এবং ছোট পেতে পারেন, কিন্তু তারা আরো আকার গ্রহণ করা. অ্যারে অনেক বেশি সহজবোধ্য করতে হয় ব্যবহার, কিন্তু তারা যতটা এ নিয়ন্ত্রণমূলক আছেন আমরা মাপ সেট করা আছে হিসাবে খুব শুরুতে অ্যারের এবং তারপর আমরা এটা দিয়ে আটকে করছি. 

কিন্তু যে আমরা প্রায় কাছাকাছি করেছি, এর আমাদের বিষয় সব ক্লান্ত লিঙ্ক তালিকা এবং অ্যারে সম্পর্কে. অথবা আমরা আছে? হয়তো আমরা কিছু করতে পারি এমনকি আরো সৃজনশীল. আর ধার দেয় যে সাজানোর একটি হ্যাশ টেবিল ধারণা. 

সুতরাং একটি হ্যাশ টেবিল আমরা চেষ্টা করে যাচ্ছেন একটি লিঙ্ক তালিকা একটি অ্যারের মেশা. আমরা সুবিধাও নিতে যাচ্ছেন অ্যারের, র্যান্ডম এক্সেস মত, শুধু অ্যারে যেতে সক্ষম হচ্ছে উপাদান 4 বা অ্যারে উপাদান 8 জুড়ে বারবার করেও. একেবারে ঠিক, বেশ দ্রুত? 

কিন্তু আমরা আমাদের তথ্য আছে চান কাঠামো সম্প্রসারণ ও সঙ্কোচন পাবে. আমরা না, প্রয়োজন হবে না সীমিত করা চাই. আর আমরা সক্ষম হতে চান যোগ এবং কিছু মুছে ফেলার জন্য খুব সহজেই, যা আপনার যদি মনে থাকে, একটি অ্যারের সাথে খুবই জটিল. আর আমরা এই কল করতে পারেন নতুন জিনিস একটি হ্যাশ টেবিল. 

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

ওয়েল গড়ে সন্নিবেশ একটি হ্যাশ টেবিল মধ্যে বন্ধ ধ্রুব সময় পেতে শুরু করতে পারেন. এবং মুছে ফেলার পেতে পারেন ধ্রুব সময় বন্ধ. এবং লুকআপ পেতে পারেন ধ্রুব সময় বন্ধ. অদূর ভবিষ্যতে আমরা একটি তথ্য আছে না কাঠামো এখনো যে তা করতে পারে, এবং তাই এটি ইতিমধ্যে শোনাচ্ছে একটি বেশ বড় জিনিস ভালো. আমরা সত্যিই নির্বাপিত করেছি তার নিজের প্রতিটি অসুবিধা. 

এই পারফরম্যান্স পেতে যদিও আমরা আপগ্রেড আমরা যোগ কিভাবে পুনর্বিবেচনা করতে হবে গঠন মধ্যে তথ্য. বিশেষভাবে আমরা চাই তথ্য নিজেই আমাদের জানাতে যেখানে এটা কাঠামো যেতে হবে. আর আমরা তখন তা যদি দেখতে প্রয়োজন হলে কাঠামো, আমরা তা খুঁজে পাওয়া প্রয়োজন হলে, আমরা তথ্য তাকান করতে চান আবার ও কার্যকরভাবে পাবে, তথ্য ব্যবহার করে, এলোমেলোভাবে এটি অ্যাক্সেস. শুধু এ খুঁজছেন দ্বারা তথ্য আমরা থাকতে হবে ঠিক আমরা যেখানে একটি ধারণা হ্যাশ টেবিল এটি খুঁজে পাওয়া যাচ্ছে. 

একটি হ্যাশ এখন downside হয় টেবিল সত্যিই তারা যে হয় ক্রম বা তথ্য বাছাই এ বেশ খারাপ. এবং সত্য, আপনি যদি নতুন অর্ডার বা সাজানোর তাদের ব্যবহার করতে তথ্য আপনি সব হারান সুবিধার পূর্বে আপনি সন্নিবেশ এবং মুছে ফেলার পরিপ্রেক্ষিতে ছিল. সময় কাছাকাছি হয়ে এন থেটা, এবং আমরা মূলত করেছি একটি লিঙ্ক তালিকা মধ্যে regressed. আর তাই আমরা শুধুমাত্র হ্যাশ ব্যবহার করতে চান টেবিল আমরা যত্নশীল না হলে তথ্য সাজানো হয় কিনা. কনটেক্সট যা আপনি CS50 মধ্যে তাদের ব্যবহার করব আপনি সম্ভবত না যত্ন তথ্য সাজানো হয় যে. 

সুতরাং একটি হ্যাশ টেবিল সংমিশ্রণ দুই স্বতন্ত্র টুকরা যা দিয়ে আমরা পরিচিত. প্রথমে একটি ফাংশন, যা আমরা সাধারণত একটি হ্যাশ ফাংশন কল. আর যে হ্যাশ ফাংশন যাচ্ছে কিছু অঋণাত্মক পূর্ণসংখ্যা ফিরে যা আমরা সাধারণত ঠিক আছে, একটি হ্যাশকোড কল? দ্বিতীয় খণ্ড, যা একটি অ্যারের, হয় টাইপ আমরা স্টোরিং তথ্য সক্ষম ডাটা স্ট্রাকচার স্থাপন করতে চান. আমরা বন্ধ রাখা হবে এখন জন্য তালিকা উপাদান লিঙ্ক এবং মাত্র একটি বেসিক দিয়ে শুরু এটি প্রায় আপনার মাথা পেতে হ্যাশ টেবিল, এবং তারপর আমরা হয়তো গাট্টা করব আপনার মনের একটি সামান্য বিট যখন আমরা একসঙ্গে অ্যারে এবং লিঙ্কটি তালিকা একত্রিত. 

মৌলিক ধারণা, যদিও আমরা কিছু তথ্য নেওয়া হয়. আমরা যে তথ্য মাধ্যমে চালানো হ্যাশ ফাংশন. তাই তথ্য প্রক্রিয়াকরণ করা হয় এবং এটা ঠিক আছে, একটি সংখ্যা খুঁজে spits? এবং তারপর যে নম্বর দিয়ে আমরা শুধু তথ্য সংরক্ষণ আমরা সঞ্চয় করতে চান যে অবস্থানে অ্যারে. সুতরাং উদাহরণস্বরূপ আমরা হয়তো আছে স্ট্রিং এই হ্যাশ টেবিল. এটা তাই, এটা 10 উপাদানের পেয়েছিলাম আমরা এটা 10 স্ট্রিং ফিট করতে পারে. 

আসুন আমরা জন হ্যাশ চান বলে. জন সুতরাং তথ্য হিসাবে আমরা সন্নিবেশ করতে চান কোথাও এই হ্যাশ টেবিল মধ্যে. কোথায় আমরা এটা করা হয়? ওয়েল সাধারণত সঙ্গে একটি অ্যারে পর্যন্ত আমরা সম্ভবত অ্যারে পাঁচ 0 এটি করা হবে. কিন্তু এখন আমরা এই নতুন হ্যাশ ফাংশন আছে. 

আর আসুন আমরা জন চালানোর যে বলা যাক এই হ্যাশ ফাংশন মাধ্যমে এবং এটা 4 খুঁজে spits হচ্ছে. আমরা যেখানে ওয়েল দ্যাট জন লাগাতে চান যাচ্ছে. আমরা অ্যারে অবস্থানে জন লাগাতে চান 4, আমরা again-- জন হ্যাশ যদি কারণ এর পরে আমরা বলতে দিন অনুসন্ধান ও দেখতে চাই জন এই হ্যাশ উপস্থিত থাকলে আমরা যা করতে হবে সব টেবিলের একই হ্যাশ মাধ্যমে এটি চালানো হয় ফাংশন, সংখ্যা 4 নামা এবং জন এটি পাবে অবিলম্বে আমাদের তথ্য কাঠামো. যে বেশ ভাল. 

আসুন আমরা এখন এই কাজ করা যাক বলতে আবার, আমরা পল হ্যাশ চান. আমরা পল যোগ করতে চান এই হ্যাশ টেবিল মধ্যে. এই সময় আমরা চালানো বলে চলুন শুরু করা যাক হ্যাশ ফাংশন মাধ্যমে পল, উৎপন্ন হয় যে হ্যাশকোড 6. অবশ্য, এখন আমরা পল লাগাতে পারেন অ্যারে পাঁচ 6. আর আমরা কিনা সন্ধান করার প্রয়োজন হলে পল এই হ্যাশ টেবিল হয়, আমরা যা করতে হবে সব পল চালানো হয় হ্যাশ ফাংশন মাধ্যমে আবার এবং আমরা আবার 6 পেতে যাচ্ছেন. 

এবং তারপর আমরা শুধু চেহারা অ্যারে পাঁচ 6 এ. পল আছে কি? যদি তাই হয়, তিনি হ্যাশ টেবিল আছে. পল নয় কি? তিনি হ্যাশ টেবিল না. এটা বেশ সহজবোধ্য. 

এখন আপনি কিভাবে একটি হ্যাশ ফাংশন নির্ধারণ না? ওয়েল সত্যিই কোন সীমা আছে সম্ভব হ্যাশ ফাংশন সংখ্যা. আসলে একটি নম্বর, সত্যিই আছে ইন্টারনেটে সত্যিই ভাল বেশী. একটি সংখ্যা, সত্যিই আছে ইন্টারনেটে সত্যিই খারাপ বেশী. এটি বেশ সহজ একটা বাজে জিনিস লিখতে. 

তাই কি একটি ভাল তোলে আপ হ্যাশ ফাংশন, ডান? ভাল একটি ভাল হ্যাশ ফাংশন উচিত শুধুমাত্র তথ্য কুচি হচ্ছে ব্যবহার, এবং তথ্য সব কুচি হচ্ছে. সুতরাং আমরা anything-- ব্যবহার করতে চান না আমরা কিছু একত্রীভূত করে না তথ্য ছাড়া অন্য. এবং আমরা তথ্য সব ব্যবহার করতে চান. আমরা শুধু একটি স্থানের ব্যবহার করতে চান না এটা নিয়ে আমরা এটা সব ব্যবহার করতে চান. একটি হ্যাশ ফাংশন উচিত এছাড়াও নিয়ন্ত্রণবাদী হতে. ওটার মানে কি? আচ্ছা এটা মানে যে প্রতিটি সময় আমরা তথ্য সঠিক একই টুকরা পাস হ্যাশ ফাংশন মধ্যে আমরা সবসময় একই হ্যাশকোড নামা. আমি শুধুমাত্র জন পাস হলে হ্যাশ ফাংশন আমি 4 নামা. আমি যে কাজ করতে সক্ষম হওয়া উচিত 10,000 বার ও আমি সবসময় 4 কিনবো. সুতরাং কোন র্যান্ডম সংখ্যার কার্যকরভাবে আমাদের হ্যাশ জড়িত করা যাবে tables-- আমাদের হ্যাশ ফাংশন. 

একটি হ্যাশ ফাংশন এছাড়াও উচিত অবিশেষে তথ্য বিতরণ. প্রত্যেক সময় আপনি মাধ্যমে তথ্য চালানোর প্রয়োজন হলে হ্যাশ ফাংশন আপনি, হ্যাশকোড 0 পেতে যে অধিকার, সম্ভবত তাই মহান না? আপনি সম্ভবত বড় করতে চান হ্যাশ কোড একটি পরিসীমা. এছাড়াও কিছু ছড়িয়ে যেতে পারে টেবিল জুড়ে আউট. আর এটা যদি সত্যিই মহান হতে হবে জন ও জনাথন মত একই তথ্য, হয়তো তৌল ছড়িয়ে পড়ে হ্যাশ টেবিল বিভিন্ন স্থানে. এটা একটা চমৎকার সুবিধা হবে. 

এখানে একটি হ্যাশ ফাংশন একটি উদাহরণ. আমি আগে এই এক আপ লিখেছেন. এটি একটি বিশেষ নয় ভাল হ্যাশ ফাংশন সত্যিই না যে কারণে এই মুহূর্তে মধ্যে যাওয়া বহন করে. কিন্তু তুমি এখানে কি ঘটছে দেখতে পাচ্ছ? আমরা একটি পরিবর্তনশীল ঘোষণা করছি এটি দেখে মনে হচ্ছে যোগফল এবং 0 সমান এটি সেট বলা হয়. এবং তারপর দৃশ্যত আমি কিছু কাজ করছি এতক্ষণ strstr [ঞ] সমান নয় হিসাবে 0 ব্যাকস্ল্যাশ করতে. আমি সেখানে কি করছি? 

এটি মূলত শুধু আরেকটি হল [বাস্তবায়নের উপায়? strl?] আপনি করেছি যখন এবং detecting স্ট্রিং শেষে পৌঁছে. তাই আমি আসলে হবে না স্ট্রিং এর দৈর্ঘ্য নিরূপণ, আমি আঘাত যখন আমি শুধু ব্যবহার করছি ব্যাকস্ল্যাশ 0 চরিত্র আমি জানি আমি স্ট্রিং শেষে পৌঁছে গেছেন. এবং তারপর আমি রাখা যাচ্ছে না স্ট্রিং মাধ্যমে iterating, strstr [ঞ] যোগ এ তারপর সমষ্টি, এবং যাও দিনের শেষে সমষ্টি গেলিক ফিরে যাচ্ছে HASH_MAX. 

মূলত এই সব হ্যাশ ফাংশন আপ যোগ হয় করছে এর ASCII মান সব আমার স্ট্রিং, এবং তারপর এটি কিছু হ্যাশকোড ফিরে HASH_MAX দ্বারা modded. এটা সম্ভবত আকার আমার অ্যারের, ডান? আমি হ্যাশ পেয়ে যেতে চাই না সঙ্কেত আমার অ্যারের সাইজ 10 থেকে হয়ে থাকে, আমি পেয়ে হতে চান না খুঁজে হ্যাশ কোড 11, 12, 13, আমি শুধুমাত্র কিছু করা যাবে না অ্যারের সেইসব অবস্থানের, যে অবৈধ হবে. আমি একটি সেগমেন্টেশন ফল্ট ভোগে চাই. 

এখন এখানে অন্য একটি দ্রুত সরাইয়া হয়. সাধারণত আপনি সম্ভবত যাচ্ছেন না আপনার নিজস্ব হ্যাশ ফাংশন লিখতে চান. এটা আসলে একটি বিট একটি শিল্প, একটি বিজ্ঞান. এবং তাদের মধ্যে যে যায় অনেক আছে. আমি ভালো বলেন ইন্টারনেট, পূর্ণ সত্যিই ভাল হ্যাশ ফাংশন, এবং আপনাকে ইন্টারনেট ব্যবহার করা উচিত এটা সত্যিই কারণ হ্যাশ ফাংশন খুঁজে শুধু ধরনের একটি অপ্রয়োজনীয় সময় বর্জ্য আপনার নিজের তৈরি করা. 

আপনি সহজ ওগুলো লিখতে পারেন পরীক্ষার উদ্দেশ্যে. কিন্তু আপনি আসলে করতে যাচ্ছি যখন তথ্য হ্যাশ এবং এটি সংরক্ষণ শুরু আপনি আছেন একটি হ্যাশ টেবিল মধ্যে সম্ভবত চান যাচ্ছে উত্পন্ন হয় যে কিছু ফাংশন ব্যবহার আপনার জন্য, যে ইন্টারনেটে বিদ্যমান. আপনি শুধু নিশ্চিত হতে থাকে আপনার সূত্র cite. কোনো কারণ নেই এখানে কিছু থাকতাম দ্বিতীয় তলায়. 

কম্পিউটার বিজ্ঞান সম্প্রদায় স্পষ্টভাবে মান ক্রমবর্ধমান, এবং সত্যিই ওপেন সোর্স, এবং এটা সত্যিই গুরুত্বপূর্ণ আপনার সূত্র cite যাতে মানুষ স্বীকৃতি পেতে পারেন তারা যে কাজ কমিউনিটি সুবিধার করছেন. তাই সবসময় sure-- হতে এবং শুধুমাত্র হ্যাশ জন্য ফাংশন, কিন্তু সাধারণত যখন আপনি বাইরের উত্স থেকে কোড ব্যবহার, সবসময় আপনার সোর্স উদ্ধৃত. করেনি এমন ব্যক্তিকে ঋণ দিতে কাজের কিছু তাই আপনাকে করতে হবে না. 

ঠিক আছে, তাই এর এই পরিদর্শন দিন একটি দ্বিতীয় জন্য হ্যাশ টেবিল. আমরা বাকি এই যেখানে আমরা ঢোকানো পরে বন্ধ এই হ্যাশ টেবিল মধ্যে জন এবং পল. আপনি এখানে একটি সমস্যা দেখতে পান কি? আপনি দুটি দেখতে পারে. কিন্তু বিশেষ করে, আপনি কি এই সম্ভাব্য সমস্যা দেখতে? 

আমি কি রিংগো হ্যাশ, এবং এটা যদি প্রক্রিয়াকরণের পরে দেখা যাচ্ছে যে হ্যাশ ফাংশন মাধ্যমে যে তথ্য রিংগো এছাড়াও হ্যাশকোড 6 উত্পন্ন. আমি ইতিমধ্যে এ তথ্য পেয়েছেন hashcode-- অ্যারে পাঁচ 6. সুতরাং এটি সম্ভবত একটি বিট হতে যাচ্ছে এখন আমার জন্য একটা সমস্যা, ঠিক? 

আমরা একটি সংঘর্ষের এই কল. এবং সংঘর্ষের সময় দুটি ঘটে তথ্য টুকরা একই হ্যাশ মাধ্যমে চালানো ফাংশন একই হ্যাশকোড ফলন হয়. সম্ভবতঃ আমরা এখনও উভয় পেতে চান হ্যাশ টেবিল মধ্যে তথ্য টুকরা, অন্যথায় আমরা রিংগো চলমান করা হবে না ইচ্ছামত হ্যাশ ফাংশন মাধ্যমে. আমরা সম্ভবতঃ পেতে চান যে অ্যারের মধ্যে Ringo. 

আমরা যদিও এটা করতে না, তিনি যদি এবং পল উভয় ফলন হ্যাশকোড 6? আমরা পল সেগুলিও ফরোয়ার্ড করতে চান না, আমরা পল খুব হতে চাই. সুতরাং আমরা পেতে একটি উপায় খুঁজে বের করতে হবে হ্যাশ টেবিল মধ্যে উপাদান যে এখনও আমাদের দ্রুত অপরিবর্তিত সন্নিবেশ এবং দ্রুত বর্ণন আপ. এবং তা মোকাবেলা করার জন্য একটি উপায় হয় অনুসন্ধান রৈখিক কিছু বলা না. 

আমরা একটি আছে এই পদ্ধতি ব্যবহার সংঘর্ষের, ভাল, আমরা কি করব? আচ্ছা আমরা অ্যারে পাঁচ তাকে রাখা যাবে না 6, বা যাই হোক না কেন হ্যাশকোড উত্পন্ন হয়, এর হ্যাশকোড প্লাস 1 এ তাকে করা যাক. আর যে পূর্ণ চলুন যদি হ্যাশকোড প্লাস 2 তাকে রাখা. এই হচ্ছে সুবিধার তিনি যদি না ঠিক তা কেমন করে হয় মনে হয় যেখানে, এবং আমরা অনুসন্ধান শুরু করতে হবে, হয়তো আমরা খুব বেশী দূরে যেতে হবে না. হয়তো আমরা অনুসন্ধান করতে হবে না হ্যাশ টেবিল সব n উপাদান. হয়তো আমরা আপনাকে আছে তাদের একটি দম্পতি. 

আর তাই আমরা এখনও প্রতি tending করছি গড় ক্ষেত্রে 1 পাসে বনাম হচ্ছে যে এন যাও বন্ধ, তাই হয়ত যে কাজ করব. সুতরাং আসুন কিভাবে এই দেখতে দিন বাস্তবে কাজ পারে. এবং হয়তো আমরা সনাক্ত করা সম্ভব, তাহলে দেখা যাক এখানে ঘটতে পারে যে সমস্যা. 

আসুন আমরা বার্ট হ্যাশ বলা যাক. তাই এখন আমরা একটি নতুন সেট চালানো চলুন হ্যাশ ফাংশন মাধ্যমে স্ট্রিং, এবং আমরা হ্যাশ মাধ্যমে বার্ট চালানো ফাংশন, আমরা হ্যাশকোড 6 পেতে. আমরা দেখব, আমরা 6 দেখতে খালি, তাই আমরা সেখানে বার্ট লাগাতে পারেন. 

এখন আমরা Lisa এবং যে হ্যাশ এছাড়াও হ্যাশকোড 6 উত্পন্ন. অবশ্য, এখন আমরা এই ব্যবহার করছেন রৈখিক, আমরা 6 থেকে খেলা আরম্ভ করার পদ্ধতি নীরিক্ষণ আমরা 6 পূর্ণ দেখতে. আমরা 6 লিসা করা যাবে না. তাই যেখানে আমরা যেতে পারি না? এর 7 যাই. 7 এর খালি, তাই কাজ করে. সুতরাং আসুন আছে লিসা করা যাক. 

এখন আমরা হোমার হ্যাশ এবং আমরা 7 পেতে. ওকে আমরা ভাল জানি 7 এর পূর্ণ যে এখন, তাই আমরা সেখানে হোমার করা যাবে না. সুতরাং আসুন 8 যেতে দিন. 8 পাওয়া যায়? হাঁ, এবং 7 8 এর বন্ধ, তাই যদি আমরা করছি অনুসন্ধান শুরু করতে হবে খুব দূরে যেতে হবে যাচ্ছে না. আর তাই এর 8 এ হোমার করা যাক. 

এখন আমরা হ্যাশ Maggie এবং 3 আয় ভগবান্ আমরা শুধু সেখানে ম্যাগি লাগাতে সক্ষম হন. আমরা কোনো কাজ করতে হবে না সাজান যে জন্য নীরিক্ষণ. এখন আমরা কানা হ্যাশ, এবং কানা 6 ফেরৎ. 

ওয়েল 6, 8 পূর্ণ, 7 পূর্ণ, পূর্ণ 9, ঠিক আছে 9 খালি, ঈশ্বরকে ধন্যবাদ. আমি 9 এ কানা লাগাতে পারেন. ইতিমধ্যে আমরা শুরু করছি দেখতে পারেন আমরা যেখানে এখন এই সমস্যা আছে ধরনের জিনিষ প্রসারিত শুরু এর দূরে তাদের হ্যাশ কোড থেকে. আর 1 এর যে থেটা, যে গড় ধ্রুব সময় হচ্ছে ক্ষেত্রে, একটু more-- পেতে শুরু হয় আরো একটু ঝোঁক শুরু এন থেটা দিকে. আমরা যে হারাতে শুরু করছেন হ্যাশ টেবিল সুবিধা. 

আমরা শুধু দেখেছি যে এই সমস্যা ক্লাস্টারিং কিছু বলা হয়. আর সম্পর্কে সত্যিই খারাপ কি ক্লাস্টারিং যে আপনি একবার এখন পাশ হয় দুটি উপাদান দ্বারা আছে এটা আরও বেশি সম্ভাবনা তোলে প্রান্তের, আপনি ডবল আছে সুযোগ, আপনি যাচ্ছেন যে অন্য সংঘর্ষের আছে যে থোকা, এবং ক্লাস্টারের এক হত্তয়া হবে. আর আপনি ক্রমবর্ধমান এবং ক্রমবর্ধমান যাব সংঘর্ষের হচ্ছে আপনার সম্ভাবনা. এবং শেষ পর্যন্ত এটা ঠিক যেমন খারাপ এ সব তথ্য বাছাই না. 

অন্যান্য সমস্যা যদিও আমরা হয় এখনও, এবং এখন পর্যন্ত এই বিন্দু পর্যন্ত, আমরা শুধু সাজানোর চলেছি একটি হ্যাশ টেবিল কি বুঝতে, আমরা এখনও শুধুমাত্র 10 স্ট্রিং জন্য রুম আছে. আমরা হ্যাশ অবিরত করতে চান তাহলে স্প্রিংফিল্ড নাগরিকদের, আমরা কেবল সেখানে তাদের 10 পেতে পারেন. আর আমরা, চেষ্টা এবং একটি 11 বা 12 যোগ হলে আমরা তাদের করা একটি জায়গা আছে না. আমরা শুধু কাছাকাছি কাটনা হতে পারে বৃত্ত, একটি খালি স্পট খুঁজে বের করার চেষ্টা করুন এবং আমরা হয়তো আটকে অসীম লুপ. 

তাই ধারণা করা ধার এই সাজানোর কিছু chaining বলা. আর এই আমরা আনতে যাচ্ছেন কোথায় ফিরে ছবি মধ্যে লিঙ্ক তালিকা. যদি পরিবর্তে শুধু সংরক্ষণকারী অ্যারের মধ্যে তথ্য নিজেই, অ্যারের প্রতিটি উপাদান পারা একাধিক টুকরা ডাটা রাখা? ভাল যে ঠিক আছে, জানার জন্য না? আমরা যে একটি অ্যারের শুধুমাত্র পারেন জানি একটি অ্যারের প্রতিটি উপাদান hold-- কেবল এক টুকরা রাখা যাবে যে ডাটা টাইপ ডাটা. 

কিন্তু তা যদি যে ডাটা টাইপ একটি লিঙ্ক তালিকা, ডান? তাই কি যদি ভাষার অ্যারের উপাদান ছিল একটি লিঙ্ক তালিকা মাথার একটি পয়েন্টার? এবং তারপর আমরা গড়ে তুলতে পারে যারা সংযুক্ত তালিকা এবং, ইচ্ছামত তাদের হত্তয়া লিঙ্ক তালিকা অনুমতি কারণ আমাদের বড় হয়ে যায় এবং আরো অনেক সঙ্কুচিত একটি অ্যারের না সহজে তুলনায়. তাই কি আমরা এখন ব্যবহার করা হলে, আমরা ঠিক আছে, এই লিভারেজ? আমরা এই চেইন বাড়া শুরু এই অ্যারে অবস্থানের আউট. 

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

এবং চেহারা আপ জন্য, আমরা ভাল জানি না একটি লিঙ্ক তালিকায় সন্ধান ঠিক আছে, একটা সমস্যা হতে পারে? আমরা মাধ্যমে অনুসন্ধান করতে হবে শুরু থেকে এটা শেষ করতে. কোন র্যান্ডম নেই একটি লিঙ্ক তালিকা অ্যাক্সেস. কিন্তু যদি এর পরিবর্তে এক থাকার লিঙ্ক একটি লুকআপ n হে হতে হবে যেখানে তালিকা, আমরা এখন 10 লিঙ্ক তালিকা আছে, বা 1,000 লিঙ্ক তালিকা, এখন তা 10 দ্বারা বিভক্ত n হে, বা n হে 1,000 দ্বারা বিভক্ত. 

আর আমরা কথা বলছে এমন সময় তাত্ত্বিকভাবে জটিলতা সম্পর্কে আমরা বাস্তব, ধ্রুবক উপেক্ষা এই জিনিস আসলে ব্যাপার বিশ্বের, ঠিক আছে? আমরা আসলে লক্ষ্য করবেন এই যে এরকম দ্রুত 10 বার চালানোর, বা 1,000 গুণ দ্রুত, আমরা দীর্ঘ এক বিতরণ করছি কারণ 1,000 ছোট চেইন জুড়ে চেইন. এবং তাই আমরা আছে প্রতিটি সময় আপনাকে আমরা যা করতে পারেন যারা চেইন এক মাধ্যমে আমরা পরোয়া করি না 999 চেইন উপেক্ষা সম্পর্কে, এবং শুধু যে এক অনুসন্ধান. 

যা গড়ে হয় 1,000 বার খাটো হতে. আর তাই আমরা এখনও ধরণের হয় এই গড় ক্ষেত্রে প্রতি tending ধ্রুব সময় হচ্ছে, কিন্তু শুধুমাত্র আমরা ওঠানামা করছে, কারণ কিছু বিপুল ধ্রুব ফ্যাক্টর দ্বারা বিভাজক. কিভাবে এই পারে দেখা যাক আসলে যদিও চেহারা. তাই এই আমরা ছিল হ্যাশ টেবিল ছিল আমরা একটি হ্যাশ টেবিল ঘোষণা করার আগে যে 10 পংক্তি সংরক্ষণ করতে সক্ষম ছিল না. আমরা আর যে কাজ করতে যাচ্ছেন না. আমরা ইতিমধ্যে জানি যে পদ্ধতি সীমাবদ্ধতার. এখন আমাদের হ্যাশ টেবিল হতে যাচ্ছে 10 নোড পয়েন্টার একটি অ্যারের লিঙ্ক তালিকা মাথা. 

এবং তা এখনই নাল. যারা 10 পয়েন্টার প্রত্যেকই নাল. কিছুই আমাদের মধ্যে নেই এই মুহূর্তে টেবিল হ্যাশ. 

এখন এর কিছু করা শুরু করা যাক এই হ্যাশ টেবিল মধ্যে কিছু. আর এর এই পদ্ধতি কিভাবে দেখতে দিন আমাদের অল্প লাভবান হতে যাচ্ছে. এর এখন জোয়ি হ্যাশ যাক. আমরা স্ট্রিং জোয়ি মাধ্যমে চালানো হবে করব একটি হ্যাশ ফাংশন এবং আমরা 6 আসতে. আচ্ছা আমরা এখন কি করব? 

অবশ্য, এখন সংযুক্ত তালিকার সঙ্গে কাজ, আমরা অ্যারে সঙ্গে কাজ করছি না. এবং আমরা কাজ করছি যখন সংযুক্ত তালিকার সঙ্গে আমরা আমরা পরিবর্তনশীল শুরু করতে হবে জানি স্থান ও ভবন চেইন বণ্টন. যে ধরণের যারা কোর how-- এর একটি লিঙ্ক তালিকা নির্মাণের উপাদান. তাই পরিবর্তনশীল এর দিন জোয়ি জন্য স্থান বরাদ্দ করা, এবং তারপর এর চেইন তাকে যোগ দিন. 

তাই এখন আমরা কাজ করেছি তা দেখুন. আমরা জোয়ি হ্যাশ যখন আমরা হ্যাশকোড 6 পেয়েছিলাম. অ্যারে পাঁচ 6 এ এখন পয়েন্টার একটি লিঙ্ক তালিকা মাথা স্থানটিকে, এবং এই মুহূর্তে এটা কেবলমাত্র একটি লিঙ্ক তালিকা উপাদান. আর যে নোড লিঙ্ক তালিকা জোয়ি হয়. 

আমরা জোয়ি সন্ধান করার প্রয়োজন হলে তাই পরে, আমরা শুধু আবার জোয়ি হ্যাশ, আমরা আমাদের কারণ আবার 6 পেতে হ্যাশ ফাংশন নিয়ন্ত্রণবাদী হয়. এবং তারপর আমরা মাথা এ শুরু লিঙ্ক তালিকা নির্দিষ্ট অ্যারে অবস্থান দ্বারা যাও 6, এবং আমরা পুনরুক্তি করতে পারেন জোয়ি খুঁজে বের করার চেষ্টা করুন যে জুড়ে. আর আমরা গড়ে তুলতে হলে আমাদের কার্যকরভাবে হ্যাশ টেবিল, এবং আমাদের হ্যাশ ফাংশন কার্যকরভাবে ভাল তথ্য বিতরণ করতে, গড়ে যারা প্রতিটি লিঙ্ক ভাষার অ্যারে অবস্থানে তালিকা তাহলে মাপ 1/10 হতে হবে আমরা কেবলমাত্র একটি বিশাল হিসেবে এটি ছিল এটা সবকিছু সাথে লিঙ্ক তালিকা. 

আমরা বিশাল লিঙ্ক যে বিতরণ যদি 10 লিঙ্ক তালিকায় জুড়ে তালিকা প্রতিটি তালিকা 1/10 আকার হতে হবে. আর এভাবেই 10 বার দ্রুততর মাধ্যমে আপনাকে. সুতরাং আসুন আবার এই কাজ করা যাক. এর এখন রস হ্যাশ যাক. 

আর এর যখন আমরা যে রস, বলা যাক আমরা ফিরে পেতে হ্যাশ কোড 2 হয়. অবশ্য, এখন আমরা একটি পরিবর্তনশীল বরাদ্দ নতুন নোড, আমরা যে নোড রস করা এবং আমরা অ্যারে পাঁচ এখন বলতে 2, নাল প্রতি নির্দেশ পরিবর্তে, একটি লিঙ্ক প্রধান স্থানটিকে যার একমাত্র নোড তালিকায় রস হয়. এবং আমরা এই আরো এক সময় নির্বাচন করতে পারবেন রাহেলা হ্যাশ এবং হ্যাশকোড 4 পেতে পারেন. এ রেচেল করা, নতুন নোডের malloc নোড, এবং একটি অ্যারের পাঁচ বলে 4 এখন মাথা স্থানটিকে যার একটি লিঙ্ক তালিকা একমাত্র উপাদান রেচেল হতে হবে. 

ঠিক আছে কিন্তু তা যদি ঘটে আমরা একটি সংঘর্ষের আছে? আসুন আমরা দুর্ঘটনায় হ্যান্ডেল কিভাবে দেখতে দিন পৃথক chaining পদ্ধতি ব্যবহার করে. এর চন্দ্র হ্যাশ যাক. আমরা হ্যাশকোড 6 পেতে. আমাদের পূর্ববর্তী উদাহরণে আমরা শুধু ছিল অ্যারের মধ্যে পংক্তি সংরক্ষণ. এই একটা সমস্যা ছিল. 

আমরা জখম করা চাই না জোয়ি, এবং আমরা ইতিমধ্যে করেছি আমরা কিছু ক্লাস্টারিং পেতে পারেন যে দেখা সমস্যা আমরা চেষ্টা এবং ধাপে মাধ্যমে ও প্রোবের. কিন্তু তা যদি আমরা শুধু এই ধরনের এই অধিকার, একই ভাবে আচরণ? এটা শুধু একটি উপাদান যোগ মত একটি লিঙ্ক তালিকা মাথার. চন্দ্র জন্য এর মাত্র malloc স্থান যাক. 

আমরা চন্দ্র এর পরের পয়েন্টার পয়েন্ট বলবো লিঙ্ক তালিকা পুরোনো মাথা থেকে, এবং সকাল 6 শুধু স্থানটিকে লিঙ্ক তালিকা নতুন প্রধান. আর এখন আমরা চন্দ্র পরিবর্তন করেছি, দেখুন. আমরা এখন দুই সংরক্ষণ করতে পারেন হ্যাশকোড 6 উপাদান, এবং আমরা যে কোন সমস্যা হবে না. 

যে অনেক সুন্দর সব chaining আছে. আর chaining তা হ 'ল যে পদ্ধতি আপনি যদি জন্য সবচেয়ে কার্যকর হতে যাচ্ছে আপনি একটি হ্যাশ টেবিল তথ্য সংরক্ষণ করা হয়. কিন্তু এই সমন্বয় অ্যারে এবং সংযুক্ত তালিকা একসঙ্গে সত্যিই একটি হ্যাশ টেবিল গঠন নাটকীয়ভাবে আপনার ক্ষমতা উন্নত বিপুল পরিমাণ ডেটা সংরক্ষণ করা খুব দ্রুত এবং দক্ষতার অনুসন্ধান যে তথ্য মাধ্যমে. 

আরও এখনও নেই সেখানে আউট ডাটা স্ট্রাকচার যে এমনকি একটি বিট হতে পারে নিশ্চয়তা পদ ভালো আমাদের সন্নিবেশ, অপসারণ, এবং খোঁজা বার আরও দ্রুত হয়. আর আমরা চেষ্টা একটি ভিডিওতে দেখতে পাবেন. আমি ডগ লয়েড আছি, এই CS50.