查找----基于散列表（线性探测法）
参照数据结构--符号表API实现。
除了拉链法，实现散列表的另一种方式就是用大小为M的数组保存N个键值对。
线性探测法：当碰撞发生时，直接检测散列表中的下一位置。这样线性探测可能发生三种结果：
- 命中--该位置的键和被查找的键相同
- 未命中--键为空（该位置没有键）
- 继续查找--该位置的键和被查找的键不同
开放地址类的散列表的核心思想是与其将其内存用作链表，不如将它们作为散列表中的空元素。这些空元素可以作为查找结束的标志。
使用两个平行数组来保存键值对。
线性探测法的核心方法如下：
private int hash(Key key) { //散列
return (key.hashCode()&0x7fffffff)%M;
}
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 put(Key key,Value val) { //插入方法
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++;
}线性探测法的删除操作：
不能直接将找到的位置设为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 keyTo = keys[i];
Value valTo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
//重新插入
put(keyTo,valTo);
i = (i+1)%M;
}
N--;
}调整数组大小：
private void resize(int cap) {
//创建一个更大的数组
LinearProbingHashST<Key,Value> t;
t = new LinearProbingHashST<Key,Value>(cap);
//将当前数组中的数据写入新数组
for(int i=0;i<M;i++)
if(keys[i]!=null)
t.put(keys[i], vals[i]);
keys = t.keys;
vals = t.vals;
M = t.M;
}当散列表快满时查找所需的探测次数是巨大的，但当使用率在1/2时探测次数只在1.5和2.5之间。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读