线性探针是第二种解决哈希冲突的办法。这样的办法的基本思想就是当遇到哈希冲突时，寻找下一个空位，直到找到空位为止。
演示样例
先插入一个值S，例如以下图。
插入其它的一些值，这些值的哈系没有冲突，得到下图的结果。
再插入一个值H，因为H与A的哈系冲突，因此须要寻找一个空的位置。
找到了空位
插入
代码
public class LinearProbeST<Key, Value> {private static final int M = 100;private Key[] keys = (Key[])new Object[M];private Value[] values = (Value[])new Object[M];public LinearProbeST() {}public Value get(Key key) {int hash = hash(key);for(int i=0; i < M; i++) {int index = (hash + i) % M;Key key2 = keys[index];// 找不到该键if(key2 == null) return null;// 找到了该键if(key.equals(key2)) {return values[index];}}return null;}public void put(Key key, Value value) {int hash = hash(key);for(int i=0; i < M; i++) {int index = (hash+i) % M;Key key2 = keys[index];// 找到了空位if(key2 == null) {keys[index] = key;values[index] = value;return;}// 找到了已经存在的值if(key.equals(key2)) {values[index] = value;return;}}}private int hash(Key key) {return (key.hashCode() & 0x7fffffff) % M;}
}性能
随着数据量的添加，因为冲突的哈希值添加因此速度会越来越慢。在冲突非常少的情况下，每一个操作的复杂度近似为1。在冲突非常多的情况下，每一个操作的复杂度可达到N。所以一般取M=N/2，这样性能最佳，又不浪费空间。
Knuth停车问题
有一个固定大小的停车场，每辆车都会在随机的位置i停下，假设停车位i已经被占用了，那么寻找停车位i+1、i+2等。
线性探针算法事实上就是Knuth停车问题。http://arxiv.org/abs/math/0502220