2013-05-20 121 views
-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,它不起作用。任何人都可以解释我做错了什么?

+0

没有什么可以解释的:'HashMap'是新的'HashTable' :) – dasblinkenlight

+1

我不知道你为什么使用Hashtable,或者甚至如何。他应该进入这方面而不是挑选集合班。 – EJP

+0

@ user2142511。将它作为类并添加插入和删除方法。发布该课程。并将其存储在另一个地方的对象来了.u可以在关键字,对象对中使用它,或者使用具有键值的另一个hashmap。插入将变得简单和快速,获取也将变得简单和快速,导致链接列表将使用索引。在中间插入也是高成本的。你必须插入然后更新其他键的索引。参见https://en.wikipedia.org/wiki/Linked_list加快搜索该方法的利弊搜索部分 – qwr

回答

0

愚蠢的面试问题。

我能想到的最简单的方法是将每个值的“索引”存储在关键字中,并将值存储为值,即值。

必须在外部维护头部和尾部索引,但这并不令人感到意外。然后

添加的样子:

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

离开其余作为练习留给读者。

+0

remove方法不会正确删除值。假设底层地图包含条目(a,b)和(b,c)。通过删除值'b',这些条目应该减少到(a,c),但是在你的代码中它们被减少到(b,c)。 –

+0

关键是一个整数不是其中的一个值。对于包含“a”,“b”和“c”的“列表”,地图将包含键/值(1,'a'),(2,'b'),(3,'c')。在移除('b')时,代码移除元组(2,'b')。代码不会“填充”由可能或可能不需要的删除所创建的空白。 –

+0

对不起,我看到你的代码现在是如何工作的。但那将是一个随机访问列表,而不是一个链表。 –

2

我试着用HashTable做,但最后他说我应该用HashMap来完成它。

HashTable是具有一对不希望的性质的一个老的Java类1.0:

  • 所有操作是同步...这通常是不必要的
  • 类不允许null键或价值......其中HashMap做。

除此之外,(和HashTable支持旧的API Enumeration的事实)HashMapHashTable表现几乎相同。众所周知,使用HashTable是一个糟糕的主意......除非您正在研究的代码库/平台实际上是需要它。

所以面试官指出(正确)你使用过时的课程(可能)没有好的理由。哎呀!


但是,除非他明确地告诉你这样做,如果采用任何形式的哈希表是一个非常糟糕的主意链表。

  • 它是不起眼的
  • 这是不必要的复杂
  • 这是一种低效
  • 它有力地表明,你的数据结构和算法的理解是薄弱。

简单的链接列表很容易在纯Java中从头开始实现。这就是你应该做的。

更大Ooops !!!