open_addressing_exmaple.ts

open_addressing_in_hash_table_example.ts

/* 

Como funcionam as estratégias de "encadeamento" e "endereçamento aberto"?

> No encadeamento, as colisões são resolvidas armazenando múltiplos itens no mesmo índice (geralmente com uma lista ligada). No endereçamento aberto, novas posições são exploradas dentro do array para armazenar o item colidido.


Endereçamento aberto (Open Addressing) é uma técnica utilizada em estruturas de dados como tabelas de dispersão (hash tables) para lidar com colisões.

Quando ocorre uma colisão, ou seja, dois elementos diferentes têm o mesmo endereço de hash, o endereçamento aberto procura novas posições dentro do array para armazenar o item colidido.

Isso significa que, em vez de armazenar todos os elementos colididos em uma mesma posição (como em endereçamento fechado, Closed Addressing), o algoritmo busca uma nova posição vazia no array para armazenar o elemento.

Existem várias técnicas de endereçamento aberto, incluindo:

1. Linear Probing: busca a próxima posição vazia linearmente.
2. Quadratic Probing: busca a próxima posição vazia usando uma fórmula quadrática.
3. Double Hashing: usa uma segunda função de hash para determinar a próxima posição.

O endereçamento aberto oferece vantagens como:

- Melhor distribuição dos elementos
- Redução de colisões
- Maior eficiência na busca e inserção

*/

const hashTable = {}

const products = [
  {
    name: 'Laptop',
    price: 1000,
    category: 'Electronics'
  },
  {
    name: 'Keyboard',
    price: 50,
    category: 'Electronics'
  },
  {
    name: 'Teapot',
    price: 20,
    category: ' House'
  },
  {
    name: 'Shirt',
    price: 25,
    category: 'Clothing'
  },
  {
    name: 'Pants',
    price: 50,
    category: 'Clothing'
  }
]

const genHash = s => s.replaceAll(/[ae]/gi, '!').replaceAll(/[io]/gi, '@').replaceAll(/[u]/gi, '#')
for (let i = 0; i < products.length; i++) {
  const product = products[i]
  
  const hash = genHash(product.category)

  if (hashTable.hasOwnProperty(hash)) {
    /* using "Open Addressing" */
    hashTable[hash].push(product)
  } else {
    hashTable[hash] = [product]
  }
}

console.log(hashTable)