Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Introduction Hash Table
A hash table is a widely used data structure that stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has a unique key associated with it. The efficiency of a hash table comes from its ability to convert these keys into indexes of an array through a process called hashing.
Key Concepts of hash table
- Hash Function: The heart of a hash table is the hash function. This function takes a key and computes an index (an integer) which determines where the data associated with that key should be stored in the table. A good hash function distributes data uniformly across the table to minimize collisions (situations where different keys hash to the same index).
- Bucket: The hash function H(key) is used to map several dictionary entries in the hash table. Each position of the hash table is called bucket.
- Collision Resolution: Since a hash function may map multiple keys to the same index, collision resolution strategies are crucial. Common methods include chaining (where each array element in the hash table stores a linked list of entries that hash to the same index) and open addressing (where you probe for the next available slot using techniques like linear probing, quadratic probing, or double hashing).
- Load Factor: The load factor of a hash table is the number of elements divided by the number of slots available in the array. It's a measure of how full the hash table is. A higher load factor increases the likelihood of collisions, leading to a decrease in performance. This often necessitates resizing the hash table.
- Dynamic Resizing: To maintain efficient operations, hash tables may need to be resized as elements are added or removed. This involves creating a new, larger (or smaller) table, and rehashing all the existing elements into it.
Operations
- Insertion: Add a new key-value pair to the table.
- Deletion: Remove a key-value pair from the table.
- Search: Retrieve the value associated with a given key.
Advantages of hash table
- Efficient Data Retrieval: Offers near-constant time complexity for insertion, deletion, and search operations in the average case.
- Direct Access: Data can be directly indexed and is not dependent on the number of elements in the table.
Disadvantages of hash table:
- Collision Management: Requires additional structures or algorithms to handle collisions effectively.
- Hash Function Design: Creating an effective hash function can be challenging for certain types of keys.
- Memory Overhead: Some implementations may consume more memory, especially to handle collisions and resizing.
Next Topic :Hash functions