Как реализовать связанный список с помощью HashMap в java

Question

Как создать связанный список с помощью HashMap в java? Я искал в Интернете, есть реализации с использованием структуры данных LinkedList. Интервьюер попросил меня реализовать его без использования структуры данных LinkedList, я пытался использовать HashTable, но в конце он сказал, что должен был сделать это с помощью HashMap.

Большое вам спасибо за ответы.

Я сделал это после прочтения ваших комментариев:

public class hashMap { 
    static Map<Integer, Integer> mMap = new HashMap<Integer, Integer>(); 

     public static void main(String[] args) { 
     int a; 

     mMap.put(1, 2); 
     mMap.put(2, 3); 
     mMap.put(3, 4); 
     mMap.put(4, 7); 
     mMap.put(7, 8); 

     Scanner in = new Scanner(System.in); 
     System.out.println("Enter: "); 
     a = in.nextInt(); 

      itera(); 

        if(mMap.containsKey(a)) { 
       add.insert(a); 

      } 
       else if (!mMap.containsKey(a)) { 
       add.remove(a); 

      } 

     itera(); 
    } 

    public static void itera() { 
     for (Iterator<Integer> iter = (Iterator<Integer>) mMap.keySet().iterator(); iter.hasNext();) { 

      int key = iter.next(); 
      int sa = mMap.get(key); 
      System.out.println(key + " : " + sa); 
     } 

    } 
    static class add { 
    public static void insert(int a) { 
     int s = a-1; 
     int newKey = s; 
     int sa = mMap.get(a); 
     mMap.put(newKey, sa); 
     mMap.remove(a); 
    } 

    public static void remove(int a) { 
     int newa = a; 
     while(!mMap.containsKey(a)) { 
      a--; 
      System.out.println("while a: " + a); 

     } 

     mMap.put(newa, mMap.get(a)); 

     mMap.put(a, newa); 

    } 
} 


} 

Он просто вставляет и удаляет узлы в Linked List. Но есть проблемы, если некоторые ключи отсутствуют, например, 5 & 6 нет в ключах. Поэтому, если я попытаюсь вставить 6, это не сработает. Может ли кто-нибудь объяснить, что я делаю неправильно?

Answer 1

Глупые вопросы интервью.

Проще всего я могу думать о том, чтобы хранить «индекс» для каждого значения в ключе и значение как значение, ну, значение.

Имейте внешне поддерживать индекс головы и хвоста, но это не удивительно.

Add будет выглядеть следующим образом:

public void add(V value) { 
    _map.put(_tail, value); 
    _tail += 1; 
} 

Снимите:

public boolean remove(V value) { 
    Iterator<Map.Entry<Integer,V>> _map.entrySet().iterator(); 
    while(iter.hasNext()) { 
     Map.Entry<Integer,V> entry = iter.next(); 
     if(value.equals(entry.getValue())) { 
      iter.remove(); 
      return true; 
     } 
    } 
    return false; 
} 

Оставьте остальные в качестве упражнения для читателя.

Answer 2

Я пытался использовать HashTable, но в конце он сказал, что должен был сделать это с помощью HashMap.

HashTable старый Java 1.0 класс, который имеет несколько нежелательных свойств:

• Все операции синхронизированный ... которые, как правило, нет необходимости
• Класс не позволяет null клавиш или значения ... который HashMap.

Кроме того (и тот факт, что HashTable поддерживает старый Enumeration API) HashMap и HashTable ведут себя в значительной степени то же самое. Общеизвестно, что неплохо использовать HashTable ... если вы не работаете над кодовой базой/платформой, на самом деле требует.

Таким образом, интервьюер указывает (правильно), что вы использовали устаревший класс для (возможно) без уважительной причины. По электронной почте Ой!

---

Но если он специально не говорил вам, чтобы сделать это, реализуя связанный список, используя хэш-таблицу любого рода довольно плохая идея.

• Это неясное
• Это излишне сложное
• Это неэффективен
• Это наводит на мысль, что ваше понимание структур данных и алгоритмов является слабым.

Простой связанный список легко реализовать с нуля в простой Java. Это то, что вы должны были сделать.

Гораздо больше Ooops !!!