Qual é a relação entre funções de hash e objetos mutáveis/imutáveis?

Os objetos em Python dividem-se em mutáveis (mutable) e imutáveis (immutable). A relação com as funções de hash reside no facto de que apenas objetos imutáveis são hasháveis (hashable) e, consequentemente, podem ser utilizados como chaves de dicionário ou elementos de conjuntos.

• Objetos imutáveis: string (str), tuplo (tuple), número (int, float, bool), NoneType, etc. O seu valor não pode ser alterado após a criação. O Python calcula o valor de hash para esses objetos uma única vez.
• Objetos mutáveis: lista (list), dicionário (dict), conjunto (set), etc. O seu valor pode ser alterado após a criação. Se objetos mutáveis fossem hasháveis, o seu valor de hash poderia mudar após serem adicionados a um dicionário ou conjunto, o que quebraria o funcionamento das estruturas de dados baseadas em tabelas de hash.

A relação manifesta-se na utilização de dicionários e conjuntos:

• Dicionários: usam uma tabela de hash para acesso rápido aos valores por chave. As chaves do dicionário devem ser hasháveis.
• Conjuntos: também usam uma tabela de hash para armazenar elementos únicos. Os elementos do conjunto devem ser hasháveis.

# Isto funciona porque a tupla é um objeto imutável
my_dict = {(1, 2): 'olá'}
my_set = {(1, 2)}

# Isto irá gerar um erro TypeError, pois a lista é um objeto mutável
# my_dict = {[1, 2]: 'olá'}
# my_set = {[1, 2]}

# TypeError: unhashable type: 'list'