1. Hashtable

Tabela chave-valor. Suponha que usemos como função de hash o número de caracteres da string:

int hash(char *s) {
    return strlen(s) % 11;
}

Tabela:

4. Tatu, Faca => Colisão
6. Dragão
7. Mandragora

Problema: colisão de comprimento de palavra. Solução: armazenar uma lista de valores na tabela.

Buracos: gasta espaço para ganhar eficiência.

Mas a maior parte das palavras tem menos ou igual a cinco letras. Então precisamos de outra função de hash porque essa é ruim: vai ter muitas colisões. Uma boa função deixa as palavras o mais espalhadas o possível. Hash é «espalhar».

Possíveis funções hash: somar os caracteres da palavra, fazer um xor entre os caracteres da palavra.

// Palavras: casa, cachorro, armário, pedra, bola
int hash(char *c) {
    switch(s[0]) {
        case 'p':
            return 0;
        case 'a':
            return 1;
        case 'b':
            return 2;
        case 'a':
            if (s[s] == 's')
                return 3;
            else
                return 4;
    }
}

Gerador de funções hash: gperf.

1.1. Compilando

• Shell: ls, gcc, as

1.2. gcc:

- `-o arquivo`: arquivo de saída
- `-c`: só compila
- `-l`: biblioteca
- `-O n`: pode ser 1, 2, 3, é o nível de otimização