Buenas,
Para verificar lo que habia hecho en el ejercicio fui a ver la solucion del parcial y me quedo la siguiente duda. Nunca se dice que el usuario no pueda modificar el mismo valor varias veces, ni que el caso promedio sea actualizar solo 1 vez cada valor. Como se puede afirmar entonces que el orden promedio de Desasociar, por ejemplo, que tiene que recorrer toda la lista del arreglo de hash en el lugar : x%(2*N), tenga O(1)?
La otra duda que me habia quedado es porque el arreglo lo declaran de tamanio 2*N? Probabilisticamnte, ya con un arreglo de tamanio N, me quedaria el factor de carga 1. Intente verlo por el lado que hay N actualizaciones mas, pero la funcion de hash sigue siendo la misma entonces voy a insertar el elemento "actualizado" en la misma celda del array. Si el tamanio del array es de 2*N en promedio me van a quedar N celdas vacias y N celdas con una lista.
En realidad al usar x%(2*N) no se está cumpliendo con la letra que dice que la función hash debe ser x%N.
Si la letra no lo pidiera no estaría mal. Se sabe que puede haber hasta 2*N nodos (porque puede haber N actualizaciones). Al hacer la tabla más grande va a haber menos colisiones entre claves y las listas van a ser más cortas. El factor de carga se va a mantener menor a 1. También se podría haber usado 3*N/2 o cualquier otro valor mayor que N. Y tampoco estaría mal usar N pero el factor de carga podría llegar a ser 2.
Con respecto a la primera pregunta se puede afirmar porque es en promedio. Si una clave se actualiza muchas veces la lista en la que está será más larga pero las otras probablemente tengan solo 1 elemento.
Esto no es diferente a una tabla en la que no hay actualizaciones. Puede haber una lista muy larga porque hay muchas colisiones. Recorrer esa lista no es O(1) pero las demás sí. Entonces, en promedio recorrer alguna lista es O(1).