java - 为 Map/Associative Array 数据结构实现 put（或 add）方法

问题描述

我得到一个带有通用类型 (K,V) 的 Map 数据结构，其中 K 代表键，V 代表值。

现在我被要求实现经典的put(K key, V value)方法，该方法随集合一起提供。该方法是预先实现的，并从所使用的接口覆盖一个：

@Override
    public void put(K key, V value) {
        for (int i = 0; i <= this.entries.length; i++) {
            if (this.entries[i] == null || this.entries[i].getKey().equals(key)) {
                this.entries[i] = new Entry<K, V>(key, value);
                return;
            } else {
                this.entries = GenericArrayHelper.copyArrayWithIncreasedSize(this.entries, (this.entries.length) * 2);
                /*  replace [...]
                this.entries[...] = new Entry<K, V>(key, value);
                 */
            }
        }
    }

除了被注释掉的部分，我需要用数组的正确位置替换 [...] 。即：

如果映射中索引 i 处的 Entry<K,V> 为空，或者索引 i 处的条目的键等于传递的键，则将该条目替换为包含传递的键和值的新条目，并完成该方法。

如果找不到这样的 Entry<K,V>，则应完整复制调用该方法的映射（其形式为 entries<K,V>[ ] 的数组），其数组大小应为加倍（使用辅助方法GenericArrayHelper.copyArrayWithIncreasedSize）。随后，在复制和调整大小的数组的第一个空槽处，使用传递的键和值放入一个新条目。

这就是产生混乱的地方。我试图用各种索引替换 [...]，但从未得到令人满意的结果。

当我尝试输入这几个条目时，putInside是一个 Map：

putInside.put("sizeInMB", 42);
putInside.put("version", 4);
putInside.put("yearOfRelease", 2015);

打印时（使用单独的 toString 方法“字符串化”），我将得到以下结果：

yearOfRelease : 2015
sizeInMB : 42
version : 4
yearOfRelease : 2015
sizeInMB : 42
version : 4

但是当我说，使用entry.length-1的数组索引来表示 [...]，这是我经过数小时的尝试后最接近的，并观察调试器，它看起来很糟糕：

前三个条目是正确的，但其他三个被混搭了......当我打印整个内容时，我只得到第一个树条目的输出，因为其他三个似乎完全被忽略了（也许是因为较大的for 循环中的数组仅在循环本身中定义？）

我的问题是：我如何为索引 [...] 定义一个合适的替代品，或者，也许也是为了更好地理解：为什么我们首先需要将数组的大小加倍？我以前从未实现过任何 Java Collection 数据结构，也没有在我的大学学习过数据结构类...... 我如何获得“双倍”输出？

任何形式的帮助都会非常感激！

编辑：为了让事情更清楚，这里是 toString 方法：

public static void toString(Map<String, Integer> print) {
        for(String key : print.keysAsSet()){
                System.out.println(key + ": " + print.getValueFor(key));
        }
    }

使用keysAsSet()返回 Map 的 HashSet，其中仅包含键，但不包含值。

public Set<K> keysAsSet() {
        HashSet<K> current = new HashSet<>();
        for(Entry<K,V> entry : entries){
            if(entry != null) {
                current.add(entry.getKey());
            }
        }
        return current;
    }

标签： javaarraysdictionarycollections

代码与描述不符。也就是说，您正在调整循环内的数组大小，除非其中的第一个元素entries是命中（即它是null或它等于键）。

您需要在循环之后调整数组大小（加上修复循环条件检查）：

@Override
public void put(K key, V value) {
    int oldLength = this.entries.length;
    for (int i = 0; i < oldLength; i++) {
        if (this.entries[i] == null || this.entries[i].getKey().equals(key)) {
            this.entries[i] = new Entry<K, V>(key, value);
            return;
        }
    }
    this.entries = GenericArrayHelper.copyArrayWithIncreasedSize(this.entries, oldLength * 2);
    this.entries[oldLength] = new Entry<K, V>(key, value);
}

…我假设你知道这是一个非常低效的地图实现：每次搜索和插入都需要O ( n ) 次尝试。实际上，您可以使用哈希表或某种搜索树来加速插入和查找。

java - 为 Map/Associative Array 数据结构实现 put（或 add）方法

问题描述

解决方案

推荐阅读