Mise en œuvre HashMap personnalisée

Question

Cette question m'a été posée lors d'une interview. Je pense que la seule façon d'obtenir la meilleure solution est SOF. Donc, la question était "Comment voulez-vous implémenter un HashMap personnalisé dans Java (Supposons qu'il n'y a pas une telle structure de données appelée HashMap)". La seule réponse que je pouvais penser était en mettant en œuvre des tableaux associatifs (mais encore une fois, Java n'a pas de tableaux associatifs). Pourriez-vous experts s'il vous plaît verser dans vos pensées sur cette question?

Answer 1

Réponse courte:

Ce serait un tableau de tableaux (ou listes).

Object[][] map; 

où map[bucketIndex] renverrait le 'compartiment'. Lors de l'insertion de quelque chose, vous avez besoin d'une fonction pour calculer bucketIndex cela utilisera le hashcode de l'objet inséré.

Boom fait!

:)

Answer 2

Regardez Cliff Cliquez de nonblockinghahmap pour un exemple de la nécessité d'un hashmap implémenté en Java. Rappelez-vous qu'un tableau associé est juste un autre nom pour une carte de hachage, donc il vous demande comment l'implémenter.

En général, les hachages sont implémentés en utilisant des tableaux standard (pas des listes ou quelque chose de fantaisie pour la vitesse). Le problème est de savoir ce qu'il y a à l'intérieur de chacun de ces tableaux ... dans le cas d'une collision de hachage, voulez-vous utiliser LinkedList (chaînage) ou voulez-vous ressasser et aller à un autre emplacement de tableau (adressage ouvert). Lire un peu plus d'informatique pour apprendre le coût/avantage de faire les deux.

Answer 3

Vous devez utiliser un tableau à une dimension. Objet [] arr.

L'index du tableau est le hashcode normalisé de l'objet Key. Le tableau contient la paire. La raison pour laquelle la valeur consiste à la fois en Clé et en Valeur est que s'il y a une collision, elle doit passer par la liste des clés à l'intérieur de la fente et trouver la bonne clé (en utilisant l'objet clé).

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 article explique très bien HashMap et d'autres collections. Regarde.

Créer une classe qui fait office de cartographie sur la carte

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

Et la classe carte qui utilisera les entrées

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

Références: - 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()); 
    } 


}