Linear Probing
Duration: 6 min
This video lesson is available to enrolled students.
Inside: a video lesson and guided study material.
Module outline
- About the Course: About the Course
- Paper-1 & 2 | Basic Numeracy / आधारभूत संख्यात्मक योग्यता: Ratio and Proportion / अनुपात और समानुपात, Divisibility Rules / विभाज्यता के नियम, Mixture and Alligation / मिश्रण और एलिगेशन, Permutation and Combination / क्रमचय और संचय, Logarithm / लघुगणक, Number System / संख्या पद्धति, HCF and LCM / महत्तम समापवर्तक और लघुत्तम समापवर्त्य, अनुक्रम, श्रेणी और संयोजन / Sequences, Series and Combinatorics, Time, Speed and Distance / समय, चाल और दूरी, Percentage / प्रतिशत, Average / औसत, Solid Mensuration / घन क्षेत्रमिति, Age Problems / आयु संबंधी प्रश्न, Arithmetic / अंकगणित, Statistics / सांख्यिकी, Probability / प्रायिकता, Profit, Loss and Discount / लाभ, हानि और बट्टा, Simple and Compound Interest / साधारण और चक्रवृद्धि ब्याज, Partnership / साझेदारी, Speed Mathematics and Basic Mathematics / द्रुत गणित और आधारभूत गणित, Algebra / बीजगणित, Simplification, Indices and Surds / सरलीकरण, घातांक और करणी, Time and Work / समय और कार्य, Pipe and Cistern / नल और टंकी, RSSB Specific Videos - Basic Numeracy / RSSB विशेष वीडियो - आधारभूत संख्यात्मक योग्यता, Sets, Relations, Functions and Discrete Mathematics / समुच्चय, संबंध, फलन और विविक्त गणित, Number Systems and Number Theory / संख्या पद्धति और संख्या सिद्धांत, Coordinate Geometry, Vectors and 3D Geometry / निर्देशांक ज्यामिति, सदिश और त्रिविमीय ज्यामिति, Polynomials, Equations and Complex Numbers / बहुपद, समीकरण और सम्मिश्र संख्याएँ, वास्तविक और सम्मिश्र विश्लेषण / Real and Complex Analysis, Plane Mensuration / समतल क्षेत्रमिति, आव्यूह और रैखिक बीजगणित / Matrices and Linear Algebra, Production and Costs / उत्पादन एवं लागत, Business Finance, Banking and Financial Markets / व्यावसायिक वित्त, बैंकिंग एवं वित्तीय बाज़ार, Euclidean Geometry and Mensuration / यूक्लिडीय ज्यामिति और क्षेत्रमिति, Statistics and Probability / सांख्यिकी और प्रायिकता, Integers & Rational Numbers / पूर्णांक और परिमेय संख्याएँ
- Paper-1 & 2 | Data Interpretation / आँकड़ों की व्याख्या: Data Interpretation / आँकड़ा निर्वचन
- Paper-1 & 2 | General Mental Ability / सामान्य मानसिक योग्यता: Mental Ability / मानसिक योग्यता, RSSB Specific Videos - Mental Ability / RSSB विशेष वीडियो - मानसिक योग्यता
- Paper-1 & 2 | Logical Reasoning and Analytical Ability / तार्किक तर्कणा एवं विश्लेषणात्मक क्षमता: Series / श्रेणी, Coding-Decoding / कूट लेखन एवं कूट वाचन, Data Sufficiency / आँकड़ों की पर्याप्तता, Non-Verbal Reasoning / अशाब्दिक तर्क, Syllogisms / न्यायवाक्य, Seating Arrangement and Puzzles / बैठक व्यवस्था एवं पहेलियाँ, Blood Relations / रक्त संबंध, Direction and Distance / दिशा एवं दूरी, Analytical Reasoning (Counting Figures Reasoning) / विश्लेषणात्मक तर्क (आकृति गणना तर्क), Mathematical Operations and Missing Numbers / गणितीय संक्रियाएँ एवं लुप्त संख्या, Calendar and Clock / कैलेंडर एवं घड़ी, Clock / घड़ी, Cubes, Dice and Figure Counting / घन, पासा एवं आकृतियों की गिनती, Venn Diagrams, Syllogism and Inequalities / वेन आरेख, न्याय वाक्य एवं असमानता, Analogy and Classification / सादृश्यता एवं वर्गीकरण, Order and Ranking / क्रम एवं रैंकिंग, Statement-Based Reasoning / कथन आधारित तार्किक विवेचन, Data Arrangement / आँकड़ों की व्यवस्था, Alphabet and Number Test / वर्णमाला एवं संख्या परीक्षण, Crypt Arithmetic / कूट अंकगणित, Data Sufficiency and Decision Making / आँकड़ों की पर्याप्तता एवं निर्णय क्षमता, Maps, Remote Sensing and Geographical Techniques / मानचित्र, सुदूर संवेदन एवं भौगोलिक तकनीकें, Partnership Accounts / साझेदारी लेखांकन, Inequality / असमानता
- Paper-1 & 2 | Decision Making and Problem Solving / निर्णय लेना एवं समस्या समाधान: Data Sufficiency and Decision Making / आँकड़ों की पर्याप्तता एवं निर्णय क्षमता
- Paper-1 | General Science / सामान्य विज्ञान: Scientific Achievements and Research / वैज्ञानिक उपलब्धियाँ और अनुसंधान, कोशिका: संरचना एवं कार्य / Cell: Structure and Function, ऊष्मागतिकी एवं साम्यावस्था / Thermodynamics and Equilibrium, RSSB Specific Videos / RSSB विशेष वीडियो, Agronomy and Farming Systems / शस्य विज्ञान एवं कृषि प्रणालियाँ, Evolution / विकास, Biotechnology / जैव प्रौद्योगिकी, Periodic Classification and Chemical Bonding / आवर्त वर्गीकरण एवं रासायनिक आबंधन, d- and f-Block Elements and Coordination Compounds / d- एवं f-ब्लॉक तत्व तथा उपसहसंयोजन यौगिक, Organic Chemistry: Basic Principles and Isomerism / कार्बनिक रसायन: मूल सिद्धांत एवं समावयवता, Organic Compounds Containing Oxygen and Nitrogen / ऑक्सीजन एवं नाइट्रोजन युक्त कार्बनिक यौगिक, Geography as a Discipline and Geographical Thought / भूगोल: एक विषय एवं भौगोलिक चिंतन, पृथ्वी: उत्पत्ति, आंतरिक संरचना एवं विवर्तनिकी / The Earth: Origin, Interior and Tectonics, Geomorphic Processes and Landforms / भू-आकृतिक प्रक्रियाएँ एवं स्थलरूप, Atmosphere and Climate / वायुमंडल एवं जलवायु, जैवमंडल, मृदा एवं पर्यावरण / Biosphere, Soils and Environment, Natural Hazards and Disasters / प्राकृतिक संकट एवं आपदाएँ, संसाधन, कृषि, खनिज एवं ऊर्जा / Resources, Agriculture, Minerals and Energy, Industries, Services, Transport and Trade / उद्योग, सेवाएँ, परिवहन एवं व्यापार, द्रव्य एवं रसायन विज्ञान की मूल अवधारणाएँ / Matter and Basic Concepts of Chemistry, परमाणु संरचना एवं नाभिकीय रसायन / Structure of Atom and Nuclear Chemistry, States of Matter and Solutions / द्रव्य की अवस्थाएँ एवं विलयन, Redox Reactions and Electrochemistry / अपचयोपचय अभिक्रियाएँ एवं वैद्युतरसायन, Chemical Kinetics and Surface Chemistry / रासायनिक बलगतिकी एवं पृष्ठ रसायन, धातुकर्म, s-ब्लॉक एवं p-ब्लॉक तत्व / Metallurgy, s-Block and p-Block Elements, हाइड्रोकार्बन, हैलोऐल्केन एवं हैलोऐरीन / Hydrocarbons, Haloalkanes and Haloarenes, Biomolecules, Polymers and Everyday Chemistry / जैव-अणु, बहुलक एवं दैनिक जीवन में रसायन, Analytical Chemistry and Spectroscopy / विश्लेषणात्मक रसायन एवं स्पेक्ट्रमिकी, Measurement and Mathematical Methods / मापन और गणितीय विधियाँ, गति और गति के नियम / Motion and Laws of Motion, कार्य, ऊर्जा, शक्ति और घूर्णी गति / Work, Energy, Power and Rotational Motion, Gravitation / गुरुत्वाकर्षण, Mechanical Properties of Matter / पदार्थ के यांत्रिक गुण, Thermal and Statistical Physics / तापीय और सांख्यिकीय भौतिकी, Oscillations and Mechanical Waves / दोलन और यांत्रिक तरंगें, Electrostatics and Current Electricity / स्थिरवैद्युतिकी और धारा विद्युत, Magnetism, Induction and Alternating Current / चुम्बकत्व, प्रेरण और प्रत्यावर्ती धारा, Optics and Photonics / प्रकाशिकी और फोटोनिकी, Quantum Physics and Relativity / क्वांटम भौतिकी और आपेक्षिकता, Atoms, Nuclei and Astrophysics / परमाणु, नाभिक और खगोल भौतिकी, जीव जगत एवं जैविक वर्गीकरण / Living World and Biological Classification, Plant Physiology / पादप कार्यिकी, मानव कार्यिकी / Human Physiology, Molecular Basis of Inheritance / वंशागति का आणविक आधार, Biology in Human Welfare / मानव कल्याण में जीव विज्ञान, पारिस्थितिकी एवं पर्यावरण / Ecology and Environment, Family, Marriage and Kinship / परिवार, विवाह और नातेदारी, Soil Science / मृदा विज्ञान, Plant Nutrition, Manures and Fertilizers / पादप पोषण, खाद एवं उर्वरक, Fruit Science and Orchard Management / फल विज्ञान एवं बाग प्रबंधन, Floriculture, Landscaping and Protected Cultivation / पुष्प विज्ञान, भूदृश्य एवं संरक्षित खेती, Plant Breeding and Seed Technology / पादप प्रजनन एवं बीज प्रौद्योगिकी, Plant Protection / पादप संरक्षण, Anatomy and Physiology / शरीर रचना एवं शरीर क्रिया विज्ञान, Kinesiology and Biomechanics / कायनेसियोलॉजी एवं बायोमैकेनिक्स, Sports Psychology, Growth and Sociology / खेल मनोविज्ञान, वृद्धि एवं समाजशास्त्र, Sports Training and Physical Fitness / खेल प्रशिक्षण एवं शारीरिक पुष्टि, Sports Medicine, Injuries and Rehabilitation / खेल चिकित्सा, चोटें एवं पुनर्वास, Test, Measurement and Evaluation / परीक्षण, मापन एवं मूल्यांकन, Food and Nutrients / भोजन और पोषक तत्त्व, Nutrition Processes and Meal Planning / पोषण प्रक्रियाएँ और आहार नियोजन, Food Science, Processing and Food Safety / खाद्य विज्ञान, प्रसंस्करण और सुरक्षा, Public Nutrition, Health and First Aid / जन पोषण, स्वास्थ्य और प्राथमिक उपचार, Textile Science and Indian Textiles / वस्त्र विज्ञान और भारतीय वस्त्र, Extension Education and Development Communication / प्रसार शिक्षा और विकास संचार, Solid State Physics and Electronics / ठोस अवस्था भौतिकी और इलेक्ट्रॉनिकी, Main-group and Periodic Chemistry / मुख्य समूह एवं आवर्त रसायन, Biochemistry and Bioenergetics / जैवरसायन एवं जैवऊर्जिकी, Non-chordate Diversity / अरज्जुकी विविधता, Plant Morphology and Anatomy / पादप आकारिकी और शारीर, Animal Reproduction and Development / जंतुओं में जनन एवं परिवर्धन
- Paper-1 | General Awareness / सामान्य जागरूकता: State-Specific General Knowledge / राज्य विशेष सामान्य ज्ञान, Current Affairs / समसामयिकी, प्रादेशिक एवं राजनीतिक भूगोल / Regional and Political Geography, Social Problems and Welfare / सामाजिक समस्याएँ और कल्याण, Guidance and Counselling / निर्देशन एवं परामर्श, Digital India and Online Services, भारत का भौतिक पर्यावरण / India: Physical Environment, जनसंख्या, मानव विकास एवं सांस्कृतिक भूगोल / Population, Human Development and Cultural Geography, Human Settlements / मानव बस्तियाँ, संघवाद, राज्य और स्थानीय शासन / Federalism, State and Local Government, Sources and Historiography / इतिहास के स्रोत एवं इतिहास-लेखन, Prehistoric Cultures and the Harappan Civilisation / प्रागैतिहासिक संस्कृतियाँ एवं हड़प्पा सभ्यता, Harsha and Early Medieval India / हर्ष एवं पूर्व मध्यकालीन भारत, Delhi Sultanate and the Deccan Kingdoms / दिल्ली सल्तनत एवं दक्कन के राज्य, Mughal Empire and the Marathas / मुगल साम्राज्य एवं मराठा, European Arrival, British Expansion and 1857 / यूरोपीय आगमन, ब्रिटिश विस्तार एवं 1857, Modern and Contemporary World / आधुनिक एवं समकालीन विश्व, Culture, Socialisation and Social Control / संस्कृति, समाजीकरण और सामाजिक नियंत्रण, Vegetables and Specialty Crops / सब्जी एवं विशिष्ट फसलें, Animal Husbandry and Dairy Science / पशुपालन एवं दुग्ध विज्ञान, Olympic Movement, Sports Bodies and Awards / ओलंपिक आंदोलन, खेल संस्थाएँ एवं पुरस्कार, Athletics (Track and Field) / एथलेटिक्स (ट्रैक एवं फील्ड), खेल एवं क्रीड़ाएँ / Games and Sports, Sports Management and Tournaments / खेल प्रबंधन एवं प्रतियोगिताएँ, Indian Architecture, Temple Sculpture and Bronzes / भारतीय स्थापत्य, मंदिर मूर्तिकला और कांस्य, Indian Miniature Painting Schools / भारतीय लघुचित्र शैलियाँ, Folk Art and Crafts / लोक कला और हस्तशिल्प, Folk and Contemporary Dance / लोक और समकालीन नृत्य, Cultural and Language Awareness / संस्कृति और भाषा परिचय, Defence and Security Awareness / रक्षा और सुरक्षा परिचय
- Paper-2 | Fundamentals of Computer: Basics of COA, Number System, Floating Point Rep, Number Representation
- Paper - 2 | Digital Logic Systems: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits
- Paper-2 | Operating Systems: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Deadlock, Threads & Process Creation, Memory Management, Virtual Memory, Disc Scheduling, File Management, Linux OS, Distributed Systems
- Paper-2 | Database Management System: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, Relational Algebra, SQL, Relational Calculus, File Organization & Indexing, Transaction Management, Concurrency Control
- Paper-2 | Data Structures: Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing
- Paper-2 | C Programming: C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums, DMA, Macros, Scoping & File Handling
- Paper 2 | Oops, C++, Java: Language Design, OOPS with C++, Java, .Net Programming, Java Fundamentals
- Paper 2 | Python: Introduction to Python, Tokens, Variables, Data Types, I/O, Operators & Expressions, Control Flow & Looping, Collections & Strings, Functions & Modules, File Handling & Data Analysis
- Paper 2 | Emerging Trends and AI: Emerging Trends and AI, Trade, Marketing and Consumer Protection / व्यापार, विपणन एवं उपभोक्ता संरक्षण, Internet of Things, Cloud Computing, Network Access Technologies
- Paper-2 | Algorithms: Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Advanced Algorithms
- Paper 2 | Data Communication and Network Security: Introduction to CN, Data Communication, DLL: Access Control, DLL: Flow Control, DLL: Error Control, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Security, Ethical Hacking
- Paper-2 I Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
- Paper-2 | Computer Organization and Architecture: Cache Memory Organization, Input Output Organisation, Instr Formats & Modes, Control Unit Design, Register Transfer and Microoperations
- Paper-2 | Web Development: JavaScript-Basics, HTML Basics, CSS, XML
- Pedagogy / शिक्षाशास्त्र: Growth and Development / वृद्धि और विकास, शिक्षा का अर्थ, उद्देश्य एवं दर्शन / Meaning, Aims and Philosophy of Education, Cognitive Processes / संज्ञानात्मक प्रक्रियाएँ, Theories of Development / विकास के सिद्धांत, Inclusive Education / समावेशी शिक्षा, विज्ञान शिक्षणशास्त्र / Science Pedagogy, Socialisation and Gender / समाजीकरण और जेंडर, शिक्षा, समाज एवं जेंडर / Education, Society and Gender, Teaching-Learning Process and Classroom Management / शिक्षण-अधिगम प्रक्रिया एवं कक्षा प्रबंधन, Teaching Methods and Approaches / शिक्षण विधियाँ एवं उपागम, Lesson Planning / पाठ योजना, Teaching Aids and Educational Technology / शिक्षण सहायक सामग्री एवं शैक्षिक तकनीकी, Teacher: Qualities, Professional Ethics and Development / शिक्षक: गुण, व्यावसायिक नैतिकता एवं विकास, Assessment and Evaluation / आकलन एवं मूल्यांकन, Curriculum, Arts and Co-curricular Areas / पाठ्यचर्या, कला एवं सह-शैक्षिक क्षेत्र, Education of Children with Disabilities / दिव्यांग बच्चों की शिक्षा, Educational Psychology / शैक्षिक मनोविज्ञान, अभिप्रेरणा और स्वनिर्देशित अधिगम / Motivation and Self-Directed Learning, व्यक्तिगत भिन्नताएँ, क्षमताएँ और व्यक्तित्व / Individual Differences, Abilities and Personality, Mental Health and Guidance / मानसिक स्वास्थ्य और मार्गदर्शन, Teaching Methods / शिक्षण विधियाँ, Teaching Aids and Educational Technology / शिक्षण सहायक सामग्री और शैक्षिक तकनीकी, Methods of Research and Research Design / शोध विधियाँ एवं अभिकल्प, Mathematics Pedagogy / गणित शिक्षणशास्त्र, Science and Scientific Inquiry / विज्ञान एवं वैज्ञानिक जाँच, Social Science Pedagogy / सामाजिक विज्ञान शिक्षणशास्त्र, Teaching Geography / भूगोल शिक्षण, Society, Community and Social Groups / समाज, समुदाय और सामाजिक समूह, Apparel Design and Care / परिधान डिज़ाइन और देखभाल, Nature, History and Schools of Psychology / मनोविज्ञान का स्वरूप, इतिहास और सम्प्रदाय, Research Methods and Statistics / अनुसंधान विधियाँ और सांख्यिकी, Biological Bases of Behaviour / व्यवहार के जैविक आधार, Sensation, Attention and Perception / संवेदन, अवधान और प्रत्यक्षण, Thinking, Language, Intelligence and Creativity / चिंतन, भाषा, बुद्धि और सृजनात्मकता, Motivation and Emotion / अभिप्रेरणा और संवेग, Self, Personality and Stress / आत्म, व्यक्तित्व और तनाव, Psychological Disorders / मनोवैज्ञानिक विकार, Therapeutic Approaches / चिकित्सा उपागम, Social Psychology / सामाजिक मनोविज्ञान, Industrial and Organisational Psychology / औद्योगिक और संगठनात्मक मनोविज्ञान, Indian and Western Aesthetics / भारतीय और पाश्चात्य सौन्दर्यशास्त्र, Art Pedagogy / कला शिक्षण, Fundamentals of Dance / नृत्य के मूल तत्व, General Concepts of Philosophy / दर्शन के सामान्य प्रत्यय, Social and Political Philosophy / सामाजिक एवं राजनीतिक दर्शन, Microteaching and Classroom Communication / सूक्ष्म शिक्षण एवं कक्षा संप्रेषण, Educational Policies, Acts and Administration / शैक्षिक नीतियाँ, अधिनियम एवं प्रशासन, Learning and Behavioural Theories / अधिगम और व्यवहारवादी सिद्धांत, Teaching Planning and Teaching Skills / शिक्षण योजना और शिक्षण कौशल, मानव विकास / Human Development, Assessment and Evaluation / आकलन और मूल्यांकन
- Live Sessions:
- RSSB Paper 1 - Full Mock Tests:
- RSSB Paper 2 - Full Mock Tests:
- SCI Previous Year Papers:
AI summary & chapters
AI Summary
An AI-generated summary of this video lecture.
This lecture segment provides a comprehensive overview of Linear Probing within hash table implementations. The instructor details the sequential search mechanism, emphasizing that operations like insertion, search, and deletion generally achieve constant expected time complexity, provided the load factor remains strictly below one. A significant portion of the lesson is dedicated to the nuances of the deletion operation, explaining why simple removal is insufficient and how special markers are used to preserve search integrity. Finally, the lecture transitions to the disadvantages of this method, specifically focusing on the phenomenon of primary clustering and its detrimental impact on performance as the table fills up.
Chapters
0:00 – 2:00 00:00-02:00
The instructor begins by defining linear probing as a method that searches the table sequentially starting from the position given by the hash function. He draws a vertical rectangle to represent the hash table structure and writes i, i+1, i+2, and i+3 alongside it to illustrate the probing sequence. The on-screen text highlights that dictionary operations can be implemented in O(1) as long as the load factor is a constant strictly less than one. He explains that for insertion, the algorithm keeps probing until an empty slot is found, while search continues until a matching key is found or an empty slot is reached. He notes that this constant expected time holds when implemented using a random hash function.
2:00 – 5:00 02:00-05:00
The discussion moves to the Delete(k) operation, which the instructor marks as interesting in red text. He explains that if a key is simply deleted, subsequent searches for keys that collided and were placed later in the sequence may fail. To solve this, he demonstrates marking slots of deleted keys specially as deleted rather than empty. He writes O(m) next to the table to indicate worst-case time complexity. The instructor then transitions to a new slide titled Disadvantage, preparing to discuss the limitations of this collision resolution scheme. He emphasizes that insert can insert an item in a deleted slot, but search doesn't stop at a deleted slot.
5:00 – 5:32 05:00-05:32
The lecturer outlines the disadvantages, specifically underlining primary clustering on the slide. He draws a hash table with a dense cluster of filled slots to visualize how one collision causes more nearby collisions. He writes 1/10 to represent a load factor and circles the cluster, explaining that performance degrades more quickly at high load factors because basic operations take more time. The slide also notes that achieving good performance requires a higher-quality hash function than other schemes. He explains that this is a tendency for one collision to cause more nearby collisions.
The video effectively bridges the gap between theoretical complexity and practical implementation issues. It establishes that while linear probing is efficient on average, the deletion logic is non-trivial and requires special state management. The lesson concludes by identifying primary clustering as a critical flaw, demonstrating through diagrams how collisions propagate and degrade performance, thereby necessitating strict load factor controls and high-quality hash functions for optimal results.

