请用Java实现一个简单的线性探测法
时间: 2024-01-24 09:04:12 浏览: 22
好的,以下是一个简单的Java实现线性探测法的示例代码:
```java
public class LinearProbingHashMap<Key, Value> {
private int size; // 符号表中键值对的数量
private int capacity; // 线性探测表的大小
private Key[] keys; // 键数组
private Value[] values; // 值数组
// 构造函数
public LinearProbingHashMap(int capacity) {
this.capacity = capacity;
size = 0;
keys = (Key[]) new Object[capacity];
values = (Value[]) new Object[capacity];
}
// 获取键值对数量
public int size() {
return size;
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 判断是否包含key
public boolean containsKey(Key key) {
return get(key) != null;
}
// 获取value
public Value get(Key key) {
for (int i = hash(key); keys[i] != null; i = (i + 1) % capacity) {
if (keys[i].equals(key)) {
return values[i];
}
}
return null;
}
// 添加键值对
public void put(Key key, Value value) {
if (size >= capacity * 0.5) {
resize(capacity * 2);
}
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % capacity) {
if (keys[i].equals(key)) {
values[i] = value;
return;
}
}
keys[i] = key;
values[i] = value;
size++;
}
// 删除键值对
public void remove(Key key) {
if (!containsKey(key)) {
return;
}
int i = hash(key);
while (!key.equals(keys[i])) {
i = (i + 1) % capacity;
}
keys[i] = null;
values[i] = null;
i = (i + 1) % capacity;
while (keys[i] != null) {
Key tempKey = keys[i];
Value tempValue = values[i];
keys[i] = null;
values[i] = null;
size--;
put(tempKey, tempValue);
i = (i + 1) % capacity;
}
size--;
if (size > 0 && size <= capacity * 0.25) {
resize(capacity / 2);
}
}
// 计算散列值
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % capacity;
}
// 重新调整表的大小
private void resize(int newCapacity) {
LinearProbingHashMap<Key, Value> temp = new LinearProbingHashMap<>(newCapacity);
for (int i = 0; i < capacity; i++) {
if (keys[i] != null) {
temp.put(keys[i], values[i]);
}
}
keys = temp.keys;
values = temp.values;
capacity = temp.capacity;
}
}
```
这里我们实现了一个基于线性探测法的哈希表数据结构,它支持添加、删除、查询、判断是否包含某个键等基本操作。