Hash Table Operations

Hash Table and Hash Function

• 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

Linear Probing

• 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)

Quicksort

• 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)

Heapsort

• 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

Mergesort

• 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 (Partitioning Strategy)

• 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