Usaremos um objeto para representar a estrutura de dados.
import { defaultToString } from '../utils.js';
class HashTable {
_table;
_toStrFn;
constructor(toStrFn = defaultToString) {
this._toStrFn = toStrFn;
this._table = {};
}
size() {
return Object.keys(this._table).length;
}
isEmpty() {
return this.size() === 0;
}
clear() {
this._table = {};
}
}Também criaremos uma classe para gerar um para chave/valor, que será o valor salvo na tabela. Esta classe também terá um método toString:
export default class ValuePair {
#key;
#value;
constructor(key, value) {
this.#key = key;
this.#value = value;
}
toString() {
return `[#${this.#key}: ${this.#value}]`;
}
get key() {
return this.#key;
}
get value() {
return this.#value;
}
}A seguir, precisamos implementar três métodos básicos na classe HashTable:
put(key, value): adiciona um novo item à hash table (ou atualiza item existente);remove(key, value): remove o valor da tabela cuja chave é key;get(key): retorna o valor associado à key;
Antes de implementar os três métodos mencionados acima, precisamos criar a função hash:
_loseloseHashCode(key) {
if (typeof key === 'number') return key;
const tableKey = this._toStrFn(key);
let hash = 0;
for (let i = 0; i < tableKey.length; i++) {
hash += tableKey.charCodeAt(i);
}
return hash % 37
}
_hashCode(key) {
return this._loseloseHashCode(key);
}No método loseloseHashCode verificamos se key é um número; caso seja, a função retorna esse número. Em seguida, é gerado um número através da soma dos valores ASCII de todas os caracteres da key. Por fim, a função retorna o valor hash. Para trabalharmos com números baixos, usamos o resto da divisão do hash por um número arbitrário - isso previne trabalharmos com números muito grandes.
OBS: mais sobre a tabela ASCII aqui
Com a função hash concluída, podemos implementar os outros métodos.
put(key, value) {
if (key !== null && value !== null) {
const position = this._hashCode(key);
this._table[position] = new ValuePair(key, value);
return true;
}
return false;
}Primeiramente é verificado se key e value são válidos; caso não sejam, a função retorna false, indicando que o dado não foi inserido (ou atualizado) na hash table.
Para um par chave/valor válido, a função define uma posição na tabela usando hashCode(key). É criada, então, uma instância de ValuePair com a chave e o valor e na tabela uma nova instância de `ValuePair é armazenada.
get(key) {
const valuePair = this._table[this._hashCode(key)];
return valuePair === null ? undefined : valuePair.value
}Primeiro achamos a posição da key com a função hashCode, então acessamos a tabela nessa posição. Por fim a função retorna o valor associado à chave.
remove(key) {
const hash = this._hashCode(key);
const valuePair = this._table[hash];
if (valuePair !== null) {
delete this._table[hash];
return true;
}
return false;
}Para remover um valor da hash table, primeiro identificamos sua posição com a função hashCode. Caso o valor seja diferente de null (pois hash tables não aceitam null como uma chave válida), deletamos esse valor com o operador delete. A função retornar true se a remoção aconteceu, ou false caso a remoção não tenha ocorrido.
Às vezes chaves diferentes podem ter o mesmo hash. Chamamos essa situação colisão porque diferentes pares chave/valor são atribuidos à mesma posição de uma hash table.
Suponha a seguinte situação:
const hash = new HashTable();
hash.put('Jonathan', 'jon@email.com'); // loseloseHashCode('Jonathan') retorna 5
hash.put('Jamie', 'jamie@email.com'); // loseloseHashCode('Jamie') retorna 5
hash.put('Sue', 'sue@email.com'); // loseloseHashCode('Sue') retorna 5Podemos implementar a seguinte função toString na classe HashTable para verificar como ficaria a tabela após as inserções acima.
toString() {
if (this.isEmpty()) return '';
const keys = Object.keys(this._table);
let objString = `{${keys[0]} => ${this._table[keys[0]].toString()}}`;
for (let i = 1; i < keys.length; i++) {
objString = `${objString}\n{${keys[i]} => ${this._table[keys[i]].toString()}}`
}
return objString;
}Após chamar console.log(hash.toSring()) teremos o seguinte resultado:
console.log(hash.toString());
// {5 => [#Sue: sue@email.com]}Jonathan, Jamie e Sue receberam uma mesma hash, e Sue, por ter sido a última adição à tabela, fica sendo a ocupante da posição 5.
Há algumas técnicas para lidar com colisões: separate chaining (encadeamento), linear probing (sondagem linear) e double hashing. Comentaremos a seguir acerca das duas primeiras.
A técnica separate chaining consiste em criar uma lista encadeada (linked list) para cada posição da tabela, armazenando elementos nessa lista. É o modo mais simples de lidar com colisões, no entanto requer consumo adicional de memória fora da instância da hash table.
Para usar as técnicas separate chaining e linear probing precisamos alterar três métodos: put, get, e remove. Esses métodos serão diferentes para cada técnica.
Começemos com a implementação da classe HashTableSeparateChaining:
import ValuePair from './ValuePair.js';
import LinkedList2 from '../linked-list/LinkedList2.js';
import { defaultToString } from '../utils.js';
import HashTable from './HashTable.js';
export default class HashTableSeparateChaining extends HashTable {
_table;
constructor(toStrFn = defaultToString) {
super(toStrFn);
this._table = {};
}
}put(key, value) {
// If any 'nullish' value is passed into 'put' return 'false':
if (
key === undefined ||
key === null ||
value === undefined ||
value === null
)
return false;
// Hash the key
const position = this._hashCode(key);
// If there the position is empty, create a new linked list into it
if (this._table[position] === null || this._table[position] === undefined) {
this._table[position] = new LinkedList2();
}
// Insert the key/value into the linked list
this._table[position].push(new ValuePair(key, value));
// Return 'true' if the addition is successfull
return true;
}Verficamos se a posição em que tentaremos inserir um valor já possui outros valores. Caso seja o primeiro valor da posição, iniciamos uma instância de LinkedList, então adicionamos a instância de ValuePair à lista encadeada usando o método insert.
get(key) {
const position = this._hashCode(key);
const linkedList = this._table[position];
// If there is no such key, return 'undefined'
if (
linkedList === null ||
linkedList === undefined ||
linkedList?.isEmpty()
) {
return undefined;
}
// Get the 'head' reference of the list
let current = linkedList.head;
// Find the wanted element based on the 'key'
while (current !== null) {
if (current.element.key === key) {
return current.element.value;
}
current = current.next;
}
}Descobrimos a hash da key inserida na função, então acessamos a posição position na tabela, salvando o valor na variável linkedList.
Se linkedList é nullish ou é uma lista vazia, o método retorna undefined.
Caso a lista não esteja vazia, iteramos nela até encontrar o elemento cuja propriedade key seja igual ao argumento key passado no método get.
remove(key) {
const position = this._hashCode(key);
const linkedList = this._table[position];
//If there is no such key, return 'false'
if (
linkedList === null ||
linkedList === undefined ||
linkedList?.isEmpty()
) {
return false;
}
// Get the head reference of the list:
let current = linkedList.head;
// Find the element to be deleted:
while (current !== null) {
if (current.element.key === key) {
// When found, remove the element
linkedList.remove(current.element);
// If the list becomes empty, it is removed from the table
if (linkedList.isEmpty()) {
delete this._table[position];
}
// Retur 'true' to confirm the deletion
return true;
}
current = current.next;
}
}Assim como no método get, primeiramente é verificado se há algum valor na tabela com a key passada como argumento.
Caso haja uma lista na posição informada, iteramos sobre ela até encontrar o elemento cuja propriedade key seja igual ao argumento passado no método remove. Então, o elemento encontrado é removido, usando o método remove da classe LinkedList2.
Por fim, caso a lista tenha ficado vazia após a remoção do elemento, a entrada afetada da tabela é removida, e a função retorna true.
Esta técnica de resolução de conflitos chama-se sondagem linear porque lida com colisões armazenando os valores diretamente na tabela, e não em um estrutura de dados a parte.
Basicamente, ao tentarmos adicionar um elemento numa posição, caso esta esteja ocupada o valor é armazenado na próxima posição vaga.
O seguinte diagrama exemplifica o processo:
Se usarmos linear probing, para remover um par chave-valor da has table não basta remover o elemento da sua posição na tabela, como fizemos anteriormente. Se apenas removermos o elemento da tabela, é possível que ao procurar por outros elementos com mesmo hash encontremos aquela posição vazia.
Há duas opções para lidar com esse problema na remoção de elementos. A primeira opção chama-se soft delete. Essa abordagem consiste em usar um valor convencional (flag) para indicar a remoção do par chave/valor, em vez de realmente deletar o elemento. Com o passar do tempo, no entanto, a tabela poderá conter muitas dessas flags, o que reduzirá a eficiência da tabela.
O seguinte diagrama exemplifica a abordagem soft (lazy) deletion:
A outra estratégia possível para lidar com remoção de elementos é verificar, a cada remoção, se é necessário mover algum elemento a uma posição anterior na tabela. Ao procupara por uma chave, essa abordagem previne encontrar espaços vazios.
A seguinte imagem ilustra essa abordagem:
Ambas as estratégias têm prós e contras. A seguir vai a implementação da segunda estratégia:
Linear probing com realocação de elementos
A função hash lose-lose não é boa por gerar muitas colisões. Uma boa hash function deve ter as seguintes propriedades:
- Baixo tempo de inserção e extração de dados (performance);
- Baixa probabilidade de colisões
Um função simples que é melhor que a lose-lose chama-se djb2:
djb2HashCode(key) {
const tableKey = this._toStrFn(key);
let hash = 5381;
for (let i = 0; i < tableKey.length; i++) {
hash = (hash * 33) + tableKey.charCodeAt(i);
}
return hash % 1013;
}Transformada a key em string, a função djb2HashCode inicia a variável hash com um número primo (a maioria das implementações usa 5381); então, iterando por cada caracter da string representante da key, multiplica hash por 33 (usado como magic number) e soma este valor com o valor ASCII do caracter.
Por fim, a função retorna o resto da divisão de hash por outro número primo aleatório, que deve ser maior que o tamanho da hash table.
Essa, certamente, não é a melhor funcção hash existente, mas é uma das mais recomendadas pela comunidade.
Há, ainda, alguma técnicas para criar hash functions para chaves numéricas. Uma relação destas e algumas implementações podem ser encontradas neste link