Hash Table Operations

Study Notes

To insert an object:
- Compute its hash code
- Check if it exists in the appropriate list
- If not, insert at the front of the list
Disadvantages of using linked lists:
- Slows down the algorithm
- Requires implementing another data structure
Open Addressing techniques:
- Linear Probing: sequentially search the table until an empty location is found
- Quadratic Probing: uses a collision resolution technique to avoid primary clustering
- Double Hashing: uses a second hash function when the result of the hash function results in a collision

When a collision occurs, sequentially search the table until an empty location is found
Example: suppose the hash function hashes the key 343-567 (SEU Dammam Branch) into index #4 which is already occupied by the key 343-567 (SEU Medina Branch)
Solution: sequentially search for an empty location (e.g., index #5 is occupied, so move to index #6)

Strategies for selecting the pivot:
- First element
- Last element
- Arbitrary
- Median of three values
Selecting the first value as a pivot is acceptable if the input is random
Selecting the pivot randomly is a safe strategy
The best strategy of selecting a pivot would be the median of the array items
Problems:
- Hard to calculate
- Slows down the quicksort
Solution: calculate the median of three items (first, last, and middle elements)

A heap is a binary tree that fulfills two conditions:
- It is completely filled, with the possible exceptions of the last level
- The tree fulfills the heap property (min-heap or max-heap)
Using min-heap to sort a set of elements yields decreasing sorted order
Using max-heap to sort a set of elements yields increasing sorted order
Steps to store a heap into an array:
1. Arrays start at index 0, but we start at index 1 for binary heaps
2. Compute the indices of item's parent, left child, and right child

Step 4: continue to merge parts until merging all parts into one sorted list
Example: merging two sorted arrays X{8, 12, 14, 17} and Y{9, 16, 19, 20} into array Z{}
Algorithm: mergesort(data[], firstItem, lastItem)
- If firstItem < lastItem, then
  - middleItem = (firstItem + lastItem) / 2
  - mergesort(data[], firstItem, middleItem)
  - mergesort(data[], middleItem +1, lastItem)
  - merge(data[], firstItem, lastItem)

Quicksort is a fast sorting algorithm in practice
Average running time for quicksort is O(N log N)
Worst-case running time for quicksort is O(N2)
Quicksort orders values by partitioning the list around one element, then sorting each partition
Partitioning strategy:
- Step 1: Swap the pivot with the last item
- Step 2: Let i pointing to the first item and j pointing to next-to-last item
- Step 3: While i is to the left of j, move i right, skip over elements that are smaller than the pivot
- Step 4: When i and j have stopped, i is pointing at a large element and j is pointing at a small element
- Step 5: Repeat steps 3 and 4 until i and j crossed
- Step 6: When i and j crossed, swap the pivot element with the element pointed to by i