java - 使用并行数组编写简单的 String hashMap。重新散列后获取某些键的空值
问题描述
我第一次在put
方法中遇到冲突,即当hasKey
返回方法开始并且触发冲突-1
的rehashing
值变为双倍数组到可能的空槽时。但是System.out.println(m.get("1000"));
给我一些键的空值,这意味着它们丢失了。我不明白它们是如何丢失的,因为在keyArray
.
import java.util.*;
public class StringMapParallel implements Iterable<String>{
private int nButckets = 2000;
private String[] keyArray = new String[nButckets];
private String[] valueArray = new String[nButckets];
private int numberOfEntries = 0;
public static void main(String[] args) {
StringMapParallel m = new StringMapParallel();
;
for (int i = 0; i < 8000; i++) {
m.put(String.valueOf(i), String.valueOf(i));
}
System.out.println(m.get("1000"));
}
private void rehashing() {
if (numberOfEntries > (int) (0.3 * nButckets)) {
int newBucketsNumber = nButckets * 2;
String[] newKeyArray = new String[newBucketsNumber];
String[] newValueArray = new String[newBucketsNumber];
for (int i = 0; i < keyArray.length; i++) {
if (keyArray[i] != null) {
int index = keyArray[i].hashCode() % newBucketsNumber;
newKeyArray[index] = keyArray[i];
newValueArray[index] = valueArray[keyArray[i].hashCode() % nButckets];
}
}
/*
for (String key: this) {
int index = key.hashCode() % newBucketsNumber;
newKeyArray[index] = key;
if (key == null) System.out.println(key);
newValueArray[index] = valueArray[key.hashCode() % nButckets];
}
*/
keyArray = newKeyArray;
valueArray = newValueArray;
nButckets = newBucketsNumber;
}
}
public void put(String key, String value) {
int index = key.hashCode() % nButckets;
int hasKey = hasKey(index, key);
if (hasKey == 1) {
valueArray[index] = value;
} else if (hasKey == 0){
keyArray[index] = key;
valueArray[index] = value;
numberOfEntries++;
} else {
rehashing();
index = key.hashCode() % nButckets;
keyArray[index] = key;
valueArray[index] = value;
numberOfEntries++;
}
}
public String get(String key) {
int index = key.hashCode() % nButckets;
if (hasKey(index, key) == 1) return valueArray[index];
return null;
}
private int hasKey(int index, String key) {
if (keyArray[index] == null) {
return 0;
} else if (keyArray[index].equals(key)) {
return 1;
} else {
return -1;
}
}
public Iterator<String> iterator(){
Iterator<String> iter = new Iterator<String>() {
private int currentIndex = 0;
private int nEntries = 0;
@Override
public boolean hasNext() {
return nEntries < numberOfEntries && numberOfEntries != 0;
}
@Override
public String next() {
for (int i = currentIndex; i < keyArray.length; i++) {
if (keyArray[i] != null) {
currentIndex = i + 1;
nEntries++;
return keyArray[i];
}
}
return null;
}
};
return iter;
}
}
解决方案
int index = key.hashCode() % nButckets;
您的算法中 key1000
和的值6357
是相同的,即1423
. 因此,您的算法keyArray[1423]=1000
用keyArray[1423]=6357
当您打印m.get(String.valueOf(1000))
时,以下get()
方法会检查index
以及key
,因此它会返回null
。阅读代码中的注释以获得进一步的解释。
public String get(String key) {
//System.out.println(key+" "+ key.hashCode());
int index = key.hashCode() % nButckets;
System.out.println(index+"bfb"+hasKey(index, key));
//hasKey(index, key) would return -1, because key[1423] is 6357, and not 1000 as you expected.
if (hasKey(index, key) == 1) return valueArray[index];
return null;
}
private int hasKey(int index, String key) {
//System.out.println(keyArray[index]);
if (keyArray[index] == null) {
return 0;
} else if (keyArray[index].equals(key)) {
return 1;
} else {
return -1;
}
}
推荐阅读
- android - 如何自行安装 APK 修复错误解析 APK?
- excel - 如何计算vba中的最大回撤?
- c++ - 程序未按应有的方式运行。很多关于局部变量的警告
- c# - ClickOnce 无法从 .NET BrowserControl 启动
- go - USB Amory Mk-II - ATECC608A:AES 命令 (I²C)
- go - 当字段值字符串解组为 []byte 时会发生什么
- php - 如何使用 php 从 musicbrainz api 艺术家搜索中提取分数
- python - TypeError:'int'对象在python中不是可调用错误
- vue.js - 在 Vue 中比较两个不同的数据对象同时减少
- raspberry-pi - Supercollider 不再适用于 Raspberry Pi