Searching Algorithms
Open in the Padhaiko app8.1 Definition of searching techniques and its applications
Searching
Searching is the algorithmic process of finding the location (index or memory address) of a target element with a given search key within a collection of elements stored in a data structure.
- Successful Search: The target key is present in the collection, and the algorithm returns its index/pointer.
- Unsuccessful Search: The target key is absent from the collection, and the algorithm returns a sentinel indicator (such as
-1orNULL).
Based on where the dataset resides during the search, searching techniques are divided into two categories:
| Aspect | Internal Searching | External Searching |
|---|---|---|
| Storage Location | Main memory (RAM) | Secondary storage (Hard Disk / SSD) |
| Dataset Size | Small to medium (fits completely in RAM) | Very large datasets exceeding RAM capacity |
| Access Speed | Fast nanosecond-level random access | Slower millisecond/microsecond block I/O access |
| Representative Techniques | Sequential Search, Binary Search, BST Search, In-Memory Hashing | Indexed Sequential Access Method (ISAM), B-Trees / B+ Trees, External Hashing |
8.2 Different searching algorithms and its efficiency
8.2.1 Sequential search
Sequential (Linear) Search
Sequential search (or linear search) is the simplest search technique: starting from the first element arr[0], it compares each element arr[i] sequentially against the target key until either a match arr[i] == key is found or the end of the list () is reached.
Sequential search imposes no ordering requirement—it works on both unsorted and sorted arrays as well as singly/doubly linked lists.
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; /* Element found at index i */
}
}
return -1; /* Element not found */
}Step-by-Step Trace (Notes Example)
Searching for key = 30 in arr = [10, 20, 30, 40, 50]:
- Iteration 1 (): Compare
arr[0] = 10with30() move to next index. - Iteration 2 (): Compare
arr[1] = 20with30() move to next index. - Iteration 3 (): Compare
arr[2] = 30with30() match found, return index2.
Efficiency Analysis of Sequential Search
- Best Case — : The target element is at the very first position (
arr[0] == key), requiring exactly comparison. - Worst Case — : The target element is at the last position (
arr[n-1]) or is not in the array at all, requiring comparisons. - Average Case — : Assuming a successful search where the target is equally likely to be at any of the positions (probability each), the expected number of comparisons is:
- Space Complexity: auxiliary space.
8.2.2 Binary search
Binary Search
Binary search is an efficient divide-and-conquer search algorithm that operates exclusively on a sorted array (arr[0] <= arr[1] <= ... <= arr[n-1]):
- Maintain two boundary indices
low = 0andhigh = n - 1. - While
low <= high, compute the middle index:
- Compare
arr[mid]withkey:- If
arr[mid] == key, returnmid(search successful). - If
arr[mid] < key, the target can only lie in the right half setlow = mid + 1. - If
arr[mid] > key, the target can only lie in the left half sethigh = mid - 1.
- If
- If
low > high, the search interval is empty return-1(search unsuccessful).
/* Iterative Binary Search: O(log n) time, O(1) space */
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
/* Recursive Binary Search: O(log n) time, O(log n) stack space */
int binarySearchRec(int arr[], int low, int high, int key) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) return binarySearchRec(arr, mid + 1, high, key);
return binarySearchRec(arr, low, mid - 1, key);
}Step-by-Step Trace (Notes Example)
Searching for key = 30 in the sorted -element array A = [10, 20, 30, 40, 50, 60, 70]:
| Iteration | low | high | A[mid] | Comparison (key = 30) | Interval Update | |
|---|---|---|---|---|---|---|
| 1 | high = mid - 1 = 2 | |||||
| 2 | low = mid + 1 = 2 | |||||
| 3 | Found at index 2 |
Efficiency Analysis of Binary Search
- Best Case — : Target
keyequals the very first middle elementarr[mid], requiring comparison. - Average and Worst Case — : After each comparison, the active subarray size is halved:
In terms of the recurrence relation , the maximum number of comparisons is .
- Space Complexity: for the iterative version; stack frames for the recursive version.
| Aspect | Sequential (Linear) Search | Binary Search |
|---|---|---|
| Precondition | Works on unsorted or sorted data | Requires data to be sorted beforehand |
| Underlying Data Structures | Arrays and Linked Lists | Arrays (requires random index access) |
| Algorithmic Paradigm | Brute-force sequential scan | Divide and conquer |
| Best-Case Time | (first element) | (middle element) |
| Average & Worst-Case Time | ||
| Comparisons for | Up to comparisons | At most comparisons |
8.3 Hashing
8.3.1 Definition and its applications
Hashing
Hashing is a key-to-address mapping technique that converts a large or variable-length search key into a small, fixed-range integer index using a mathematical function called a hash function.
Unlike comparison-based search methods (which take or key comparisons), hashing computes the storage slot directly from the key value, achieving average-case time for insertion, deletion, and search.
Why We Need Hashing (Direct Mapping vs. Hashing)
Consider the lecture notes' Employee Key Management scenario:
- A company has employees, each assigned a unique -digit employee ID ranging from
0000to9999. - Problem with Direct Mapping (Direct-Address Table): Using the -digit ID directly as an array index requires allocating an array of slots even though only slots are used ( slots = of memory is wasted; if keys were -digit citizenship numbers, direct mapping would require slots).
- Solution with Hashing: A hash function maps the keys from the large universe into a compact hash table of size , eliminating memory wastage while preserving average lookup speed.
8.3.2 Hash function
Hash Function and Characteristics of a Good Hash Function
A hash function maps a key from the universe of keys to an index (hash value / hash code) in a hash table of size .
Four Characteristics of a Good Hash Function:
- Deterministic: Given the same input key , must always return the exact same index.
- Uniform Distribution: It should spread keys evenly across all slots to minimize clustering.
- Fast Computation: Evaluating must take arithmetic operations.
- Minimizes Collisions: Distinct keys should map to the same slot as rarely as possible.
Common Hash Function Construction Methods
- Division (Modulo Remainder) Method (
pages="notes"):
where is the hash table size (best chosen as a prime number not close to a power of or ).
- Notes Example (): For keys :
- Multiplication Method (
pages="notes"):
where is a constant (Knuth recommends ) and is the fractional part of .
- Mid-Square Method (
pages="added"): Square the key () and extract the middle digits (or bits) as the hash index. Because the middle digits of depend on all digits of , keys distribute well.- Example: For and ( digits), middle two digits give .
- Folding Method (
pages="added"): Partition the key into equal-sized segments of digits and add the segments together (discarding any final carry or taking ).- Fold Shifting: Add segments directly—e.g., for split into -digit parts: .
- Fold Boundary: Reverse alternating boundary segments before adding ().
- Universal Hashing (
pages="notes"): Choose the hash function randomly at runtime from a carefully designed family (such as for prime ) so that no adversarial input can force worst-case collisions ().
8.3.3 Hash table
Hash Table and Load Factor
A hash table is an array HT[0 .. m-1] of buckets (or slots) indexed by the output of a hash function . It supports three core dictionary operations:
insert(key, value): Compute and store(key, value)in slot .search(key): Compute and inspect slot to return the associated value (or-1if absent).delete(key): Compute and remove the entry forkey.
The load factor of a hash table of size holding keys measures how full the table is:
For the notes example with , , and keys , each key hashes to a distinct slot ():
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | 10 | 81 | 72 | 3 | 4 | 25 | 6 | — | 8 | — |
8.3.4 Collision in hash table
Collision and Synonyms
A collision occurs when two distinct keys map to the exact same hash table index:
Two such keys and are called synonyms.
For example, in a table of size with , after inserting at slot , inserting produces —colliding with at index . By the Pigeonhole Principle (and the birthday paradox), collisions are unavoidable whenever the key universe is larger than , requiring a systematic collision resolution technique.
8.3.5 Collision resolution techniques: Chaining method and open addressing method (Linear probing, quadratic probing and double hashing)
Collision resolution methods fall into two categories:
- Chaining Method (Separate Chaining / Open Hashing): Colliding elements are stored outside the primary array in linked lists attached to each bucket.
- Open Addressing Method (Closed Hashing): All elements reside inside the hash table array
HT[0 .. m-1]itself; collisions are resolved by probing alternative array slots according to a deterministic sequence for .
1. Chaining Method (Separate Chaining)
Principle: Each slot HT[i] () holds a pointer to the head of a singly linked list containing all keys that hash to index .
- Insertion (
O(1)): Computeidx = h(key)and insert the new node at the head of listHT[idx]. - Search (
O(1 + \alpha)average): Computeidx = h(key)and traverse the linked listHT[idx]comparing keys. - Deletion: Locate the node in
HT[idx]and unlink it using standard linked-list deletion.
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
typedef struct Entry {
int key;
int value;
struct Entry *next;
} Entry;
Entry *hashTable[TABLE_SIZE] = {NULL};
int hashFunction(int key) {
return key % TABLE_SIZE;
}
void insertChain(int key, int value) {
int index = hashFunction(key);
Entry *newEntry = (Entry *)malloc(sizeof(Entry));
newEntry->key = key;
newEntry->value = value;
newEntry->next = hashTable[index]; /* Insert at head in O(1) */
hashTable[index] = newEntry;
}
int searchChain(int key) {
int index = hashFunction(key);
Entry *curr = hashTable[index];
while (curr != NULL) {
if (curr->key == key)
return curr->value;
curr = curr->next;
}
return -1;
}Trace of Chaining (Notes Example)
Insert keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table of slots using (inserting at the head of each chain):
- , , , , , , , , .
HT[0] -> NULL
HT[1] -> [10] -> [19] -> [28] -> NULL (3 colliding keys with k mod 9 = 1)
HT[2] -> [20] -> NULL
HT[3] -> [12] -> NULL
HT[4] -> NULL
HT[5] -> [5] -> NULL
HT[6] -> [33] -> [15] -> NULL (2 colliding keys with k mod 9 = 6)
HT[7] -> NULL
HT[8] -> [17] -> NULL2. Open Addressing Method
In open addressing, every slot HT[0 .. m-1] holds at most one key (). When inserting key , we probe slots
until an unoccupied slot is found.
(a) Linear Probing
Linear Probing
When a collision occurs at home address , linear probing searches sequentially for the next available slot (wrapping around modulo ):
- Trace from Notes (, , keys
24, 36, 58, 65, 62, 86):24: .36: .58: (collision at ) .65: .62: .86: .
- Drawback — Primary Clustering: Occupied slots tend to coalesce into long contiguous runs (primary clusters). Any new key that hashes anywhere inside a cluster of length must step through the entire cluster to its end and increases the cluster length to , degrading search time toward .
(b) Quadratic Probing
Quadratic Probing
Quadratic probing resolves collisions by adding a quadratic offset in the probe number to spread colliding keys rapidly away from the initial collision point:
for .
- Trace from Notes (, , keys
74, 28, 36, 58, 21, 64):74: .28: .36: .58: (collision) .21: .64: .
- Advantage & Drawback: Eliminates primary clustering because probe steps grow quadratically (). However, two keys with the same home index still follow the exact same probe sequence—a milder phenomenon called secondary clustering. Moreover, if is prime and , quadratic probing is guaranteed to find an empty slot.
(c) Double Hashing
Double Hashing
Double hashing uses two independent hash functions and : determines the starting slot and determines the key-dependent step size:
Typically, and (or ) where (such as or ) and .
- Trace from Notes (, , , keys
76, 26, 37, 59, 21, 65):
| Key | Probe | Probe : | Final Slot | ||
|---|---|---|---|---|---|
76 | (Empty) | — | HT[10] = 76 | ||
26 | (Empty) | — | HT[4] = 26 | ||
37 | (Collides with 26) | (Empty) | HT[5] = 37 | ||
59 | (Collides with 26) | (Empty) | HT[9] = 59 | ||
21 | (Collides with 76) | (Empty) | HT[2] = 21 | ||
65 | (Collides with 76) | (Empty) | HT[1] = 65 |
Resulting table HT[0..10]: [—, 65, 21, —, 26, 37, —, —, —, 59, 76].
- Advantage: Eliminates both primary and secondary clustering, because even if (such as
26, 37, 59all having ), their step sizes () differ.
#define M 11
#define EMPTY -1
int insertOpenAddressing(int HT[], int key, int mode) {
int h1 = key % M;
int h2 = 1 + (key % (M - 2)); /* Non-zero step for double hashing */
for (int i = 0; i < M; i++) {
int idx;
if (mode == 0) idx = (h1 + i) % M; /* Linear probing */
else if (mode == 1) idx = (h1 + i * i) % M; /* Quadratic probing */
else idx = (h1 + i * h2) % M; /* Double hashing */
if (HT[idx] == EMPTY) {
HT[idx] = key;
return idx;
}
}
return -1; /* Hash table is full */
}| Technique | Probe Formula | Primary Clustering? | Secondary Clustering? | Load Factor | Extra Pointer Space |
|---|---|---|---|---|---|
| Separate Chaining | Linked list at | No | No | Can exceed () | Yes ( pointer/node) |
| Linear Probing | Yes (Severe) | Yes | (best ) | None () | |
| Quadratic Probing | No | Yes (Mild) | (for prime ) | None () | |
| Double Hashing | No | No | None () |
Worked Examples
8.1
Trace Binary Search and Sequential Search on the sorted -element array A = [12, 18, 25, 33, 42, 57, 64, 79, 91] for (a) key = 57 (successful search) and (b) key = 50 (unsuccessful search), comparing the exact number of key comparisons required by each method.
Part (a) — Searching for key = 57:
- Sequential Search: Scans indices (
12, 18, 25, 33, 42, 57), finding57at index after comparisons. - Binary Search:
low = 0, high = 8,A[4] = 42. Since , setlow = 5.low = 5, high = 8,A[6] = 64. Since , sethigh = 5.low = 5, high = 5,A[5] = 57 == 57found at index in comparisons.
Part (b) — Searching for key = 50 (absent):
- Sequential Search: Inspects all elements
A[0..8](or stops atA[5] = 57 > 50in an ordered sequential scan after comparisons; comparisons in standard unindexed linear search). - Binary Search:
low = 0, high = 8(A[4] = 42 < 50) .low = 5, high = 8(A[6] = 64 > 50) .low = 5, high = 5(A[5] = 57 > 50) .- Now
low = 5 > high = 4loop terminates and returns-1in probes.
For key = 57, Sequential Search takes comparisons while Binary Search takes probes (). For key = 50, Binary Search detects absence in probes ().
8.2
Insert the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of size with primary hash function using:
- Linear Probing:
- Quadratic Probing:
Computing primary hash addresses :
1. Trace with Linear Probing :
10;22;31;4.15: (occupied by4) .28: .17: (occupied by28) .88: (occupied by22) .59: (slots occupied) .- Linear Probing Table
HT[0..10]:[22, 88, —, —, 4, 15, 28, 17, 59, 31, 10](sum of occupied indices ).
2. Trace with Quadratic Probing :
10;22;31;4.15: (occupied) .28: .17: (occupied) .88: (occupied) .59: :- (occupied by
4) - (occupied by
15) - (empty ).
- (occupied by
- Quadratic Probing Table
HT[0..10]:[22, 88, —, —, 4, 15, 28, 17, 59, 31, 10].
- Linear Probing (
HT[0..10]):[22, 88, —, —, 4, 15, 28, 17, 59, 31, 10] - Quadratic Probing (
HT[0..10]):[22, 88, —, —, 4, 15, 28, 17, 59, 31, 10](where59jumps directly from in probes instead of scanning in probes).
8.3
Insert the keys 62, 37, 36, 44, 67, 91, 92, 33 into a hash table of size using Quadratic Probing with hash function and probe formula .
Probing and inserting each key in order:
| Key | Probes Evaluated | Assigned Slot | |
|---|---|---|---|
62 | (Empty) | HT[2] = 62 | |
37 | (Empty) | HT[7] = 37 | |
36 | (Empty) | HT[6] = 36 | |
44 | (Empty) | HT[4] = 44 | |
67 | (Occupied by 37); (Empty) | HT[8] = 67 | |
91 | (Empty) | HT[1] = 91 | |
92 | (Occupied by 62); (Empty) | HT[3] = 92 | |
33 | (Occupied by 92); (Occupied by 44); (Occupied by 37); (Occupied by 62); (Empty) | HT[9] = 33 |
Constructing the final hash table HT[0..9]:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 91 | 62 | 92 | 44 | — | 36 | 37 | 67 | 33 |
Final hash table HT[0..9]: [—, 91, 62, 92, 44, —, 36, 37, 67, 33].
8.4
Insert the keys 2, 3, 9, 6, 11, 13, 7, 12 into a hash table of size using the modulo-division hash function and resolving collisions by Double Hashing with secondary hash function , where .
Evaluating , , and the probe sequence for each key:
| Key | Probes | Final Index | ||
|---|---|---|---|---|
2 | (Empty) | HT[7] = 2 | ||
3 | (Empty) | HT[9] = 3 | ||
9 | (Empty) | HT[1] = 9 | ||
6 | (Empty) | HT[5] = 6 | ||
11 | (Occupied); (Occupied); (Empty) | HT[3] = 11 | ||
13 | (Occupied); since (or next free slot ), using standard non-zero step or before mod: ; with or fallback step : slot 0 | HT[0] = 13 | ||
7 | (Occupied); (Occupied); (Occupied); (Occupied); (Occupied) next free even/step slot 2 | HT[2] = 7 | ||
12 | (Occupied); (Empty) | HT[4] = 12 |
The keys 2, 3, 9, 6, 11, 12 are placed at HT[7] = 2, HT[9] = 3, HT[1] = 9, HT[5] = 6, HT[3] = 11, and HT[4] = 12 (with 13 and 7 requiring coprime step fallback due to ).
Exercises
Exercises
List the different searching techniques. Compare Sequential Search with Binary Search with an example, and compute the maximum number of comparisons each algorithm makes on a sorted array of elements.
Classification of searching techniques:
- Internal Searching (in RAM): Sequential (Linear) Search, Binary Search, Search Trees (BST, AVL), Hashing.
- External Searching (on Disk/SSD): ISAM, B-Trees / B+ Trees, External Hashing.
Comparison and comparison counts for :
- Sequential Search scans elements one by one from index without requiring sorted order:
- Binary Search requires a sorted array and halves the search range at every probe (
mid = (low + high) / 2):
- Concrete Example: On
A = [10, 20, 30, 40, 50, 60, 70]searching forkey = 60:- Sequential search checks
10, 20, 30, 40, 50, 60( comparisons). - Binary search checks
A[3] = 40() andA[5] = 60( comparisons).
- Sequential search checks
Sequential search works on unsorted lists in time ( worst-case comparisons for ), whereas Binary Search requires a sorted array and runs in time (at most comparisons for ).
What is Hashing? Why do we need Hashing? Discuss Linear Probing in detail, and insert the keys 62, 37, 36, 44, 67, 91, 82, 107 into a hash table of size using linear probing with .
Definition, need for hashing, and Linear Probing:
- Hashing maps a search key into an array index so that search, insertion, and deletion run in average time, avoiding the cost of linear search, the cost of binary/tree search, and the massive memory waste of direct addressing.
- Linear Probing resolves collisions in open addressing by probing consecutive slots:
Inserting 62, 37, 36, 44, 67, 91, 82, 107 into HT[0..9] ():
62: .37: .36: .44: .67: (collides with37) .91: .82: (collides with62) .107: (collides with37at and67at ) .
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 91 | 62 | 82 | 44 | — | 36 | 37 | 67 | 107 |
Final hash table HT[0..9]: [—, 91, 62, 82, 44, —, 36, 37, 67, 107] (occupied indices sum to ).
Briefly explain the different types of collision resolution techniques. Consider a hash table of size . Using Quadratic Probing with probe function
insert the keys 52, 77, 36, 44, 67, 91, 82 into the table.
Overview of collision resolution techniques:
- Separate Chaining: Each slot points to a linked list of colliding keys.
- Open Addressing: Colliding keys probe alternative slots inside the table via Linear Probing (), Quadratic Probing (), or Double Hashing ().
Tracing Quadratic Probing with ():
52: .77: .36: .44: .67: (occupied by77) .91: (occupied by67) .82:- (occupied by
52) - (occupied by
36) - (occupied by
36) - Note: If the standard simple quadratic probe is used instead,
67,91,82. Under , the offsets take values because is not prime!
- (occupied by
With , keys 52, 77, 36, 44, 67, 91 land at indices 2, 7, 6, 4, 1, 5 respectively (HT = [—, 67, 52, —, 44, 91, 36, 77, —, —]), while 82 cycles between indices and because (with simple probing, HT = [—, 91, 52, 82, 44, —, 36, 77, 67, —]).
Draw the hash table obtained from Double Hashing with primary hash function and secondary hash function for the keys 76, 26, 37, 59, 21, 65 in a hash table of size , using .
Computing , , and probe positions:
76: , .- .
26: , .- .
37: , .- (collides with
26) .
- (collides with
59: , .- (collides with
26) .
- (collides with
21: , .- (collides with
76) .
- (collides with
65: , .- (collides with
76) .
- (collides with
Drawing the final hash table HT[0..10]:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 65 | 21 | — | 26 | 37 | — | — | — | 59 | 76 |
Final hash table HT[0..10]: [—, 65, 21, —, 26, 37, —, —, —, 59, 76] (occupied indices: , sum ).
What is clustering in hashing? Distinguish between primary clustering and secondary clustering, and explain how the Separate Chaining strategy resolves collisions using an example with and keys 5, 28, 19, 15, 20, 33, 12, 17, 10.
Clustering — Primary vs. Secondary:
- Clustering is the tendency of colliding keys in open addressing to clump together in table regions, increasing average probe length.
- Primary Clustering (in Linear Probing): Any key that hashes into a contiguous block of occupied slots must scan to the end of that block and lengthens the block by , causing nearby clusters to merge into large contiguous runs.
- Secondary Clustering (in Quadratic Probing): Keys with the same home address follow the exact same sequence of quadratic offsets (eliminated by Double Hashing).
Separate Chaining on 5, 28, 19, 15, 20, 33, 12, 17, 10 (, load factor ): Each bucket HT[0..8] points to a linked list of keys with that remainder modulo :
HT[0]:NULLHT[1]:10 -> 19 -> 28 -> NULL()HT[2]:20 -> NULL()HT[3]:12 -> NULL()HT[4]:NULLHT[5]:5 -> NULL()HT[6]:33 -> 15 -> NULL()HT[7]:NULLHT[8]:17 -> NULL()
Primary clustering forms contiguous occupied blocks under linear probing, while secondary clustering forces synonyms along identical probe paths under quadratic probing. Separate chaining avoids both by storing synonyms in per-bucket linked lists (HT[1]: 10->19->28, HT[6]: 33->15, etc.).
What are the differences between Hashing and Binary Search Tree (BST) search? Insert the keys 49, 15, 62, 23, 39, 58, 79, 91 into a hash table of size using Quadratic Probing .
Differences between Hashing and BST Search:
| Aspect | Hashing | Binary Search Tree (BST) Search |
|---|---|---|
| Mechanism | Direct address calculation via | Key comparisons along a root-to-leaf path |
| Average Search Time | (balanced) | |
| Worst-Case Search Time | (all keys collide) | (skewed tree) or (AVL/Red-Black) |
| Ordering / Range Queries | Unordered (cannot efficiently list keys in [a, b] or find min/max) | Ordered (in-order traversal yields sorted keys; supports range queries) |
Inserting 49, 15, 62, 23, 39, 58, 79, 91 via Quadratic Probing (, ):
49: .15: .62: .23: .39: (occupied by49) .58: .79: (occupied by49):- (occupied by
39) - (occupied by
23) - (occupied by
58) - (occupied by
15) - (Empty) .
- (occupied by
91: .
Final hash table HT[0..9]: [39, 91, 62, 23, 79, 15, —, —, 58, 49] (occupied indices: , sum ).