Funciones Hash y Tablas Hash

Funciones Hash

• Una función hash convierte un valor grande (como una cadena) en un valor pequeño (como un entero).
• Entrada: Valor grande.
• Salida: Valor pequeño, adecuado para indexar una matriz.
• Este entero se llama código hash o hash.

Ejemplo de Función Hash

• Aquí tienes un ejemplo de una función hash simple:

def hash(s):
    code = 0
    for elemento in s:
        code += ord(elemento)
    return code

• La función convierte una cadena en un entero.

Tablas Hash

• Si se utiliza una función hash para indexar en una array, este array se llama tabla hash.

Terminología para Tablas Hash

• Clave: El valor grande (ej., cadena) que se quiere almacenar.
• Función hash: Función que convierte la clave en un array.
• Tabla hash: El array que almacena los valores.

Colisiones en Tablas Hash

• Múltiples claves pueden dar el mismo índice
• Esto se llama colisión.
• La resolución de colisiones es una estrategia para manejar colisiones.
• Hay dos principales estrategias:
  • Encadenamiento separado
  • Direccionamiento abierto

Resolución de Colisiones: Encadenamiento Separado

• Encadenamiento separado: Cada índice del array almacena una lista de valores.
• Cada lista contiene todas las claves que dan ese índice.
• También se llama: Hashing con encadenamiento, Hashing abierto.

Implementación de Encadenamiento Separado

• Cada índice del array almacena una lista enlazada (u otra estructura de lista).
• Al insertar, calcula el hash de la clave para encontrar el índice, y agrega la clave a la lista en ese índice.
• Al buscar, calcula el hash de la clave para encontrar el índice, y busca la clave en la lista en ese índice.

Resolución de Colisiones: Direccionamiento Abierto

• Direccionamiento abierto: Si hay una colisión, encuentra espacio vacío en el array.
• También llamado hashing cerrado.
• Hay varias estrategias para encontrar un lugar vacío:
  • Prueba lineal
  • Prueba cuadrática
  • Hashing doble

Prueba Lineal

• Prueba lineal: Si hay una colisión, revisa el siguiente espacio en el array.
• Si el espacio está vacío, utilízalo.
• Si el espacio está lleno, revisa el siguiente espacio.
• Repite hasta que se encuentre un espacio vacío.
• Es posible que debas hacer una iteración hasta el principio del array.

Implementación de Prueba Lineal

• Al insertar, hashea la clave para encontrar el índice.
• Si el índice está vacío, inserta la clave allí.
• Si el índice está lleno, busca el siguiente índice.
• Repite hasta que se encuentre un índice vacío.
• Al buscar, hashea la clave para encontrar el índice.
• Si la clave está en ese índice, devuélvela.
• Si la clave no está en ese índice, busca el siguiente índice.
• Repite hasta que se encuentre la clave o se encuentre un índice vacío.

Otras Estrategias de Sondeo

• Sondeo cuadrático: Si hay una colisión, revisa el siguiente espacio en el array, pero aumenta el índice una cantidad cuadrática.
• Por ejemplo, revisa el índice + 1, índice + 4, índice + 9, índice + 16, etc.
• Es más probable que encuentres un espacio vacío que con el sondeo lineal.
• Hashing doble: Utiliza una segunda función de hash para determinar el incremento.
• Por ejemplo, revisa el índice + hash2(clave), índice + 2hash2(clave), índice + 3hash2(clave), etc.
• Es aún más probable que encuentres un espacio vacío que con el sondeo cuadrático.

Implementación de la Tabla Hash

• Ejemplo de Implementación de tabla hash en Python, con Encadenamiento Separado:

class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)]

    def insert(self, key, value):
        index = hash(key) % self.capacity
        self.table[index].append((key, value))

    def find(self, key):
        index = hash(key) % self.capacity
        for k, v in self.table[index]:
            if k == key:
                return v
        return None # No encontrado

• Ejemplo de uso:

table = HashTable(10)
table.insert("apple", 1)
table.insert("banana", 2)
table.insert("cherry", 3)
print(table.find("banana")) # Prints 2
print(table.find("grape"))  # Prints None

Rendimiento de la Tabla Hash

Encadenamiento Separado

• Inserción: $O(1)$
  • Solo se agrega a la lista en el índice.
• Búsqueda: $O(L)$
  • Donde $L$ es la longitud promedio de las listas.
  • Si la función hash es buena, $L$ será pequeño.
  • Si la función hash es mala, $L$ podría ser grande; por ejemplo, si todas las claves dan el mismo índice, $L=N$.

Direccionamiento Abierto

• Inserción: $O(1)$ en promedio.
  • Pero podría ser $O(N)$ en el peor de los casos; por ejemplo, si tienes que hacer muchas pruebas para encontrar un espacio vacío.
• Búsqueda: $O(1)$ en promedio.
  • Pero podría ser $O(N)$ en el peor de los casos; por ejemplo, si tienes que hacer muchas pruebas para encontrar la clave.

Diseño de la Función Hash

• Cuanto mejor sea la función hash, más uniformemente distribuirá las claves a través de la matriz.
• Una función hash mala causa muchas colisiones. Y eso empeora el rendimiento de la tabla hash.

Propiedades de una Buena Función Hash

• Debe ser rápida de calcular.
• Debe distribuir las claves uniformemente a través del array.
• Debe ser determinante.

Funciones Hash Comunes

• Método de división: hash(clave) = clave % tamaño_del_array
  • Simple y rápida.
  • Pero puede ser malo si el tamaño del array es múltiplo de un factor común de las claves.
• Método de multiplicación: hash(clave) = piso(tamaño_del_array * (clave * A % 1))
  • Donde A es una constante entre 0 y 1.
  • Menos sensible al tamaño del array.
• Hashing universal: Elige una función hash aleatoria de una familia de funciones hash.
  • Garantiza un buen rendimiento en promedio.
  • Pero es más complejo de implementar.

Funciones Hash en Python

• Python tiene una función hash integrada: hash()

 hash("hello")
## -4777266968777927679
hash("world")
## 2816481427714474791
hash("hello")
## -4777266968777927679

Objetos Hasheables

• No todos los objetos pueden ser hasheados.
• Solo los objetos inmutables se pueden hashear (ej., cadenas, números, tuplas).
• Los objetos mutables no se pueden hashear (ej., listas, diccionarios).
• Esto es porque el valor hash de un objeto no debe cambiar.
• Si el valor hash de un objeto cambia, éste se almacenará en el índice incorrecto en la tabla hash, lo cual rompería la tabla hash.

Resumen

• Una función hash convierte un valor grande a uno pequeño.
• Las tablas hash usan una función hash para indexar en un array.
• Las colisiones ocurren cuando dos claves dan el mismo índice.
• Estrategias de resolución de colisiones:
  • Encadenamiento separado
  • Direccionamiento abierto:
    • Prueba lineal
    • Prueba cuadrática
    • Hashing doble
• Las buenas funciones hash distribuyen las claves uniformemente a través del array.

Espacios Vectoriales

Definición

• Un espacio vectorial es un conjunto 𝑉 con:
• Una operación de adición: 𝑉×𝑉→𝑉. Denotada v + w , donde v , w ∈𝑉
• Una operación de multiplicación escalar: ℝ×𝑉→𝑉. Denotada c v , donde c ∈ℝ y v ∈𝑉
• Operaciones que deben satisfacer los siguientes axiomas: Para todos u , v , w ∈𝑉 y a , b ∈ℝ:
  1. u + v ∈ V
  2. a u ∈ V
  3. u + v = v + u
  4. u + ( v + w ) = ( u + v ) + w
  5. Existe un vector cero 0 ∈ V tal que u + 0 = u
  6. Para cada u ∈ V , existe − u ∈ V tal que u + ( − u ) = 0
  7. a ( u + v ) = a u + a v
  8. ( a + b ) u = a u + b u
  9. a ( b u ) = ( a b ) u
  10. 1 u = u

Ejemplos

• ℝ n
• ℙ n = { a x n + b x n − 1 + ⋯ + c ∣ a , b , ⋯ , c ∈ ℝ } = polinomios de grado ≤ n
• M m × n ( ℝ ) = conjunto de todas las matrices m × n .
• C ( ℝ ) = conjunto de todas las funciones continuas f : ℝ → ℝ

Teorema

Sea 𝑉 un espacio vectorial, u ∈𝑉 , y c ∈ℝ . Entonces:

• 0 u = 0
• c 0 = 0
• ( − 1 ) u = − u
• Si c u = 0 , entonces ambos c = 0 o u = 0

Subespacios

Sea 𝑉 un espacio vectorial y 𝑊 un subconjunto de 𝑉 . Entonces 𝑊 es un subespacio de 𝑉 si 𝑊 también es un espacio vectorial.

Teorema

Sea 𝑉 un espacio vectorial y 𝑊 un subconjunto de 𝑉 . Entonces 𝑊 es un subespacio de 𝑉 sí y solo si:

1. 0 ∈ W
2. Para todos u , v ∈ W, u + v ∈ W
3. Para todos u ∈ W y c ∈ R , c u ∈ W

Ejemplos

Sea 𝑉 = ℝ 2 .

• 𝑊 = { [ x 0 ] ∣ x ∈ ℝ } es un subespacio de ℝ 2
• 𝑊 = { [ x 1 ] ∣ x ∈ ℝ } no es un subespacio de ℝ 2
• 𝑊 = { [ x x 2 ] ∣ x ∈ ℝ } no es un subespacio de ℝ 2

Teorema

Sea 𝑉 un espacio vectorial y v 1 , ⋯ , v n ∈ V . Entonces 𝑊 = span { v 1 , ⋯ , v n } es un subespacio de 𝑉 .

• Ejemplo:* Sean v 1 = [ 1 1 1 ] y v 2 = [ 1 2 3 ] . Entonces 𝑊 = span { v 1 , v 2 } es un subespacio de ℝ 3 .

Espacios Vectoriales: Continuación

Sea 𝐴 Una matriz m x n.

• 𝑁 ( 𝐴 ) = { x ∈ ℝ n ∣ 𝐴 x = 0 } Se denomina espacio nulo de 𝐴 .
• 𝐶 ( 𝐴 ) = { b ∈ ℝ m ∣ 𝐴 x = b Tiene una solución } Se llama el espacio de columna de 𝐴 .

Teorema

𝑁 ( 𝐴 ) es un subespacio de ℝ n y 𝐶 ( 𝐴 ) es un subespacio de ℝ m.

Prueba

Sean x , y ∈ 𝑁 ( 𝐴 ) . Entonces 𝐴 x = 0 y 𝐴 y = 0 . Entonces 𝐴 ( x + y ) = 𝐴 x + 𝐴 y = 0 + 0 = 0 , así que x + y ∈ 𝑁 ( 𝐴 ) . Sea c ∈ ℝ . Entonces 𝐴 ( c x ) = c 𝐴 x = c 0 = 0 , así que c x ∈ 𝑁 ( 𝐴 ) . También, 0 ∈ 𝑁 ( 𝐴 ) Ya que 𝐴 0 = 0 . Por lo tanto, 𝑁 ( 𝐴 ) es un subespacio de ℝ n.

• Independencia lineal Sea 𝑉 un espacio vectorial y 𝑣 1 , ⋯ , 𝑣 n ∈ V . Entonces 𝑣 1 , ⋯ , 𝑣 n son linealmente independientes si la única solución es: c 1 v 1 + ⋯ + c n v n = 0 Es c 1 = ⋯ = c n = 0 . De lo contrario, 𝑣 1 , ⋯ , 𝑣 n son linealmente dependientes.

Teorema de Bayes

• El Teorema de Bayes describe la probabilidad de un evento basándose en el conocimiento previo de las condiciones que pueden estar relacionadas con el evento.
• Formalmente, el teorema de Bayes se expresa como:

$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)} $$

• $P(A|B)$: Probabilidad condicional de A dado que B es verdadero.
• $P(B|A)$: Probabilidad condicional de B dado que A es verdadero.
• $P(A)$: Probabilidad a priori de A.
• $P(B)$: Probabilidad a priori de B.

Deducción del Teorema

• Considere dos eventos, A y B. La probabilidad de que ambos ocurran ($P(A \cap B)$) puede expresarse de dos maneras: $$ P(A \cap B) = P(A|B)P(B) $$ $$ P(A \cap B) = P(B|A)P(A) $$ Igualando las dos expresiones, derivamos el Teorema de Bayes.

Teorema de Bayes en la Práctica

• Ejemplo: en el contexto de las pruebas médicas, incluso un resultado de prueba positivo no implica necesariamente que un paciente tenga una enfermedad.
• La probabilidad de un resultado positivo de la prueba (la probabilidad a priori) debe considerar la prevalencia de la enfermedad en la población.