z
Hash Tables and Advanced Sorting
z Introduction
Hash Table
- Hash tables are data structures that store key-value
pairs. In Python, dictionaries are implemented using hash
tables. They allow for efficient lookup, insertion, and deletion of
elements based on their keys.
z
Basic operations of a hash table
search operation
- is used to locate the element within a hash table.
insert operation
- is used to add elements into the hash table.
delete operation
- removes elements from the hash table.
z
To create a Hash Table
Hashing Separate Chaining
z
To create a Hash Table
Hash Function
z
Introduction
Advanced Sorting
A Sorting Algorithm is used to rearrange a given array or list of
elements according to a comparison operator on the elements.
Advanced sorting in Python involves using more complex algorithms
like bubble sort, insertion sort, selection sort, merge sort, quicksort,
or heap sort. These algorithms offer better performance for sorting
large datasets compared to simpler methods like bubble sort or
insertion sort. Python's built-in sorting functions like sorted() and
sort() use efficient sorting algorithms under the hood to quickly sort
lists and arrays.
Sortingz Techniques
1. Bubble Sort - is a sorting algorithm that uses comparison methods to sort an array. The
algorithm compares pairs of elements in an array and swaps them if the left pair(position) is
greater than the right pair(position+1). This process is repeated until the entire array is sorted.
Sample code for Bubble Sorting
Sortingz Techniques
2. Insertion Sort - insert one or more elements into the array. We can insert an element at
any position in the array like beginning, end or at any given indexed position. First of all, we
have to check that whether there is a room(space) available or not.
Sample code for Insertion Sorting
Sortingz Techniques
3. Selection Sort - Selection sort works by taking the smallest element in an unsorted array
and bringing it to the front. You'll go through each item (from left to right) until you find the
smallest one. The first item in the array is now sorted, while the rest of the array is unsorted.
Sample code for Selection Sorting
Sorting Techniques
4. Quick Sort - is a recursive algorithm for sorting an array of elements. It works by
selecting a pivot element and partitioning the array around the pivot, such that all elements less
than the pivot are moved to its left and all elements greater than the pivot are moved to its right.
Sample code for Quick Sorting
Sorting Techniques
5. Merge Sort - Merge sort is one of the most efficient sorting algorithms. It is based on the
divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists
until each has only one item, then merges those sublists into a sorted list.
Sample code for Merge Sorting
Output
Separate Chaining in Hash Tables with Python
(Efficient Collision Handling)
Introduction to Hashing
• Hash tables store key-value pairs.
• Hash function maps keys to table indices.
Collisions occur when keys map to the same index.
What is Separate Chaining?
• Separate Chaining is a collision resolution technique used in hash tables. When multiple keys
generate the same hash value (resulting in a collision).
• Separate Chaining stores these keys in a linked list associated with that hash index.
• Essentially, each index in the hash table contains a chain of elements that share the same hash
value.
Insertion Method
• The `insert` method hashes the key to find the appropriate index. If the index is empty, it
creates a new node. If not, it inserts the new node at the head of the existing list.
• To search for a key, we traverse the linked list at the hashed index.
Deletion
• For deletion, we find the node and remove it from the list, maintaining the chain’s
integrity.
Advantages of Separate Chaining:
Simple to implement.
Hash table never fills up, we can always add more elements to the chain.
Less sensitive to the hash function or load factors.
It is mostly used when it is unknown how many and how frequently keys may be inserted
or deleted.
Disadvantages:
The cache performance of chaining is not good as keys are stored using a linked list.
Open addressing provides better cache performance as everything is stored in the same
table.
Wastage of Space (Some Parts of the hash table are never used) .
If the chain becomes long, then search time can become O(n) in the worst case.
Conclusion (Separate Chaining)
Collision resolution by linking entries at the same hash index.
Fast operations due to direct index access and linked lists.
Essential for maintaining hash table performance during collisions
Ensures efficient data management.
