Hashtables

Agenda

• Discussion: pros/cons of array-backed and linked structures
• Python's other built-in DS: the dict
• A naive lookup DS
• Direct lookups via Hashing
• Hashtables
  • Collisions and the "Birthday problem"
• Runtime analysis & Discussion

# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

Discussion: pros/cons of array-backed and linked structures

Between the array-backed and linked list we have:

1. $O(1)$ indexing (array-backed)
2. $O(1)$ appending (array-backed & linked)
3. $O(1)$ insertion/deletion without indexing (linked)
4. $O(\log N)$ binary search, when sorted (array-backed)

Python's other built-in DS: the dict

import timeit

def lin_search(lst, x):
    for i in range(len(lst)):
        if lst[i] == x:
            return i
    raise ValueError(x)
    
def bin_search(lst, x):
    # assume that lst is sorted!!!
    low = 0
    hi  = len(lst)
    mid = (low + hi) // 2
    while lst[mid] != x and low <= hi:
        if lst[mid] < x:
            low = mid + 1
        else:
            hi  = mid - 1
        mid = (low + hi) // 2
    if lst[mid] == x:
        return mid
    else:
        raise ValueError(x)

def time_lin_search(size):
    return timeit.timeit('lin_search(lst, random.randrange({}))'.format(size), # interpolate size into randrange
                         'import random ; from __main__ import lin_search ;'
                         'lst = [x for x in range({})]'.format(size), # interpolate size into list range
                         number=100)

def time_bin_search(size):
    return timeit.timeit('bin_search(lst, random.randrange({}))'.format(size), # interpolate size into randrange
                         'import random ; from __main__ import bin_search ;'
                         'lst = [x for x in range({})]'.format(size), # interpolate size into list range
                         number=100)

def time_dict(size):
    return timeit.timeit('dct[random.randrange({})]'.format(size), 
                         'import random ; '
                         'dct = {{x: x for x in range({})}}'.format(size),
                         number=100)

lin_search_timings = [time_lin_search(n)
                      for n in range(10, 10000, 100)]

bin_search_timings = [time_bin_search(n)
                      for n in range(10, 10000, 100)]

dict_timings = [time_dict(n)
                for n in range(10, 10000, 100)]

%matplotlib inline
import matplotlib.pyplot as plt
#plt.plot(lin_search_timings, 'ro')
plt.plot(bin_search_timings, 'gs')
plt.plot(dict_timings, 'b^')
plt.show()

[<matplotlib.lines.Line2D at 0x17861d39610>]

[<matplotlib.lines.Line2D at 0x17861d39b20>]

## A naive lookup DS

class LookupDS:
    def __init__(self):
        self.data = []
        # python list, basically an arry
        # store [key, values]  two element lists, in each position of self.data
    
    def __setitem__(self, key, value):   #l["spiderman"]='matt'
        for i in range(len(self.data)):
            if self.data[i][0]==key:
                self.data[i][1]=value
                break
        else:  # if key not found then append
            self.data.append([key,value])
    
    def __getitem__(self, key):
        for i in range(len(self.data)):
            if self.data[i][0]==key:
                return self.data[i][1]
        else:  # if key not found then exception
            raise KeyError()
    
    def __contains__(self, key):
        for i in range(len(self.data)):
            if self.data[i][0]==key:
                return True
        else:  # if key not found then false
            return False

l = LookupDS()
l['batman'] = 'bruce wayne'
l['superman'] = 'clark kent'
l['spiderman'] = 'peter parker'

l['spiderman']
l['batman'] ="matt"
l['batman']

'peter parker'

'matt'

"batman" in l
"pyhtonguy" in l

True

False

Direct lookups via Hashing

Hashes (a.k.a. hash codes or hash values) are simply numerical values computed for objects.

hash('hello')

957129065593704848

hash('batman')

-5023233161789592975

hash('batmen')

3065434418422581811

[hash(s) for s in ['different', 'objects', 'have', 'very', 'different', 'hashes']]

[-677213448131972782,
 3312122274176133112,
 -3158262903479520711,
 5641915831706961672,
 -677213448131972782,
 6710270634949560770]

[i%100 for i in range(10, 1000, 1)]

[10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99,
 0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99]

[hash(s)%100 for s in ['different', 'objects', 'have', 'very', 'different', 'hashes']]

[18, 12, 89, 72, 18, 70]

Hashtables

class Hashtable:
    def __init__(self, n_buckets=1000):
        self.buckets = [None] * n_buckets
        
    def __setitem__(self, key, val):   #O(1)
        idx = hash(key)% len(self.buckets)
        self.buckets[idx]=val
        
    def __getitem__(self, key):    #O(1)
        idx = hash(key)% len(self.buckets)
        if self.buckets[idx] !=None:
            return self.buckets[idx]
        else:
            raise KeyError()
        
    def __contains__(self, key):
        try:
            _ = self[key]   # calls getitem, self is a hashtable
            return True
        except:
            return False

ht = Hashtable(10)
ht['batman'] = 'bruce wayne'
ht['superman'] = 'clark kent'
ht['spiderman'] = 'peter parker'

ht['spiderman']
ht['batman'] ="matt"
ht['batman']

'peter parker'

'matt'

"batman" in ht
"pyhtonguy" in ht

True

False

ht['batman1'] = 'bruce wayne1'
ht['superman1'] = 'clark kent1'
ht['spiderman1'] = 'peter parker1'
ht.buckets

['peter parker',
 None,
 'clark kent1',
 None,
 None,
 'bruce wayne',
 None,
 None,
 'clark kent',
 'peter parker1']

On Collisions

The "Birthday Problem"

Problem statement: Given $N$ people at a party, how likely is it that at least two people will have the same birthday?

def birthday_p(n_people):
    p_inv = 1
    for n in range(365, 365-n_people, -1):
        p_inv *= n / 365
    return 1 - p_inv

birthday_p(2)

0.002739726027397249

1-364/365

0.002739726027397249

%matplotlib inline
import matplotlib.pyplot as plt

n_people = range(1, 80)
plt.plot(n_people, [birthday_p(n) for n in n_people])
plt.show()

[<matplotlib.lines.Line2D at 0x17861e63c10>]

General collision statistics

Repeat the birthday problem, but with a given number of values and "buckets" that are allotted to hold them. How likely is it that two or more values will map to the same bucket?

def collision_p(n_values, n_buckets):
    p_inv = 1
    for n in range(n_buckets, n_buckets-n_values, -1):
        p_inv *= n / n_buckets
    return 1 - p_inv

collision_p(23, 365) # same as birthday problem, for 23 people

0.5072972343239857

collision_p(10, 100)

0.37184349044470544

collision_p(100, 1000)

0.9940410733677595

collision_p(100, 100000)

0.04831047413228129

# keeping number of values fixed at 100, but vary number of buckets: visualize probability of collision
%matplotlib inline
import matplotlib.pyplot as plt

n_buckets = range(100, 100001, 1000)
plt.plot(n_buckets, [collision_p(100, nb) for nb in n_buckets])
plt.show()

[<matplotlib.lines.Line2D at 0x17861ec33d0>]

def avg_num_collisions(n, b):
    """Returns the expected number of collisions for n values uniformly distributed
    over a hashtable of b buckets. Based on (fairly) elementary probability theory.
    (Pay attention in MATH 474!)"""
    return n - b + b * (1 - 1/b)**n

avg_num_collisions(28, 365)

1.011442040700615

avg_num_collisions(1000, 1000)

367.6954247709637

avg_num_collisions(1000, 10000)

48.32893558556316

Dealing with Collisions

To deal with collisions in a hashtable, we simply create a "chain" of key/value pairs for each bucket where collisions occur. The chain needs to be a data structure that supports quick insertion — natural choice: the linked list!

class Hashtable:   # handles collisions
    class Node:
        def __init__(self, key, val, next=None):
            self.key = key
            self.val = val
            self.next = next
            
    def __init__(self, n_buckets=1000):
        self.buckets = [None] * n_buckets
        
    def __setitem__(self, key, val):
        bucket_idx = hash(key) % len(self.buckets)
#        self.buckets[bucket_idx]=val
        # if there is a Node at the [bucket_idx] position that has the "key" we are looking for
        # update the val
        # otherwise, walk the linked list looking for the key, or append a new Node at the end
        #if self.buckets[bucket_idx].key == key:
        #    self.buckets[bucket_idx].val=val
        n =  self.buckets[bucket_idx]  # pointer to linked list of collisions, or None
        while n:  #n not = None
            if n.key== key:   # I have a Node
                n.val=val
                return
            else:
                n=n.next   #look at the next Node
        # I am out of the walking the linked list, and I did not find the key        
        self.buckets[bucket_idx]= Hashtable.Node(key, val, self.buckets[bucket_idx])  
                
    def __getitem__(self, key):
        bucket_idx = hash(key) % len(self.buckets)
        # walk the linked list of collisions, if find key, return value, else raise KeyError
        n =  self.buckets[bucket_idx]  # pointer to linked list of collisions, or None
        while n:  #n not = None
            if n.key== key:   
                return n.val
            else:
                n=n.next
        # exit loop means key not found
        raise KeyError()
                    
            
    def __contains__(self, key):
        try:
            _ = self[key]   #self.__getitem__(key)
            return True
        except:
            return False

ht = Hashtable(1)
ht['batman'] = 'bruce wayne'
ht['superman'] = 'clark kent'
ht['spiderman'] = 'peter parker'

ht.buckets

[<__main__.Hashtable.Node at 0x1c7073aeb20>]

ht['batman']
ht['superman']
ht['spiderman'] 

'bruce wayne'

'clark kent'

'peter parker'

def prep_ht(size):
    ht = Hashtable(size*10)
    for x in range(size):
        ht[x] = x
    return ht

def time_ht(size):
    return timeit.timeit('ht[random.randrange({})]'.format(size), 
                         'import random ; from __main__ import prep_ht ;'
                         'ht = prep_ht({})'.format(size),
                         number=100)

ht_timings = [time_ht(n)
                for n in range(10, 10000, 100)]

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(bin_search_timings, 'ro')
plt.plot(ht_timings, 'gs')
plt.plot(dict_timings, 'b^')
plt.show()

[<matplotlib.lines.Line2D at 0x1c709a79640>]

[<matplotlib.lines.Line2D at 0x1c709a79a60>]

[<matplotlib.lines.Line2D at 0x1c709a79dc0>]

Loose ends

Iteration

class Hashtable(Hashtable):
    def __iter__(self):
        # self.buckets is my array (python list), some entries none
        for item in self.buckets:
            while item:
                yield item.key
                item=item.next
   

ht = Hashtable(1)
ht['batman'] = 'bruce wayne'
ht['superman'] = 'clark kent'
ht['spiderman'] = 'peter parker'

for k in ht:
    print(k)

spiderman
superman
batman

ht1 = Hashtable(100)
ht1['batman'] = 'bruce wayne'
ht1['superman'] = 'clark kent'
ht1['spiderman'] = 'peter parker'
for k in ht1:
    print(k)

batman
superman
spiderman

Key ordering

ht = Hashtable()
d = {}
for x in 'apple banana cat dog elephant'.split():
    d[x[0]] = x
    ht[x[0]] = x

for k in d:
    print(k, '=>', d[k])

a => apple
b => banana
c => cat
d => dog
e => elephant

for k in ht:
    print(k, '=>', ht[k])

d => dog
a => apple
e => elephant
c => cat
b => banana

class OrderedHashtable:   # handles collisions
#    class Node:
#        def __init__(self, key, val, next=None):
#            self.key = key
#            self.val = val
#            self.next = next
    class Node:
        def __init__(self, index, next=None):
            self.index = index   #index is into the self.entries list
            self.next = next            

    def __init__(self, n_buckets=1000):
#        self.buckets = [None] * n_buckets
        self.indices = [None] * n_buckets   #buckets, the hash table
        self.entries=[]    # a list of key value pairs, use two element lists for [key, value]
        self.count=0  # how many items currently in the hashtable

    def __setitem__(self, key, val):
"""        bucket_idx = hash(key) % len(self.buckets)
        n =  self.buckets[bucket_idx]  # pointer to linked list of collisions, or None
        while n:  #n not = None
            if n.key== key:   # I have a Node
                n.val=val
                return
            else:
                n=n.next   #look at the next Node
        self.buckets[bucket_idx]= Hashtable.Node(key, val, self.buckets[bucket_idx])  
          """
        indices_idx = hash(key) % len(self.indices)
        n =  self.indices[indices_idx]  # pointer to linked list of collisions, or None
        while n:  #n not = None
            if self.entries[n.index] and self.entries[n.index][0] == key:
                self.entries[n.index][1]  = val
                return
            else:
                n=n.next
        # I have a new key value pair, I need to append to entries list
        # and then make the hashtable entry for the index of that node in the entries list
        self.entries.append([key,val])  #how do I get the index for this entry?
        # index is len(self.entries)-1
        self.indices[indices_idx] = OrderedHashtable.Node(len(self.entries)-1, self.indices[indices_idx] )
        self.count+=1

# THE REST OF THIS CLASS HAS NOT BEEN UPDATED YET FOR ORDEREDHASHTABLE        
    def __getitem__(self, key):
        bucket_idx = hash(key) % len(self.buckets)
        # walk the linked list of collisions, if find key, return value, else raise KeyError
        n =  self.buckets[bucket_idx]  # pointer to linked list of collisions, or None
        while n:  #n not = None
            if n.key== key:   
                return n.val
            else:
                n=n.next
        # exit loop means key not found
        raise KeyError()
                    
            
    def __contains__(self, key):
        try:
            _ = self[key]   #self.__getitem__(key)
            return True
        except:
            return False
        
    def __iter__(self):
        # self.buckets is my array (python list), some entries none
        for item in self.buckets:
            while item:
                yield item.key
                item=item.next

"Load factor" and Rehashing

It doesn't often make sense to start with a large number of buckets, unless we know in advance that the number of keys is going to be vast — also, the user of the hashtable would typically prefer to not be bothered with implementation details (i.e., bucket count) when using the data structure.

Instead: start with a relatively small number of buckets, and if the ratio of keys to the number of buckets (known as the load factor) is above some desired threshold — which we can determine using collision probabilities — we can dynamically increase the number of buckets. This requires, however, that we rehash all keys and potentially move them into new buckets (since the hash(key) % num_buckets mapping will likely be different with more buckets).

Other APIs

• FIXED __setitem__ (to update value for existing key)
• __delitem__
• keys & values (return iterators for keys and values)
• setdefault

Runtime analysis & Discussion

For a hashtable with $N$ key/value entries:

• Insertion: $O(?)$
• Lookup: $O(?)$
• Deletion: $O(?)$

Vocabulary list

• hashtable
• hashing and hashes
• collision
• hash buckets & chains
• birthday problem
• load factor
• rehashing

---

Addendum: On Hashability

Remember: a given object must always hash to the same value. This is required so that we can always map the object to the same hash bucket.

Hashcodes for collections of objects are usually computed from the hashcodes of its contents, e.g., the hash of a tuple is a function of the hashes of the objects in said tuple:

hash(('two', 'strings'))

This is useful. It allows us to use a tuple, for instance, as a key for a hashtable.

However, if the collection of objects is mutable — i.e., we can alter its contents — this means that we can potentially change its hashcode.`

If we were to use such a collection as a key in a hashtable, and alter the collection after it's been assigned to a particular bucket, this leads to a serious problem: the collection may now be in the wrong bucket (as it was assigned to a bucket based on its original hashcode)!

For this reason, only immutable types are, by default, hashable in Python. So while we can use integers, strings, and tuples as keys in dictionaries, lists (which are mutable) cannot be used. Indeed, Python marks built-in mutable types as "unhashable", e.g.,

hash([1, 2, 3])

That said, Python does support hashing on instances of custom classes (which are mutable). This is because the default hash function implementation does not rely on the contents of instances of custom classes. E.g.,

class Student:
    def __init__(self, fname, lname):
        self.fname = fname
        self.lname = lname

s = Student('John', 'Doe')
hash(s)

s.fname = 'Jane'
hash(s) # same as before mutation

We can change the default behavior by providing our own hash function in __hash__, e.g.,

class Student:
    def __init__(self, fname, lname):
        self.fname = fname
        self.lname = lname
        
    def __hash__(self):
        return hash(self.fname) + hash(self.lname)

s = Student('John', 'Doe')
hash(s)

s.fname = 'Jane'
hash(s)

But be careful: instances of this class are no longer suitable for use as keys in hashtables (or dictionaries), if you intend to mutate them after using them as keys!