java—为Map/关联数组数据结构实现put(或add)方法

s71maibg  于 2021-06-29  发布在  Java
关注(0)|答案(1)|浏览(316)

我得到了一个带有泛型类型(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);
                 */
            }
        }
    }

除了注解掉的部分,我需要用数组的正确位置替换[…]。即:
如果Map中索引i处的项<k,v>为null,或者索引i处的项的键等于传递的键,则用包含传递的键和值的新项替换该项,然后完成该方法。
如果找不到这样一个条目<k,v>,则调用该方法的map(它是表单条目<k,v>[])的数组)应全部复制,其数组大小应加倍(使用辅助方法genericarrayhelper.copyArrayWithinIncreasedSize)。接着,在复制并调整大小的数组的第一个空槽处,放入一个带有传递的键和值的新条目。
这就是混乱产生的地方。我试过用各种指数来代替[…],但一直没有得到满意的结果。
当我尝试输入以下几个条目时,putinide是一个Map:

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

在打印时,我将得到以下结果(“stringized”使用单独的tostring方法):

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

但是,当我使用entries.length-1的数组索引来表示[…],这是我经过几个小时的尝试后得到的最接近的索引,并且观察调试器时,它看起来非常糟糕:

前三个条目是正确的,但其他三个被混为一谈。。。当我打印整个内容时,我只得到第一个树条目的输出,因为其他三个条目似乎被完全忽略了(也许是因为for循环中较大的数组仅仅是在循环本身中定义的?)
我的问题是:如何为索引[…]定义一个合适的替换项,或者,也许也是为了更好地理解:究竟为什么我们需要首先将数组的大小增加一倍?我以前从未实现过任何java集合数据结构,也没有在uni上过data structures类……如何获得“加倍”的输出?
任何形式的帮助都将不胜感激!
编辑:为了让事情更清楚,下面是tostring方法:

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

使用keysasset()返回Map的哈希集,该哈希集仅包含键,而不包含值。

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

7gcisfzg1#

代码与描述不匹配。也就是说,您正在调整循环中数组的大小,除非循环中的第一个元素 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);
}

… 我 假设您知道这是一个非常低效的map实现:每次搜索和插入都要进行o(n)次尝试。实际上,您可以使用哈希表或某种搜索树来加速插入和查找。

相关问题