0

如何在 java 中使用 HashMap 创建链表？我在网上搜索，有使用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);

    }
}


}

它只是将节点插入和删除到链接列表中。但是如果缺少某些键就会出现问题，例如键中没有 5 和 6。因此，如果我尝试插入 6，它就不起作用。谁能解释我做错了什么？

4

2 回答 2

4

我尝试使用 HashTable，但最后他说我应该使用 HashMap 来完成。

HashTable是一个旧的 Java 1.0 类，它有几个不受欢迎的属性：

  • 所有操作都是同步的……这通常是不必要的
  • 该类不允许null键或值...HashMap确实如此。

HashTable除此之外（以及支持旧EnumerationAPI的事实）HashMap并且HashTable行为几乎相同。众所周知，使用HashTable... 是一个坏主意，除非您在实际需要它的代码库/平台上工作。

因此，面试官（正确地）指出您（可能）没有充分的理由使用过时的课程。哎呀！

但是除非他明确告诉你这样做，否则使用任何类型的哈希表来实现链表都是一个非常糟糕的主意。

  • 晦涩难懂
  • 这是不必要的复杂
  • 效率低下
  • 这强烈表明你对数据结构和算法的理解很薄弱。

一个简单的链表很容易在纯 Java 中从头开始实现。那是你应该做的。

更大的哎呀！！！

于 2013-05-20T02:04:32.143 回答
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;
}

剩下的留给读者练习。

于 2013-05-20T02:00:59.087 回答