Implementazione HashMap personalizzata

Question

Questa domanda mi è stata posta in un'intervista. Penso che l'unico modo per ottenere la migliore soluzione sia SOF. Quindi la domanda era "Come implementeresti una HashMap personalizzata in java (Supponiamo che non ci sia una tale struttura dati chiamata HashMap)". L'unica risposta che ho potuto pensare è stata l'implementazione di array associativi (ma poi ancora, Java non ha array associativi). Potresti per favore un esperto versare i tuoi pensieri su questa domanda?

Answer 1

Risposta breve:

sarebbe un array di array (o liste).

Object[][] map; 

dove map[bucketIndex] sarebbe restituire il 'secchiello'.

Quando si inserisce qualcosa, è necessario utilizzare una funzione per calcolare bucketIndex utilizzando lo hashcode dell'oggetto inserito.

Braccio fatto!

:)

Answer 2

Guarda Cliff Clicca del nonblockinghahmap per un esempio di una necessità di una HashMap implementato in Java. Ricorda che un array associato è solo un altro nome per una mappa hash, quindi ti chiede come implementarlo.

Generalmente gli hash sono implementati utilizzando matrici standard (non elenchi o di qualcosa di speciale per la velocità). Il problema è che cosa c'è all'interno di ognuno di questi array ... nel caso di una collisione hash, si desidera utilizzare una LinkedList (concatenazione) o si desidera eseguire il rehash e passare a un'altra posizione dell'array (indirizzo aperto). Leggi un po 'di informatica per scoprire il rapporto costo/beneficio per entrambi.

Answer 3

È necessario utilizzare un array dimensionale. Oggetto [] arr.

L'indice della matrice è la hashcode normalizzata dall'oggetto chiave. La matrice contiene la coppia.

Il motivo per cui il valore è costituito da Chiave e Valore è che se c'è una collisione di hash, deve passare attraverso l'elenco di chiavi all'interno dello slot e scoprire qual è la chiave corretta (usando equals sull'oggetto chiave).

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 articolo spiega molto bene HashMap e altre collezioni. Dare un'occhiata.

Creare una classe che funge da mappatura nella mappa

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; 
    } 
} 

E la classe mappa che utilizzerà le voci

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

Riferimenti: - 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()); 
    } 


}