如何在java中使用HashMap实现链表

How can I create linked list using HashMap in java? I searched online, there are implementations using LinkedList data structure. Interviewer asked me to implement it without using LinkedList data structure, I tried to do with HashTable but at the end he said I should have done it using HashMap.

如何在java中使用HashMap创建链表?我在网上搜索,有使用LinkedList数据结构的实现。面试官让我在不使用LinkedList数据结构的情况下实现它,我试着用HashTable做,但最后他说我应该用HashMap完成它。

Thank you so much for answers.

非常感谢你的回答。

I have done this after reading your comments:

我在阅读你的评论后这样做了:

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

    }
}


}

It just inserts and deletes nodes into Linked List. But there is problem if some keys are missing, like 5 & 6 is not there in keys. So if I try to insert 6, it doesn't work. Could anyone explain what am I doing wrong?

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

2 个解决方案

#1

I tried to do with HashTable but at the end he said I should have done it using HashMap.

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

HashTable is an old Java 1.0 class that has a couple of undesirable properties:

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

All operations are synchronized ... which is typically unnecessary

所有操作都是同步的......这通常是不必要的

The class doesn't allow null keys or values ... which HashMap does.

该类不允许使用空键或值... HashMap执行此操作。

Apart from that (and the fact that HashTable supports the old Enumeration API) HashMap and HashTable behave pretty much the same. It is common knowledge that it is a bad idea to use HashTable ... unless you are working on a codebase / platform that actually requires it.

除此之外(以及HashTable支持旧的Enumeration API的事实)HashMap和HashTable的行为几乎相同。众所周知,使用HashTable是个坏主意......除非您正在开发实际需要它的代码库/平台。

So the interviewer is pointing out (correctly) that you used an out-of-date class for (probably) no good reason. Ooops!

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

But unless he specifically told you to do this, implementing a linked list using a hash table of any kind is a pretty bad idea.

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

It is obscure

这是模糊不清的

It is unnecessarily complicated

这是不必要的复杂

It is inefficient

效率低下

It strongly suggests that your understanding of data structures and algorithms is weak.

它强烈表明您对数据结构和算法的理解很薄弱。

A simple linked list is easy to implement from scratch in plain Java. That's what you should have done.

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

Much bigger Ooops!!!

更大的哎呀!

#2

Stupid interview questions.

愚蠢的面试问题。

Easiest way I can think of is to store the "index" for each value in the key and the value as the, well, value.

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

Have to externally maintain the head and tail index but that is not too surprising.

必须从外部保持头尾指数,但这并不太令人惊讶。

Add will then look like:

添加将看起来像:

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

Remove:

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

Leave the rest as an exercise for the reader.

剩下的作为练习给读者。

#1