java线性探测法myhash
时间: 2023-11-21 21:58:54 浏览: 36
根据提供的引用内容,我们可以了解到线性探测法是散列表中的一种解决冲突的方法,但是容易造成元素聚集,导致元素无法均匀存入表中,增加了运算的复杂度。因此,我们可以使用平方探测法来解决这个问题。
以下是Java中平方探测法实现散列表的代码示例:
```java
public class MyHash {
private DataItem[] hashArray;
private int arraySize;
private DataItem nonItem;
public MyHash(int size) {
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1);
}
public void displayTable() {
System.out.print("Table: ");
for (int j = 0; j < arraySize; j++) {
if (hashArray[j] != null) {
System.out.print(hashArray[j].getKey() + " ");
} else {
System.out.print("** ");
}
}
System.out.println(""); }
public int hashFunc(int key) {
return key % arraySize;
}
public void insert(DataItem item) {
int key = item.getKey();
int hashVal = hashFunc(key);
int stepSize = 1;
while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
hashVal += stepSize * stepSize;
hashVal %= arraySize;
stepSize++;
}
hashArray[hashVal] = item;
}
public DataItem delete(int key) {
int hashVal = hashFunc(key);
int stepSize = 1;
while (hashArray[hashVal] != null) {
if (hashArray[hashVal].getKey() == key) {
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
return temp;
}
hashVal += stepSize * stepSize;
hashVal %= arraySize;
stepSize++;
}
return null;
}
public DataItem find(int key) {
int hashVal = hashFunc(key);
int stepSize = 1;
while (hashArray[hashVal] != null) {
if (hashArray[hashVal].getKey() == key) {
return hashArray[hashVal];
}
hashVal += stepSize * stepSize;
hashVal %= arraySize;
stepSize++;
}
return null;
}
}
class DataItem {
private int iData;
public DataItem(int ii) {
iData = ii;
}
public int getKey() {
return iData;
}
}
```
以上代码实现了平方探测法的散列表,其中包括插入、删除和查找操作。在插入操作中,我们使用平方探测法来解决冲突,即每次增加的步长为1的平方,直到找到空的位置为止。在删除和查找操作中,我们也使用相同的探测方式来查找对应的元素。