Computer Science 08

Hashing is how the 'dict' is implemented in Python. It trades off space (memory) for time (CPU utilization).  Take for example, we have a set of integers. We build the set of integers, and detect whether or not a particular integer is in the set very quickly.

We are first going to take an integer i, and hash it. A hashing function is one that converts integer i to some other integer in a range between 0 to k. We will then use this hash integer to index into a list of buckets (a bucket is actually a list).

We know that we can find the i^th element of a list in constant time, so to find an integer in a dictionary, we hash the integer, then look directly into the index to look for it. The hash function has the following issues:
1) Many-to-One - There can be an infinite number of different inputs that may hash to the same value, resulting in Collisions.
2) Collision - When two different values hash to the same bucket, we have a collision.
3) Linear Rehashing is used to take care of Collision, which keeps a list of things with the same hash value in buckets.

A good hash function has the following properties:
1) Wide Dispersal, One-to-One - This requires a large hash size
2) Avalanche Effect - A small change in input should result in a large change in hash

If we analyze the complexity of a Hash Lookup, we know that the hashing is of constant complexity, while the lookup is actually based on the number of things stored in the Bucket. If the particular item you're looking for has a great number of other things that collided with it, then it will take a longer time to find it. If all buckets are of length 1 (no collision), then a hash lookup is actually a constant complexity operation. The more buckets there are, the less chance is it for there to be a collision. This is a type of trade off between space (take more space) and time (use less time).

A practical hash table uses a large hash such that there is really low collision.

Python's dictionary implements an expanding hash system that expands accordingly to the number of collisions detected.

The reason why the keys in a 'dict' has to be immutable is because if a list is used as a key, and it mutates somewhere along the way, the hash would come out different and we would not be able to find the object it's supposed to be the key for.

Exceptions are everywhere in programming languages. What an exception is an error that is encountered during execution. Examples are:
1) IndexError - When you try to access an invalid index
2) NameError - When you try to access an invalid variable
3) TypeError - When an unexpected type is encountered

These Exceptions are also called Unhandled Exceptions. In Unhandled Exceptions, the program crashes. Sometimes we write programs that intentionally raise exceptions, and we write code to catch these exceptions and handle them. To handle these exceptions, we use the try and except blocks:

try:
    #Code that potentially can raise exception here
except:
    #Things that run when an exception is caught

Let us look at the following code:
def readVal(valType, msgRequest, msgError):
    tries=0
    while tries<4

        val = input(msgRequest)
        try:
            val=valType(val)
            return val
        except:
            print(msgError)
            tries+=1
    raise TypeError('Number of tries exceeded')

print(readVal(int,"Please enter an int:","You did not enter an int."))

We can actually catch specific exceptions raised by an exception like this:

try:
    print(readVal(int,"Please enter an int:","You did not enter an int."))
except TypeError as tE:
    print(tE)

In this case, we can see that the tE variable stores the TypeError Exception. We can directly print the tE variable to display its message. If we do not specify the Exception type then all Exceptions are caught by the statement. We can also specify multiple except statements to represent the different cases of Exceptions.

The notion of the Class is what distinguishes a modern programming language from a primitive one.

A Module is a collection of related functions. An example of a Module is math, which we import by using "import math". From there, we can then use the log function stored in the math module using math.log(). The Dot-Notation is used to Disambiguate names. For example, item1.x and item2.x are different x's.

A Class is similar to a Module in that it is a collection of functions, but it also contains data on which its functions operate on. It allows us to pass a whole group of functions and data around. This is the basis of what we call Object-Oriented Programming. An example of a Class is the list, which contains functions like append(). The data and function associated with the object is called an object's attributes. The data, function, and everything, including the class itself, is an object.

When we deal with objects, there is a Message Passing Metaphor. The basic metaphor is that when we write something like L.append(e), we are actually passing the message "append(e)" into the L object, and it is executed within its own scope. A Method, such as append(), is a Function associated with an Object. A Class is a collection of objects with identical characteristics that forms a type. Lists and Dictionaries are actually built-in classes.