如何在java中使用HashMap實現鏈接列表

-1

如何在java中使用HashMap創建鏈接列表？我在網上搜索，有使用LinkedList數據結構的實現。 Interviewer要求我在不使用LinkedList數據結構的情況下實現它，我嘗試着使用HashTable，但最終他說我應該使用HashMap來完成它。如何在java中使用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); 

    } 
} 


}

它只是插入和刪除節點到鏈表。但是如果某些鍵丟失，就會出現問題，例如5 & 6在鍵中不存在。所以如果我嘗試插入6，它不起作用。任何人都可以解釋我做錯了什麼？

來源

2013-05-20 Mayur

沒有什麼可以解釋的：'HashMap'是新的'HashTable' :) – dasblinkenlight

我不知道你爲什麼使用Hashtable，或者甚至如何。他應該進入這方面而不是挑選集合班。 – EJP

@ user2142511。將它作爲類並添加插入和刪除方法。發佈該課程。並將其存儲在另一個地方的對象來了.u可以在關鍵字，對象對中使用它，或者使用具有鍵值的另一個hashmap。插入將變得簡單和快速，獲取也將變得簡單和快速，導致鏈接列表將使用索引。在中間插入也是高成本的。你必須插入然後更新其他鍵的索引。參見https://en.wikipedia.org/wiki/Linked_list加快搜索該方法的利弊搜索部分 – qwr

愚蠢的面試問題。

我能想到的最簡單的方法是將每個值的「索引」存儲在關鍵字中，並將值存儲爲值，即值。

必須在外部維護頭部和尾部索引，但這並不令人感到意外。然後

添加的樣子：

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

離開其餘作爲練習留給讀者。

來源

2013-05-20 02:00:59

remove方法不會正確刪除值。假設底層地圖包含條目（a，b）和（b，c）。通過刪除值'b'，這些條目應該減少到（a，c），但是在你的代碼中它們被減少到（b，c）。 –

關鍵是一個整數不是其中的一個值。對於包含「a」，「b」和「c」的「列表」，地圖將包含鍵/值（1，'a'），（2，'b'），（3，'c'）。在移除（'b'）時，代碼移除元組（2，'b'）。代碼不會「填充」由可能或可能不需要的刪除所創建的空白。 –

對不起，我看到你的代碼現在是如何工作的。但那將是一個隨機訪問列表，而不是一個鏈表。 –

我試着用HashTable做，但最後他說我應該用HashMap來完成它。

HashTable是具有一對不希望的性質的一個老的Java類1.0：

所有操作是同步...這通常是不必要的
類不允許null鍵或價值......其中HashMap做。

除此之外，（和HashTable支持舊的API Enumeration的事實）HashMap和HashTable表現幾乎相同。衆所周知，使用HashTable是一個糟糕的主意......除非您正在研究的代碼庫/平臺實際上是需要它。

所以面試官指出（正確）你使用過時的課程（可能）沒有好的理由。哎呀！

但是，除非他明確地告訴你這樣做，如果採用任何形式的哈希表是一個非常糟糕的主意鏈表。

它是不起眼的
這是不必要的複雜
這是一種低效
它有力地表明，你的數據結構和算法的理解是薄弱。

簡單的鏈接列表很容易在純Java中從頭開始實現。這就是你應該做的。

更大Ooops !!!

來源

2013-05-20 02:04:32

如何在java中使用HashMap實現鏈接列表

回答

相關問題