我正在开发一个使用开放寻址和线性探测的哈希表。我正在使用标准函数，例如获取、插入和删除。我的问题是，虽然这些函数对于较小的哈希表工作得很好，但当哈希表变大时，它似乎会出错。 size() 不会返回正确的值，get() 也不会。我非常感谢任何有关我如何解决这些问题的意见。
public class SymbolTable {
private static final int INIT_CAPACITY = 7;
/* Number of key-value pairs in the symbol table */
private int N;
/* Size of linear probing table */
private int M;
/* The keys */
private String[] keys;
/* The values */
private Character[] vals;
/**
* Create an empty hash table - use 7 as default size
*/
public SymbolTable() {
this(INIT_CAPACITY);
}
/**
* Create linear probing hash table of given capacity
*/
public SymbolTable(int capacity) {
N = 0;
M = capacity;
keys = new String[M];
vals = new Character[M];
}
/**
* Return the number of key-value pairs in the symbol table
*/
public int size() {
return N;
}
/**
* Is the symbol table empty?
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Does a key-value pair with the given key exist in the symbol table?
*/
public boolean contains(String key) {
return get(key) != null;
}
/**
* Hash function for keys - returns value between 0 and M-1
*/
public int hash(String key) {
int i;
int v = 0;
for (i = 0; i < key.length(); i++) {
v += key.charAt(i);
}
return v % M;
}
/**
* Insert the key-value pair into the symbol table
*/
public void put(String key, Character val) {
int z = hash(key);
if(keys[z] == null){ //Ökar endast om platsen redan är null. lösning för att omplaceringarna från delete inte ska öka värdet
N++;
// System.out.println("stlk "+N);
}
if(key.equals(keys[z])){
vals[z]= val;
}
else
if (keys[z]!=null){
if(z == M -1){
z = 0;
}
for (int i = z; i < M; i++){
if (keys[z]!=null){
if(i == M - 1){
if(keys[i] == null){
z=i;
N++;
// System.out.println("strlk " + N);
break;
}else{
i=0;
}
}}
if(key.equals(keys[i])){
vals[i]= val;
break;
}
if(keys[i] == null){
z = i;
N++;
// System.out.println("stlk "+N);
break;
}
}
}
keys[z]=key;
vals[z]=val;
}
// dummy code
/**
* Return the value associated with the given key, null if no such value
*/
public Character get(String key) {
int index = hash(key);
while (keys[index] != null && !keys[index].equals(key)) {
index++;
if (index == M) {
index = 0;
}
}
return vals[index];
} // dummy code
/**
* Delete the key (and associated value) from the symbol table
*/
public void delete(String key) {
if (keys[hash(key)] != null){ //Kollar så att strängen faktiskt finns, så att den inte deletar pga. HASHVÄRDET av strängen finns
if(key.equals(keys[hash(key)])){
keys[hash(key)] = null;
vals[hash(key)] = null;
N --;
for (int i = 0; i < M; i++){
if(keys[i] != null && hash(keys[i]) != i){
N--;
// System.out.println("strlk "+N);
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
}}
} else {
for (int i = 0; i < M; i++){
if(keys[i] != null && hash(keys[i]) != i){
N--;
// System.out.println("strlk "+N);
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
}
if(key.equals(keys[i])){
keys[hash(key)] = null;
N --;
}
}
}
}
}
// dummy code
/**
* Print the contents of the symbol table
*/
// dummy code
/**
* Print the contents of the symbol table
*/
public void dump() {
String str = "";
for (int i = 0; i < M; i++) {
str = str + i + ". " + vals[i];
if (keys[i] != null) {
str = str + " " + keys[i] + " (";
str = str + hash(keys[i]) + ")";
} else {
str = str + " -";
}
System.out.println(str);
str = "";
}
}
}
这是用来运行它的测试程序。
import java.io.*;
public class SymbolTableTest2 {
public static void main(final String[] args){
final SymbolTable st = new SymbolTable(733);
final int nums = 730;
final int gap = 37;
final char[] tests = new char[nums];
int i;
System.out.println("Checking... (no more output means success)");
// Associate i (as a string) with a random printable character
for (i = gap; i != 0; i = (i + gap) % nums) {
final char ch = (char) (32 + (int) (Math.random() * ((127 - 32) + 1)));
st.put(Integer.toString(i), ch);
tests[i] = ch;
}
// Check that size() is correct
if (st.size() != nums - 1) {
System.out.println("size was() " + st.size()
+ ", should have been " + (nums - 1));
}
// Delete some entries
for (i = 1; i < nums; i += 2) {
st.delete(Integer.toString(i));
}
// Check that size is correct
if (st.size() != ((nums / 2) - 1)) {
System.out.println("size was() " + st.size()
+ ", should have been " + ((nums / 2) - 1));
}
// Delete same entries again
for (i = 1; i < nums; i += 2) {
st.delete(Integer.toString(i));
}
// Check that size is correct
if (st.size() != ((nums / 2) - 1)) {
System.out.println("size was() " + st.size()
+ ", should have been " + ((nums / 2) - 1));
}
// Check that correct entries are still in table
for (i = 2; i < nums; i += 2) {
if (st.get(Integer.toString(i)) == null
|| st.get(Integer.toString(i)) != tests[i]) {
System.out.println("get(" + i + ") was "
+ st.get(Integer.toString(i))
+ ", should have been " + tests[i]);
}
}
// Check that deleted entries really were deleted
for (i = 1; i < nums; i += 2) {
if (st.get(Integer.toString(i)) != null) {
System.out.println("get(" + i + ") was "
+ st.get(Integer.toString(i))
+ ", should have been null");
}
}
}}
最佳答案
您的删除方法错误。
以下代码片段显示了问题:
SymbolTable st = new SymbolTable(733);
st.put("12", 'A');
st.put("21", 'B');
st.put("13", 'C');
st.remove("13");
运行此代码后，st 将包含两个键“12”和“13”，而不是“12”和“21”。
一个问题是 put 方法:如果您的键已经在哈希表中，但不在键哈希码标识的位置，则执行(大约在 put 方法中的第 27 行)
if(key.equals(keys[i])){
vals[i]= val;
break;
}
后跟(在 put 方法的末尾)
keys[z]=key;
vals[z]=val;
它会覆盖其他一些随 secret 钥。
<小时/>第二个问题出现在 delete 方法中。您尝试删除并重新插入所有元素。
但是，
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
将删除该元素。如果两个元素具有相同的哈希码，则很容易发生这种情况。
关于java - 为什么我的哈希表不能在更大的范围内工作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52353454/