请用Java实现一个40行以内的简单线性探测法
时间: 2024-01-24 16:04:47 浏览: 20
好的,以下是一个40行以内的简单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; }
public boolean containsKey(Key key) { return get(key) != null; }
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;
}
}
```
这个实现与之前的实现基本相同,只是将一些方法的定义放在同一行内。不过这个实现没有包含一些必要的注释,所以可能不太容易阅读。