Estoy tratando de implementar la funcionalidad de hashmap en JavaScript y quiero mantener todo en tiempo constante.
Problema 1: eliminar el elemento de la matriz en tiempo constante (O (1)) Y estoy usando la matriz.
Problema 2: la mejor manera de resolver el problema de colisión en caso de que tengamos el mismo hash para diferentes claves.
Problema 3: la mejor manera de crear código hash. Actualmente estoy usando algunos de los valores ASCII de cada carácter.
ejemplo de código
class myHashMap { constructor(size = 0 ){ if(size){ this.hashMap = new Array(size).fill(null); this.size = size; } else{ this.hashMap = new Array(); this.size = 0; } } hash(key){ // Here hashing can have collision //for example: 122 and 212 will have same hash which is not correct let CharArray = key.split(""); return CharArray.reduce((acc,current) => { return acc+current.charCodeAt(0); },0); } set(key,value) { this.size++; this.hashMap[this.hash(key)] = value; } get(key){ return this.hashMap[key]; } has(key){ return this.hashMap[key]; } remove(key) { this.size--; this.hashMap.splice(this.hash(key),1); // Here I need to remove element in O(1) } }Problema 1: eliminar el elemento de la matriz en tiempo constante (O (1)) Y estoy usando la matriz.
A menos que esté utilizando alguna definición no estándar de "matriz", no puede eliminar un elemento de una matriz en tiempo constante. Puede establecer un elemento en algún valor nulo en tiempo constante. Pero el uso estándar de "matriz" significa múltiples elementos de tamaño conocido que se distribuyen en la memoria contigua de modo que se pueda acceder a ellos mediante un índice en tiempo constante a través de la aritmética de punteros. Para eliminar un elemento de dicha estructura, lo que significa que la matriz en realidad se vuelve más pequeña, necesitaría al menos copiar los elementos de la matriz después del elemento que está eliminando, que es una operación O (n).
Problema 2: la mejor manera de resolver el problema de colisión en caso de que tengamos el mismo hash para diferentes claves.
No hay mejor manera. Hay varias soluciones a este problema que hacen diferentes compensaciones con respecto a la eficiencia del tiempo, el espacio, la facilidad de implementación y otras consideraciones. Las dos grandes clases de soluciones más comunes son (1) el uso de una estructura de "cubo", esencialmente haciendo que la tabla hash sea una matriz de instancias en su mayoría vacías de otro tipo de contenedor (las listas vinculadas históricamente eran comunes) y (2) dejar la tabla sea plana y maneje las colisiones mediante el "direccionamiento abierto", lo que significa sondear hasta que encuentre una ranura vacía que comience en la ranura encontrada por el índice hash. De los anteriores, generalmente (1) es más fácil de implementar.
Problema 3: la mejor manera de crear código hash. Actualmente estoy usando algunos de los valores ASCII de cada carácter.
Este es un tema muy amplio, pero sí, debe usar los valores numéricos de los caracteres en la cadena, la pregunta es qué hace con esos valores. Busque un ejemplo de la implementación de boost::hash_combine en C++, del cual hay muchas referencias en StackOverflow .