Implementación de HashMap personalizada

Question

Esta pregunta me fue formulada en una entrevista. Creo que la única forma de obtener la mejor solución es SOF. Entonces, la pregunta era "¿Cómo implementaría un HashMap personalizado en java? (Supongamos que no existe tal estructura de datos llamada HashMap)". La única respuesta que se me ocurrió fue implementar matrices asociativas (pero, una vez más, Java no tiene matrices asociativas). ¿Podrían los expertos darnos sus opiniones sobre esta pregunta?

Answer 1

respuesta corta:

Sería una matriz de matrices (o listas).

Object[][] map; 

donde map[bucketIndex] devolvería el 'cubo'.

Al insertar algo necesita una función para calcular bucketIndex esto usaría el hashcode del objeto insertado.

Boom done!

:)

Answer 2

Look at Cliff Haga clic de nonblockinghahmap para un ejemplo de la necesidad de un HashMap implementado en Java. Recuerde que una matriz asociada es solo otro nombre para un mapa hash, por lo que le está preguntando cómo implementarlo.

En general, los hash se implementan utilizando matrices estándar (no listas o cualquier otra cosa para la velocidad). El problema es qué hay dentro de cada una de estas matrices ... en el caso de una colisión hash, ¿desea utilizar una LinkedList (encadenamiento) o desea reajustar e ir a otra ubicación de la matriz (direccionamiento abierto). Lea más ciencias de la computación para conocer el costo/beneficio de hacer ambas cosas.

Answer 3

Debe usar una matriz dimensional. Object [] arr.

El índice de la matriz es el código hash normalizado del objeto Key. La matriz contiene el par.

La razón por la cual el valor consiste en clave y valor es que si hay una colisión hash, tiene que ir a través de la lista de claves dentro de la ranura y averiguar cuál es la clave correcta (usando iguales en el objeto clave)

Answer 4

public class ArrayAsHashMap { 

    Object [][] hashArr = new Object [10] [2]; 

    public void put(HashObject key, String value){ 
     int index = key.hashCode(); 
     Object [] arr = {key, value}; 
     hashArr[index] = arr; 
    } 

    public String get(HashObject key){ 
     int index = key.hashCode(); 
     Object [] arr = hashArr[index]; 
     return (String)arr[1]; 

    }   

} 

Answer 5

this El artículo explica HashMap y otras colecciones muy bien. Echar un vistazo.

Crear una clase que sirve como una asignación en el mapa

public class MyEntry<K, V> { 
    private final K key; 
    private V value; 

    public MyEntry(K key, V value) { 
    this.key = key; 
    this.value = value; 
    } 

    public K getKey() { 
    return key; 
    } 

    public V getValue() { 
    return value; 
    } 

    public void setValue(V value) { 
    this.value = value; 
    } 
} 

Y la clase mapa que utilizará esas entradas

import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Set; 

public class MyMap<K, V> { 
    private int size; 
    private int DEFAULT_CAPACITY = 16; 
    @SuppressWarnings("unchecked") 
    private MyEntry<K, V>[] values = new MyEntry[DEFAULT_CAPACITY]; 


    public V get(K key) { 
    for (int i = 0; i < size; i++) { 
     if (values[i] != null) { 
     if (values[i].getKey().equals(key)) { 
      return values[i].getValue(); 
     } 
     } 
    } 
    return null; 
    } 

    public void put(K key, V value) { 
    boolean insert = true; 
    for (int i = 0; i < size; i++) { 
     if (values[i].getKey().equals(key)) { 
     values[i].setValue(value); 
     insert = false; 
     } 
    } 
    if (insert) { 
     ensureCapa(); 
     values[size++] = new MyEntry<K, V>(key, value); 
    } 
    } 

    private void ensureCapa() { 
    if (size == values.length) { 
     int newSize = values.length * 2; 
     values = Arrays.copyOf(values, newSize); 
    } 
    } 

    public int size() { 
    return size; 
    } 

    public void remove(K key) { 
    for (int i = 0; i < size; i++) { 
     if (values[i].getKey().equals(key)) { 
     values[i] = null; 
     size--; 
     condenseArray(i); 
     } 
    } 
    } 

    private void condenseArray(int start) { 
    for (int i = start; i < size; i++) { 
     values[i] = values[i + 1]; 
    } 
    } 

    public Set<K> keySet() { 
    Set<K> set = new HashSet<K>(); 
    for (int i = 0; i < size; i++) { 
     set.add(values[i].getKey()); 
    } 
    return set; 
    } 
} 

Answer 6

Referencias: - http://javarevisited.blogspot.sg/2011/10/override-hashcode-in-java-example.html - http://javarevisited.blogspot.in/2011/02/how-to-write-equals-method-in-java.html

class Entry<K, V> { 
    K key; 
    V val; 

    public K getKey() { 
     return key; 
    } 

    public void setKey(K key) { 
     this.key = key; 
    } 

    public V getVal() { 
     return val; 
    } 

    public void setVal(V val) { 
     this.val = val; 
    } 

    @Override 
    public int hashCode() { 
     int prime = 13; 
     int mul = 11; 
     if (key != null) { 
      int hashCode = prime * mul + key.hashCode(); 
      return hashCode; 
     } 
     return 0; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) { 
      return true; 
     } 
     if (o == null || this.getClass().getName() != o.getClass().getName()) { 
      return false; 
     } 
     Entry e = (Entry) o; 
     if (this.key == e.key) { 
      return true; 
     } 
     return false; 
    } 
} 

public class HashMapImpl<K, V> { 
    private float loadfactor = 0.75f; 
    private int capacity = 100; 
    private int size = 0; 
    private Entry<K, V> table[] = new Entry[capacity]; 

    private int Hashing(int hashCode) { 
     int location = hashCode % capacity; 
     System.out.println("Location:"+location); 
     return location; 
    } 

    public int size() { 
     // TODO Auto-generated method stub 
     return this.size; 
    } 

    public boolean isEmpty() { 
     if(this.size == 0) { 
      return true; 
     } 
     return false; 
    } 

    public boolean containsKey(Object key) { 
     if(key == null) { 
      if(table[0].getKey() == null) { 
       return true; 
      } 
     } 
     int location = Hashing(key.hashCode()); 
     Entry e = null; 
     try { 
      e = table[location]; 
     }catch(NullPointerException ex) { 

     } 
     if(e!= null && e.getKey() == key) { 
      return true; 
     } 
     return false; 
    } 

    public boolean containsValue(Object value) { 
     for(int i=0; i<table.length;i++) { 
      if(table[i] != null && table[i].getVal() == value) { 
       return true; 
      } 
     } 
     return false; 
    } 

    public V get(K key) { 
     V ret = null; 
     if(key == null) { 
      Entry<K, V> e = null; 
      try{ 
       e = table[0]; 
      }catch(NullPointerException ex) { 

      } 
      if(e != null) { 
       return (V) e.getVal(); 
      } 
     } else { 
      int location = Hashing(key.hashCode()); 
      Entry<K, V> e = null; 
      try{ 
      e = table[location]; 
      }catch(NullPointerException ex) { 

      } 
      if(e!= null && e.getKey() == key) { 
       return (V)e.getVal(); 
      } 
     } 
     return ret; 
    } 

    public V put(K key, V val) { 
     V ret = null; 
     if (key == null) { 
      ret = putForNullKey(val); 
      return ret; 
     } else { 
      int location = Hashing(key.hashCode()); 
      if(location >= capacity) { 
       System.out.println("Rehashing required"); 
       return null; 
      } 
      Entry<K, V> e = null; 
      try{ 
      e = table[location]; 
      }catch(NullPointerException ex) { 

      } 
      if (e!= null && e.getKey() == key) { 
       ret = (V) e.getVal(); 
      } else { 
       Entry<K, V> eNew = new Entry<K,V>(); 
       eNew.setKey(key); 
       eNew.setVal(val); 
       table[location] = eNew; 
       size++; 
      } 
     } 
     return ret; 
    } 

    private V putForNullKey(V val) { 
     Entry<K, V> e = null; 
     try { 
      e = table[0]; 
     }catch(NullPointerException ex) { 

     } 
     V ret = null; 
     if (e != null && e.getKey() == null) { 
      ret = (V) e.getVal(); 
      e.setVal(val); 
      return ret; 
     } else { 
      Entry<K, V> eNew = new Entry<K,V>(); 
      eNew.setKey(null); 
      eNew.setVal(val); 
      table[0] = eNew; 
      size++; 
     } 
     return ret; 
    } 

    public V remove(K key) { 
     int location = Hashing(key.hashCode()); 
     V ret = null; 
     if(table[location].getKey() == key) { 
      for(int i=location; i<table.length;i++) { 
       table[i] = table[i+1]; 
      } 
     } 
     return ret; 
    } 

    public static void main(String[] args) { 
     HashMapImpl<Integer, String> hashMap = new HashMapImpl<Integer, String>(); 
     hashMap.put(10, "Apple"); 
     hashMap.put(1, "Orange"); 
     hashMap.put(79, "Grape"); 
     System.out.println("Val at 79 "+hashMap.get(79)); 
     System.out.println("Val at 1 "+hashMap.get(1)); 
     System.out.println("Val at 10 "+hashMap.get(10)); 
     System.out.println("Val at 2 "+hashMap.get(2)); 
     hashMap.put(null, "Pear"); 
     System.out.println("Val at null "+hashMap.get(null)); 
     System.out.println("Hashmap has key at null:"+hashMap.containsKey(null)); 
     System.out.println("Hashmap has value at null:"+hashMap.containsValue("Pear")); 
     System.out.println("Size of Map:"+hashMap.size()); 
    } 


}