我得到了一个带有泛型类型(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;
}
1条答案
按热度按时间7gcisfzg1#
代码与描述不匹配。也就是说,您正在调整循环中数组的大小,除非循环中的第一个元素
entries
是成功的(即null
或者等于钥匙)。需要在循环之后调整数组大小(加上修复循环条件检查):
… 我 假设您知道这是一个非常低效的map实现:每次搜索和插入都要进行o(n)次尝试。实际上,您可以使用哈希表或某种搜索树来加速插入和查找。