Unit 5 - Sorting, Searching, and Hashing

Table of Contents

1. Overview: Sorting, Searching, and Hashing
2. Sorting
3. Searching
4. Hashing

5.1. Overview - Sorting, Searching, and Hashing

In this unit we're going to take a look at some classic algorithms and data structures.

Sorting algorithms work on collections of related data items and sort them according to some criteria. Because the criteria is arbitrary and because we're focused on the sorting process itself (rather than what type of data we're sorting), our examples here will typically work on collections of integers.

We'll be sorting lists of integers.

There are lots of different strategies for sorting data. It's interesting to think about how that might happen, what systems or strategies there are for doing that kind of thing.

The topic of Searching through a collection of data is another interesting topic. There are pretty much only two commonsense ways of finding items in a collection, and which one you use depends on the way the collection is implemented, and whether or not the collection is ordered. We'll look at both of those possibilities.

Related to the question of searching is the fascinating topic of hashing.

We'll soon learn all about it!

5.2. Sorting

The process of sorting is already familiar to you. In your previous Computer Science course you learned about the Selection Sort, for example:

What does this look like?

Now let's implement a Selection Sort in Python.

#!/usr/bin/env python3
"""
selection_sort.py
Creates a list of random values and sorts them using the 
Selection Sort algorithm.
"""

import time
import random

def generate_random_numbers(length, range_of_values):
    """Generates a list of "length" integers randomly
    selected from the range 0 (inclusive) to 
    range_of_values (exclusive) and returns it to 
    the caller.
    """
    # write code here
    
    
def selection_sort(nums):
    """Takes the list "nums" and sorts it using the
    Selection Sort algorithm.
    """
    # write code here
    
    
        
def display(a_list):
    """Prints out the list "a_list" on the screen. To
    be used for debugging, or displaying the initial
    and final state of the list.
    """
    # write code here
    
    
    
def main():
    NUM_OF_VALUES = 10
    nums = generate_random_numbers(NUM_OF_VALUES, 1000)
    display(nums)
    start = time.time()
    selection_sort(nums)
    stop = time.time()
    display(nums)
    print("Sorted {0:10d} values, execution time: {1:10.5f} seconds".format(NUM_OF_VALUES, stop - start))
    
if __name__ == "__main__":
    main()

Once the sorting process is working, collect some data:

Graphically identifying the performance of the Selection Sort

Create a new version of your Selection Sort program that collects data for a range of data set sizes (length of the random number list), and then plot sort time (s) vs. size of data set (values) using a spreadsheet program.

Perform a regression on the data you've collected. Does it match the published Big-O value for the Selection Sort algorithm?

Show/hide analysis

And once you've got that figured out...

(n + 2)    +    (n-1 + 2)    +    (n-2 + 2)   +  ...  +  (2 + 2)
                            
    [n + (n-1) + (n-2) +  ...  + 2]    +     [(n-1) * 2]

[2 +  ...  + n] = 
    [sum of 1 to n] - 1 = 
    n(n+1)/2        - 1     +    (n-1) * 2 (from the second part above)

5.2.1. Insertion Sort

The insertion sort is another strategy that can be used to sort a list of values.

Once you've developed an understanding of the Insertion Sort, implement a demonstration of that algorithm.

5.3. Searching

We're always storing data on the computer, and we're always trying to retrieve that data so that we can work with it, edit it, manipulate it, and display it. There are two classical means of searching for data that we've stored in a collection.

5.3.1. Linear Search

A linear search is just what it sounds like: given a list of values (sorted or unsorted), go through the list one item at a time, starting at the beginning, and checking each value in turn until you either:

1. Find the item on the list, in which case you indicate its location, or
2. You go through the entire list and don't find the number, in which case you indicate that the search term has not been found on the list.

A linear search is not usually the most efficient means of finding an item in a list, but it's a good start for us at this point.

Let's see how to write one.

5.3.2. Binary Search

If your list of items has already been sorted according to some key—the value of the item, or the serial number of an item in inventory, or its location alphabetically—we can use a divide-and-conquer strategy to find an item in the sorted list.

The Binary Search can be tricky to implement. Challenges include identifying the middle of a list of an even number of items, and keeping track of upper- and lower-bounds of the search space. Typically you'll want to have variables to track the lower index of the part of the list you're looking at, the upper part of the list, and the calculated middle of the list. Then adjust those values as you get closer and closer to finding the location of the search value.

There are also more sophisticated concerns, like "what happens if you have a billion items to search through?" Large lists like this can tax an algorithm, and even the experts can get tripped up.

We'll keep things simple in here.

Once you think you know how a binary search works, take a few moments to see if you can write and debug a Python version of it.

5.3.3. Binary Search, recursively

The version of the Binary Search above uses variables to keep track of the lower, upper, and middle indexes in the list, and manipulates those points to narrow the range of values being examine.

It may not surprise you that the binary search can be easily implemented using recursion: the search function, which examines a list with upper and lower bounds, can be used to call itself with changes in the upper and lower bounds, all the time reducing the search space.

5.4. Hashing

Most introductory classes get a chance to touch on linear and binary searching. A third strategy for looking things up in a collection is a bit more sophisticated, and involves using a certain strategy when we first store the items in memory.

Let's take a look at hashing.

5.4.1. The Principles of Hashing

Just as a list allows us to store items for access later, a hash table allows us to store items for access later. In a list we access items according to their location in the list—their index—but in a hash table, we identify the item directly by its value.

The hash table has a series of slots for holding values. At any given time, some of those slots will be filled with values (our data), and some of them will be unfilled. We can calculate a value that represents the load factor λ = number of items stored in table / table size.

Here's an example of a small hash table meant to store some integers. The size of the hash table is m = 11, for the eleven slots. The table is currently empty.

5.4.1.1. The hash function

The hash function is the strategy that is used to store values in the table. It's a mapping, or a way of calculating where in the table a given value should be stored.

The general idea is that if we take a value and apply the hash function to it to identify a location where it can be stored, then when we try to look up that value later on, we can apply the same hash function to figure out where it's located.

On the other hand, if we try to look up something and the hash function can't find it, then we know we haven't stored it in our table.

So... what is the hash function? There are lots of different functions commonly used, but an easy one to start out with is to use the modulo operation, ie. the remainder.

h(n) = n % table_size

There are other hash functions that can be implemented. We'll look at some of those a little later.

5.4.1.2. Looking up values in a hash table

To identify whether a value is in the table—to do a lookup of that value—we can just apply the hash function to any value and look in the able to see if it exists:

# table has already been created
val = 112           # value we're looking for
m = 11              # table size
slot = val % m      # calculate location
if slot != None:
    print("We found it!")
else:
    print("Value",val,"is not in the hash table")

5.4.1.3. Hash collisions

You've probably already noticed a potential problem with our hash function. What if we also want to store the value 19 in our table. Where would that go?

h(19) = 19 % 11 = 8, but we already have another value stored there, the value 30. Both of those values have the same mod value, resulting in a hash collision.

This is normal consequence of having a hash table that is smaller than the possible range of values that can be stored in it, and the possibility of a collision requires that we have some strategy for dealing with it. This process of resolving a collision is generally called rehashing. More specifically, in this case, our rehashing is using a strategy called open addressing in which we're searching for an open slot to place our value.

There are a number of different techniques, and we'll pursue a very simple one here: if a slot is already filled, go to the next available slot in the table and try to put it there. And if that one is already filled, go one slot further and try to put it there. Keep going until you find a slot that is available and put it there.

This particular collision resolution strategy is called linear probing.

So, if slot 8 is filled, we'll look in slot 9: is that one available? It is, so we'll place our value of 19 there.

5.4.2. The Map Abstract Data Type

The Map abstract data type describes a strategy for managing values in the style of a hash table. Once we describe the methods of the Map ADT, we'll use those methods to write a HashTable class.

Up to this point, we've only looked at storing integers in our hash table, but we typically want to store more than just an integer. Often, we want to store a key-value pair: a key which we'll use to identify the piece of information, and a value that goes with that key.

Examples of key-value pairs include:

• a social security number and a name
• an email address and a name
• a friend's name and his/her birthdate

In each of these note that the key has to be a unique identifier, but the value doesn't. The social security number for a certain "John Smith" is unique, even if the name itself is shared with lots of other people. My friend's name needs to be unique in my Contacts list, even if her birthdate is shared with other people in my Contacts list.

5.4.2.1. The Python implementation of the Map Abstract Data Type

You may recognize this key-value relationship as one that matches the dict dictionary data type in Python. We discussed it here, and used dictionaries to keep track of frequency counts of letters in a document.

Python's dict class is one implementation of the Map abstract data type. Let's see what methods go along with Map objects.

5.4.2.2. The Map ADT defined.

Here's a list of the Map methods.

5.4.3. Another Explanation of the Concept of Hash Tables

Harvard University's CS 50 Computer Science class is an outstanding college-level introductory computer science class. Take a look at this 7-minute video from them that explains some of the high-level fundamentals of hashing.

Once you're done with the video, let's see if we can actually write a HashTable class that will allow us to work with data.

5.4.4. Implementing a Map with the HashTable class

Now that we know a little bit about hash tables, let's write our first attempt at a HashTable class.

#!/usr/bin/env python3
"""
hash_table.py
This program describes the HashTable class, which uses a pair of arrays
to store key-value pairs.
"""

class HashTable():
    """Describes a hash table that will store key-value pairs.
    One way to do this would be to create a single array of dictionary-style
    objects. Another strategy--simultaneously simpler and more cumbersome--
    is to maintain a pair of parallel arrays. One array--slots--keeps track
    of the keys, while a second array--data--stores the value associated with
    each key.
    
    At the beginning, the parallel arrays for a hash table of size 7 look like 
    this:
    
        slots = [ None, None, None, None, None, None, None ]
    
        data =  [ None, None, None, None, None, None, None ]
        
    Calling the .put(key, value) method will update the slots and data in 
    those arrays:
    
        .put(8, "Adam")
        
    Updated hash table (based on slot 8 % 7 = 1)
     
        slots = [ None,    8  , None, None, None, None, None ]
    
        data =  [ None, "Adam", None, None, None, None, None ]
    
    """

5.4.4.1. Additional HashTable code

Before you get too far into this, download the hash_table_tester.py file for use with your program.

Be sure to alter the import statement in that program to match the filename that you're working with.

#!/usr/bin/env python3
"""
hash_table.py
This program describes the HashTable class, which uses a pair of arrays
to store key-value pairs.
"""

class HashTable():
    """Describes a hash table that will store key-value pairs.
    One way to do this would be to create a single array of dictionary-style
    objects. Another strategy--simultaneously simpler and more cumbersome--
    is to maintain a pair of parallel arrays. One array--slots--keeps track
    of the keys, while a second array--data--stores the value associated with
    each key.
    
    At the beginning, the parallel arrays for a hash table of size 7 look like 
    this:
    
        slots = [ None, None, None, None, None, None, None ]
    
        data =  [ None, None, None, None, None, None, None ]
        
    Calling the .put(key, value) method will update the slots and data in 
    those arrays:
    
        .put(8, "Adam")
        
    Updated hash table (based on slot 8 % 7 = 1)
     
        slots = [ None,    8  , None, None, None, None, None ]
    
        data =  [ None, "Adam", None, None, None, None, None ]
    
    """
    
    
###############################

    def __init__(self, m):
        """Creates an empty hash table of the size m
        """
        self.size = m                       # remember, prime numbers are better
        self.slots = [None] * self.size     # a list of None keys
        self.data = [None] * self.size      # a list of None values

###############################

    def hash_function(self, key, size):
        """This helper method returns the value of the hash function, based on 
        the key and the size of the table.
        """
        return key % size

###############################

    def put(self, key, value):
        """Places a key-value pair in the hash table, or replaces
        the current value if the key already exists in the table.
        """
        pass
        
            
###############################

    def get(self, key):
        """Tries to find a key-value pair in the hash table, or returns
        None if no key is found.
        """
        pass
        
        
###############################

    def __repr__(self):
        """Returns a string representation of the hash table, displayed 
        as two arrays.
        """
        return "Keys:   " + str(self.slots) + "\n" + "Values: " + str(self.data)

The real challenge in writing this code is the .put() method. If you're having trouble with that, pick your way through this next version of the code and see if it makes any sense.

#!/usr/bin/env python3
"""
hash_table.py
This program describes the HashTable class, which uses a pair of arrays
to store key-value pairs.
"""

class HashTable():
    """Describes a hash table that will store key-value pairs.
    One way to do this would be to create a single array of dictionary-style
    objects. Another strategy--simultaneously simpler and more cumbersome--
    is to maintain a pair of parallel arrays. One array--slots--keeps track
    of the keys, while a second array--data--stores the value associated with
    each key.
    
    At the beginning, the parallel arrays for a hash table of size 7 look like 
    this:
    
        slots = [ None, None, None, None, None, None, None ]
    
        data =  [ None, None, None, None, None, None, None ]
        
    Calling the .put(key, value) method will update the slots and data in 
    those arrays:
    
        .put(8, "Adam")
        
    Updated hash table (based on slot 8 % 7 = 1)
     
        slots = [ None,    8  , None, None, None, None, None ]
    
        data =  [ None, "Adam", None, None, None, None, None ]
    
    """
    
    
###############################

    def __init__(self, m):
        """Creates an empty hash table of the size m
        """
        self.size = m                       # remember, prime numbers are better
        self.slots = [None] * self.size     # a list of None keys
        self.data = [None] * self.size      # a list of None values

###############################

    def hash_function(self, key, size):
        """This helper method returns the value of the hash function, based on 
        the key and the size of the table.
        """
        return key % size

###############################

    def put(self, key, value):
        """Places a key-value pair in the hash table, or replaces
        the current value if the key already exists in the table.
        """
        hashvalue = self.hashfunction(key, self.size)
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = value
        elif self.slots[hashvalue] == key:      # Check replacing value
            self.data[hashvalue] = value    
        else:           # We're occupied. Time to start linear probe!
            nextslot = (hashvalue + 1) % self.size      # get the nextslot based 
            while self.slots[nextslot] != None and \
                  self.slots[nextslot] != key:
                nextslot = (nextslot + 1) % self.size
            # We stopped. Are we replacing value or entering new value?
            if self.slots[nextslot] == key:
                self.data[nextslot] = value
            else:
                self.slots[nextslot] = key
                self.data[nextslot] = value
            
###############################

    def get(self, key):
        """Tries to find a key-value pair in the hash table, or returns
        None if no key is found.
        """
        pass
        
        
###############################

    def __repr__(self):
        """Returns a string representation of the hash table, displayed 
        as two arrays.
        """
        return "Keys:   " + str(self.slots) + "\n" + "Values: " + str(self.data)

5.4.5. Adding HashTable to your atds.py

Once you've got your HashTable class working correctly, include it with your atds.py file and upload it to the server for evaluation.