Playground - Implementación de una HashTable para Contactos
Clase 81 de 99 • 30 días de JavaScript
Contenido del curso
David Ochoa
student•
hace 3 años
JOHN FREDDY BUITRAGO QUEVEDO
student•
hace 3 años
Clase 81 de 99 • 30 días de JavaScript
Contenido del curso
David Ochoa
JOHN FREDDY BUITRAGO QUEVEDO
Alejandro Anaya
Rubén Hernández Hernández
Alejandro Anaya
Osvaldo Martinez Guillen
Joan Alexander Valerio Rodríguez
Duvan Alexis Palomino Ramirez
Carina Payleman
Rubén Hernández Hernández
Nicolás Felipe Pinto Vega
Elias Rayas Gonzalez
Victor Hernandez
Alexis Corrales
Pablo Pincay Alvarez
Angel Javier Sanchez Tenjo
Hiver Tapia
Raul Carrillo Garrido
Harold Zurita Simon
Victor Ortiz
Abril Darynka Tapia Sosa
Andres Ricardo Martinez Diaz
JAIME EDUARDO DIAZ TOBON
Michis anti-spoilers
!Michi Programando
Fue algo muy parecido a la lectura, simplemente tomar en cuenta como se accede al valor, mediante el metodo hash, entonces de esa manera se puede realizar las diferentes operaciones.
export class ContactList { constructor(size) { // Tu código aquí 👈 this.buckets = new Array(size); this.numBuckets = this.buckets.length } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } console.log(total % this.numBuckets); return total % this.numBuckets; } insert(name, phone) { // Tu código aquí 👈 let index = this.hash(name) if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]) } get(name) { // Tu código aquí 👈 let index = this.hash(name); if (!this.buckets[index]) { return null } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1] } } } retrieveAll() { // Tu código aquí 👈 let allValues = [] for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push(this.buckets[i][j]) } } } return allValues } delete(name) { // Tu código aquí 👈 let index = this.hash(name) console.log(index); if (!this.buckets[index]) { return null } if (this.buckets[index]) { this.buckets[index] = [] } } }
Anti-spoilers:
El método retrieveAll se puede reducir a una línea así:
retrieveAll() { return this.buckets.flat(1); }
🛡️🛡️Escudo anti-spoilers🛡️🛡️
Busqué hacer todos mis métodos con menos de 4 lineas de código 👀 (el número de lineas de código no indican si un algoritmo es mejor o peor) simplemente 'a veces' menos código es más claro y rápido de leer, a veces, no siempre... Mi solución:
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) total += name.charCodeAt(i); return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name) if (!this.buckets[index]) this.buckets[index] = []; this.buckets[index].push([name, phone]) } get(name) { let index = this.hash(name); if (!this.buckets[index]) return null return this.buckets[index].find(b => b[0] === name)[1] } retrieveAll() { return this.buckets.filter(b => b.length > 0).flat() } delete(name) { let index = this.hash(name) if (!this.buckets[index]) return null if (this.buckets[index]) delete this.buckets[index] } }
Un par de observaciones :eyes::
get() puede encontrarse un error debido a el caso en el que borraste un elemento pero el bucket si esta inicializado, por lo que al no encontrar esa key en el método find() te devuelve undefined, siendo que al poner [1] ya no funcione y te regrese un error. La solución sería que antes verifiques si existe el dato después del find antes de accesar a él para regresar el dato [1] o en su defecto null.delete() directamente estas borrando todo el bucket cosa que no es ideal ya que en un mismo bucket pueden llegar a guardarse diversas key por lo que tienes que borrar solamente el elemento que tiene esa key dentro del bucket.@ruben-hdez Excelentes tus observaciones, gracias por tomarte el tiempo de analizarlas y compartirlas. las corregiré, gracias :)
Mi solución:
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); } get(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } return null; } retrieveAll() { let allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push([this.buckets[i][j][0],this.buckets[i][j][1]]); } } } return allValues; } delete(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return delete this.buckets[index]; } } return null; } }
La practica hace el maestro 🤓!
Comparto mi solucion:
export class ContactList { constructor(size) { // Tu código aquí 👈 this.buckets = new Array(size); this.numBuckets = this.buckets.length; }
hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; }
insert(name, phone) { // Tu código aquí 👈 let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; }; this.buckets[index].push([name, phone]); }
get(name) { // Tu código aquí 👈 let index = this.hash(name); if (!this.buckets[index]) { return null; }; for (let i = 0; i < this.buckets[index].length; i++){ if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } }
retrieveAll() { // Tu código aquí 👈 let allValues = []; for (let i = 0; i < this.numBuckets; i++){ if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++){ allValues.push(this.buckets[i][j]); } } } return allValues; }
delete(name) { // Tu código aquí 👈 let index = this.hash(name); console.log(index); if (!this.buckets[index]) { return null; };
if (this.buckets[index]) { this.buckets[index] = []; }
} }
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); } get(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } } retrieveAll() { let all = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { all.push(this.buckets[i][j]); } } } return all; } delete(name) { let index = this.hash(name) if (!this.buckets[index]) { return null; } else { this.buckets[index] = []; } } }
💚Mi solución💚
🛡️MURO ANTI-SPOILERS🛡️
!dogphone
Mi implementación en cuanto a el constructor los métodos hash() e insert() son prácticamente como los de la lectura 80.
Sin embargo, los métodos get(), retrieveAll() y delete() trate de usar los métodos de Array para mejorar la legibilidad y hacerlos un tanto más cortos. Además me aseguré de validar todos los casos posibles.
👾Código
export class ContactList { constructor(size) { this.buckets = new Array(size) this.numBuckets = this.buckets.length } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { const index = this.hash(name) if (!this.buckets[index]) this.buckets[index] = [] this.buckets[index].push([name,phone]) } get(name) { const index = this.hash(name) if (!this.buckets[index]) return null const element = this.buckets[index].find(element => element[0] === name) if(element) return element[1] else return null } retrieveAll() { return this.buckets.filter(element => element).flat() } delete(name) { const index = this.hash(name) if (!this.buckets[index]) return null const elementIndex = this.buckets[index].findIndex(element => element[0] === name) if (elementIndex != -1) this.buckets[index].splice(elementIndex,1) else return null } }
Mi solución: . . . . . . . . . . . . . . . . . .
export class ContactList { constructor(size) { // Tu código aquí 👈 this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { // Tu código aquí 👈 const index = this.hash(name); if (!this.buckets[index]) this.buckets[index] = []; this.buckets[index].push([name, phone]); } get(name) { // Tu código aquí 👈 const index = this.hash(name); if (!this.buckets[index]) return null; for (let i = 0; i < this.buckets[index].length; i++){ if (this.buckets[index][i][0] === name) return this.buckets[index][i][1]; } return null; } retrieveAll() { // Tu código aquí 👈 const allBuckets = []; for (let i = 0; i < this.numBuckets; i++){ if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++){ allBuckets.push(this.buckets[i][j]); } } } return allBuckets; } delete(name) { // Tu código aquí 👈 const index = this.hash(name); if (!this.buckets[index]) return null; const internalIndex = this.buckets[index].findIndex(bucket => bucket[0] === name); if (internalIndex < 0) return null; this.buckets[index].splice(internalIndex, 1); } }
Solución
class ContactList { constructor(size) { // Tu código aquí 👈 this.contacts = new Array(size); this.numBuckets = this.contacts.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { // Tu código aquí 👈 const index = this.hash(name); if (!this.contacts[index]) this.contacts[index] = []; this.contacts[index].push([name, phone]); } get(name) { // Tu código aquí 👈 const index = this.hash(name); const bucket = this.contacts[index]; if (!bucket) return undefined; for (let i = 0; i < bucket.length; i++) { if (bucket[i][0] === name) return bucket[i][1]; } return undefined; } retrieveAll() { // Tu código aquí 👈 const retrievedContacts = []; this.contacts.forEach((contact) => { if (!contact) return; contact.forEach((pair) => retrievedContacts.push(pair)); }); return retrievedContacts; } delete(name) { // Tu código aquí 👈 const index = this.hash(name); const bucket = this.contacts[index]; if (!bucket) return undefined; for (let i = 0; i < bucket.length; i++) { if (bucket[i][0] === name) { const deletedPair = bucket.splice(i, 1)[0]; return deletedPair; } } return undefined; } }
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); return this.buckets[index]; } get(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++){ if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } return null; } retrieveAll() { let allValues = []; for (let i = 0; i < this.numBuckets; i++){ if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++){ allValues.push(this.buckets[i][j]); } } } console.log(allValues); return allValues; } delete(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index] = []; } } return null; } }
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { const index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); } get(name) { const index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } return null; } retrieveAll() { const allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push(this.buckets[i][j]); } } } return allValues; } delete(name) { const index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index].splice(i, 1); return; } } } }
. . . SPOILERS . . . . .
. . . . . .
. . . . .
. . . . .
class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name) if (!this.buckets[index]) this.buckets[index] = []; this.buckets[index].push([name, phone]) } get(name) { let index = this.hash(name); if (!this.buckets[index]) return null return this.buckets[index].find(bucket => bucket[0] === name)[1] } retrieveAll() { let allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let value of this.buckets[i]) { allValues.push(value); } } } return allValues; } delete(name) { let index = this.hash(name) if (!this.buckets[index]) return null if (this.buckets[index]) delete this.buckets[index] } }
Hola Comparto la solución, estaba bien explicado en el anterior clase..
✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅
export class ContactList { constructor(size) { // Dentro del constructor se inicializa un array con un tamaño arbitrario // Para asignarlo como el tamaño total de buckets en nuestra hashTable this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { // Esta función toma un "name" // Para poder calcular el índice del bucket donde el valor será almacenado let total = 0; // En este caso el algoritmo para crear un hash es muy sencillo // Para calcular el hash, se suman los valores ASCII de cada caracter de la key // y se toma el resto de la división de esta suma entre el total de buckets. for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { // Este método toma el "name" y un value que seria el phone, y los almacena en la hash table // Primero se calcula el índice usando la función hash const index = this.hash(name); // si ese bucket no existe, se inicializa como un array vacío. if (!this.buckets[index]) { this.buckets[index] = []; } // Luego se agrega un arreglo con la key y el value al bucket this.buckets[index].push([name, phone]); } get(name) { // Esta función toma una key que es el atributo "name" // y retorna el valor almacenado en la hash table // Primero se calcula el índice usando la función hash const index = this.hash(name); // si ese bucket no existe, se retorna null. if (!this.buckets[index]) { return null; } // Si el bucket existe, se recorre el array en busca de un arreglo // que tenga la key especificada for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } //Si no se encuentra la key, se retorna null. return null; } retrieveAll() { // Esta función retorna un array con todos los valores almacenados // Se recorren todos los buckets y, si existen, se agrega cada value a un array const allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push(this.buckets[i][j]); } } } return allValues; } delete(name) { const index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index].splice(i, 1); return; } } } }
Mas corto mas comprensible.
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name) if (!this.buckets[index]) this.buckets[index] = [] this.buckets[index].push([name, phone]); } get(name) { let index = this.hash(name); if (!this.buckets[index]) return null return this.buckets[index].find(value => value[0] === name)[1] } retrieveAll() { return this.buckets.filter(b => b.length > 0).flat() } delete(name) { let index = this.hash(name); if (!this.buckets[index]) return null delete this.buckets[index] } }
, , , , , , ,,
, , , , ,
export class ContactList { constructor(size) { this.size = size this.buckets = new Array(size) } hash(name) { let hash = 0 for (let i = 0; i < name.length; i++) { hash += name.charCodeAt(i) } return hash % this.size } insert(name, phone) { const index = this.hash(name) if (!this.buckets[index]) { this.buckets[index] = [] } this.buckets[index].push([name, phone]) } get(name) { const index = this.hash(name) if (this.buckets[index]) { for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1] } } } return null } retrieveAll() { const result = [] for (let i = 0; i < this.buckets.length; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { result.push(this.buckets[i][j]); } } } return result } delete(name) { const index = this.hash(name) if (this.buckets[index]) { for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index].splice(i, 1) return } } } return null } }
Solución… 😄 . Tener cuidado con el método retrieveAll(), puesto que en la lectura devuelve todos los valores. . Es decir los "[i][j][1]", mientras que el reto solo pide devolver todos los valores como: [name, phone] donde se incluye la clave también, por lo que corresponde a todos los "[i][j]". .
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); } get(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { return this.buckets[index][i][1]; } } return null; } retrieveAll() { let allValues = []; for (let i = 0; i < this.numBuckets; i++) { if (this.buckets[i]) { for (let j = 0; j < this.buckets[i].length; j++) { allValues.push(this.buckets[i][j]); } } } return allValues; } delete(name) { let index = this.hash(name); if (!this.buckets[index]) { return null; } for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index].splice(i, 1); } } return null; } }
Lo hice!!!!! . . . . . . . . . . . . . . . . . . . .
export class ContactList { constructor(size) { // Tu código aquí 👈 this.contacts = new Array(size); this.numBuckets = this.contacts.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { // Tu código aquí 👈 let index = this.hash(name); if (!this.contacts[index]) this.contacts[index] = []; this.contacts[index].push([name, phone]); } get(name) { // Tu código aquí 👈 let index = this.hash(name); if (!this.contacts[index]) return null; for (let i = 0; i < this.contacts[index].length; i++) { if (this.contacts[index][i][0] === name) return this.contacts[index][i][1]; else return null; } return null; } retrieveAll() { // Tu código aquí 👈 let allContacts = []; for (let i = 0; i < this.numBuckets; i++) { if (this.contacts[i]) { for (let j = 0; j < this.contacts[i].length; j++) allContacts.push(this.contacts[i][j]); } } return allContacts; } delete(name) { // Tu código aquí 👈 let index = this.hash(name); if (!this.contacts[index]) return null; this.contacts[index] = []; } }
Mi solución . . . . . . . . . . . . .
class ContactList { constructor(size) { // Tu código aquí 👈 this.contacts = new Array(size); this.numContacts = this.contacts.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numContacts; } insert(name, phone) { // Tu código aquí 👈 const index = this.hash(name); if (!this.contacts[index]){ this.contacts[index] = []; } this.contacts[index].push([name,phone]); } get(name) { let index = this.hash(name); if (!this.contacts[index]) return null for (let i = 0; i < this.contacts[index].length; i++) { if (this.contacts[index][i][0] === name) { return this.contacts[index][i][1]; } } } retrieveAll() { // Tu código aquí 👈 let allValues = []; for (let i = 0; i < this.numContacts; i++) { if (this.contacts[i]) { for (let j = 0; j < this.contacts[i].length; j++) { allValues.push(this.contacts[i][j]); } } } // Para finalmente retornarlo. return allValues; } delete(name) { // Tu código aquí 👈 let index = this.hash(name); if (!this.contacts[index]) return null for (let i = 0; i < this.contacts[index].length; i++) { this.contacts[index].splice(i, 1); } } }
Mi solución: . . . . . . . . . . .
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { // Tu código aquí 👈 let index = this.hash(name); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([name, phone]); } get(name) { let index = this.hash(name); if (!this.buckets[index]) { return null } for (const contact of this.buckets[index]) { if (contact[0] === name) { return contact[1]; } } } retrieveAll() { let allValues = []; for (const bucket of this.buckets) { if (bucket) { for (const element of bucket) { allValues.push(element); } } } return allValues; } delete(name) { let index = this.hash(name); if (!this.buckets[index]) { return null } let found = false; for (let i = 0; i < this.buckets[index].length; i++) { if (this.buckets[index][i][0] === name) { this.buckets[index].splice(i, 1); found = true; } } if (!found) { return null } } }
++MI SOLUCION++ 💪 . . . . . . . . . . . . . . . . . . . .
export class ContactList { constructor(size) { this.buckets = new Array(size); this.numBuckets = this.buckets.length; } hash(name) { let total = 0; for (let i = 0; i < name.length; i++) { total += name.charCodeAt(i); } return total % this.numBuckets; } insert(name, phone) { const index = this.hash(name); if (!this.buckets[index]) this.buckets[index] = []; this.buckets[index].push([name, phone]); } get(name) { const index = this.hash(name); if (!this.buckets[index]) return null; const contact = this.buckets[index].find(bucket => bucket[0] === name); return contact ? contact[1] : null; } retrieveAll() { return this.buckets.flat(); } delete(name) { const index = this.hash(name); if (!this.buckets[index]) return null; const indexContact = this.buckets[index].findIndex(bucket => bucket[0] === name) if (indexContact === -1) return null; delete this.buckets[index][indexContact] } }