Aed3-hashing-parte1 prof Moacir Ponti - Icc-usp

13 – Hashing Interno (parte 1) SCC501 - Introdução à Ciência de Computação II Paulo H. R. Gabriel phrg@icmc.usp.br Prof. Maciør Ponti Jr. www.icmc.usp.br/~maciør Instituto de Ciências Matemáticas e de Computação – USP 2010/2 Paulo e Maciør : ICMC-USP Hashing (parte 1) 2010/2 1/23 Sumário Contextualização Motivação Tabela Hash Tratamento de Colisões Paulo e Maciør : ICMC-USP Hashing (parte 1) 2010/2 2/23 Busca, inserção e remoção em vetores - Métodos de busca estudados até agora: Comparação de chaves - Valor relativo de cada chave - Tiramos proveito da ordenação Custo Ordenação: O(n⋅log(n)) ou O(n²) Busca: O(log(n)) Inserção? Remoção? Paulo e Maciør : ICMC-USP Hashing (parte 1) 2010/2 3/23 Tabela Hash ou de Espalhamento ou de Dispersão • Valor absoluto das chaves • Não compara, define valor (função) • Atingir diretamente a posição Em outras palavras... O(1) Intuitivo Fazemos com frequência... Pucio e Motoki - ICMC-USP Hashing (parte 1) 20.02.1/ 22 Acesso direto (1/2) • Indexar elementos em vetores Pucio e Motoki - ICMC-USP Hashing (parte 1) 20.02.1/ 22 Acesso direto (2/2) Limitações • Elementos não numéricos • Quantidade de espaço vazio • Frequência de atualizações Exemplo: Dicionários • Conjunto de palavras e significados • Diversas aplicações práticas (e.g. pré-processamento) • Necessidade de acesso direto (eficiência) • "Volátil" Pucio e Motoki - ICMC-USP Hashing (parte 1) 20.02.1/ 22 Conceitos (1/4) Ideia Central Utilizar uma função, aplicada a [parte] da informação (i.e., a chave), para devolver o índice onde a informação deve [deveria] ser armazenada. - A função é chamada função de espalhamento (ou função hash) - A estrutura de dados é a tabela de espalhamento (ou tabela hash) Ponto e Vírgula :: ICMC-USP \ Hashing (parte 1) \ 20.09.2 \ 7 / 23 Conceitos (2/4) Função de Espalhamento Uma função de espalhamento h( ) transforma uma chave x em um endereço-base h(x) da tabela hash. - Função hash: Função injetora - Na prática: - E se h(x) estiver ocupado? - Não há garantias de injetividade: pode existir y ≠ x tal que h(y) = h(x) Ponto e Vírgula :: ICMC-USP \ Hashing (parte 1) \ 20.09.2 \ 8 / 23 Conceitos (3/4) Ponto e Vírgula :: ICMC-USP \ Hashing (parte 1) \ 20.09.2 \ 9 / 23 Conceitos (4/4) • Idealmente: • Número baixo de colisões • Facilmente computável • Uniforme Profª: e Malú: (ICMC-USP) Hashing (parte 1) 2010/2 20 / 23