0

我正在使用 HashMaps 处理这个数据结构分配。对于这个任务，我将“用一个使用墓碑条目的新方法替换删除方法。你的删除方法应该用这个替换要删除的项目。你需要修改其他方法来处理数组不同。换句话说，墓碑条目表明集群中没有中断。在这个项目中，教授提供了一个名为“可用”的墓碑。我的工作是将该墓碑用于删除方法并更改我已有的其他方法。问题是我不知道墓碑是什么或如何实现它。有人可以向我解释什么是墓碑以及我将如何实现它吗？

import java.util.Scanner;

public class HashMapLPD<Key, Value> {
    private class Item<Key, Value> {
        Key key;
        Value value;

        public Item(Key key, Value value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "(" + key + ", " + value + ")";
        }
    }

    int size;
    final static int INITIAL_SIZE = 4;
    private Item<Key, Value>[] h;
    final Item<Key, Value> AVAILABLE = new Item<>(null, null);

    public HashMapLPD() {
        this(INITIAL_SIZE);
    }

    @SuppressWarnings("unchecked")
    public HashMapLPD(int size) {
        h = new Item[size];
    }

    public Value delete(Key key) {
        int hashCode = key.hashCode();
        int index = hashCode % h.length;

        Value valueToReturn = null;

        while (h[index] != null)
            if (h[index].key.equals(key)) {
                valueToReturn = h[index].value;
                h[index] = null;
                --size;

                while (h[++index] != null) {
                    Item<Key, Value> itemToRehash = h[index];
                    h[index] = null;
                    put(itemToRehash.key, itemToRehash.value);
                    --size;
                }
            } else
                index = index + 1 % h.length;

        return valueToReturn;
    }

    public void put(Key key, Value value) {
        if (size >= h.length / 2)
            resize(2 * h.length);

        int hashCode = key.hashCode();
        int index = hashCode % h.length;

        while (h[index] != null && !h[index].key.equals(key))
            index = (index + 1) % h.length;

        h[index] = new Item<Key, Value>(key, value);
        ++size;
    }

    private void resize(int newSize) {
        HashMapLPD<Key, Value> tmp = new HashMapLPD<>(newSize);

        for (Item<Key, Value> item : h)
            if (item != null)
                tmp.put(item.key, item.value);

        h = tmp.h;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        HashMapLPD<Integer, String> st = new HashMapLPD<>();

        while (true) {
            System.out.println("1. Add");
            System.out.println("2. Get");
            System.out.println("3. Delete");
            System.out.println("4. Print");

            switch (input.nextInt()) {
            case 1:
                System.out.println("Enter Integer key and String value");
                st.put(input.nextInt(), input.nextLine());
                break;
            case 3:
                System.out.println("Enter Integer key to be deleted");
                System.out.println(st.delete(input.nextInt()));
                break;
            case 4:
                System.out.println(st);
                break;
            }
        }
    }
}
4

0 回答 0