还有一种散列表实现方式称为线性探测法
当碰撞发生时候,我们优先检查散列表中下一个位置(索引值+1)
利用一个M大的数组保存N个键值,其中M>N,依靠数组中的空位解决碰撞问题.
这样在插入的时候可能会出现三种结果
命中 键相同
未命中 键为空
查找中发现该位置的键和寻找的键不同
如果是不同,继续查找,直到达到尾部(将数组增大,或者折回开头)
这里我们将检测一个数组位置是否含有被查找的键称为探测
查找方式基本总结为,先查找对应位置是否为空,如果不为空,那么判断是否相同,相同返回
不然向后,直到找到
如下图所示
public void put(Key key,Value val) {//加入
if (N>M/2) {//动态调整
resize(M*2);
}
int i ;
for (i = hash(key); keys[i]!= null; i=(i+1)%M) {//最后一步让其循环
if (keys[i].equals(key)) {//已存在,且相同
vals[i] = val;
return ;
}
}
keys[i] = key;
vals[i] = val;
N++;
}
public Value get(Key key) {
for (int i = hash(key); keys[i]!= null; i=(i+1)%M) {
if (keys[i].equals(key)) {//已存在,且相同
return vals[i];
}
}
return null;
}
对应的删除如下
public void delete(Key key) {
if (!contains(key)) {//如果不存在
return;
}
int i = hash(key);
while (!key.equals(keys[i])) {//不等于
i = (i + 1) % M;//就前进
}
keys[i] = null;
vals[i] = null;
i = (i + 1) % M;//向前一格
while (keys[i] != null) {//直到下一个空格,
//这一步因为前面的让我们删除了,所以会自动向前一格
Key keytemp = keys[i];
Value valtemp = vals[i];
N–;
put(keytemp, valtemp);
i = (i + 1) % M;
}
N–;
if (N > 0 && N == M / 8) {
resize(M / 2);
}//动态调整
}
最后给出当时的课后讨论,一个关于放置的平均值
对于线性探测法,调整数组的大小是有必要的,如果插入的键值超过预期的时候他的查找时间会变得极其长
而且会在散列表被填满的时候进入无限循环