作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
当元素数量 N 大于 m/2(m 是数组的初始大小)时,我尝试调整数组大小,但它不起作用,我不明白为什么。这个数组应该像哈希表一样工作,所以我在每次插入之前都有一个哈希函数,在调整大小之后我想再次插入具有新哈希值的每个元素(m 值已更改)。这是错误:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at JumpHashing.resize(JumpHashing.java:55)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
at JumpHashing.hashing(JumpHashing.java:40)
at JumpHashing.resize(JumpHashing.java:61)
at JumpHashing.put(JumpHashing.java:50)
问题显然是调整大小,没有它(元素少于 23 个)它也能工作。
m 的初始大小为 23,这是实际代码(用于从 algs4 读取文件的“In”类):
public class JumpHashing{
private int m;
private int[] hashTable;
private static int id;
private int N;
public JumpHashing(){
m = 23;
hashTable = new int[m];
N = 0;
}
public void hashing(int value) {
int key = (value*11)%m;
put(key, value);
}
public void put(int key, int value) {
if(N <m/2) {
hashTable[key] = value;
N++;
} else {
m=m*2;
N=0;
resize(m);
}
}
public void resize(int m) {
int[] temp = new int[m];
for(int i=0; i<hashTable.length; i++) {
temp[i] = hashTable[i];
}
hashTable = new int[m];
for(int i=0; i<temp.length; i++) {
hashing(temp[i]);
}
}
public static void main(String[] args) {
JumpHashing hashT1 = new JumpHashing();
In file = new In("random.txt");
while(file.hasNextLine()) {
int value = Integer.parseInt(file.readLine());
hashT1.hashing(value);
}
for(int j=0; j<hashT1.hashTable.length; j++) {
StdOut.println("Key: "+j+" Value: "+hashT1.hashTable[j]);
}
}
}
最佳答案
您最终会重复调用resize
,直到内存用完。问题出在这个函数上:
public void resize(int m) {
int[] temp = new int[m]; // <-- this is the new double-size of m
for(int i=0; i<hashTable.length; i++) {
temp[i] = hashTable[i];
}
hashTable = new int[m];
for(int i=0; i<temp.length; i++) { // <-- here we go too far
hashing(temp[i]);
}
}
您的第二个循环将遍历全新的“m”大小数组,而不是原始的 m/2 大小数组。在循环中加一,您的 N
将再次大于 m/2
,并且每次发生这种情况时都会调用 resize。
以下是该函数中应该包含的内容:
public void resize(int m) {
int[] oldHash = hashTable;
hashTable = new int[m];
for(int i=0; i<oldHash.length; i++) {
if (oldHash[i] != 0) { // <-- don't hash empty slots
hashing(oldHash[i]);
}
}
}
这也提高了性能,因为您只循环一次且不超过 m/2 次。
关于java - 当元素超过其大小的 1/2 时调整数组大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61576570/
我是一名优秀的程序员,十分优秀!