散列表查找算法
步骤：
- 用散列函数将被查找的键转化成数组索引
- 处理碰撞冲突
有两种常见的碰撞处理的方法，分别是链地址法和线性探测法。
1 链地址法
链地址法：将大小为M的数组中的每个元素指向一条结点类型的链表，链表中保存散列值为该元素的索引的键值对。
在一张含有M条链表和N个键的散列表中，未命中查找和插入操作需要的比较次数为~N/M。
算法实现：
private int hash(Key key) { //散列return (key.hashCode() & 0x7fffffff)%M;
}
public Value get(Key key) { //查询return (Value) st[hash(key)].get(key); //这里调用了链表的get()方法
}
public void put(Key key,Value val) { //插入st[hash(key)].put(key, val); //这里调用了链表的插入方法
}
public void delete(Key key) { //删除if (key == null) throw new IllegalArgumentException("argument to delete() is null");int i = hash(key);if (st[i].contains(key)) N--;st[i].delete(key); //这里调用了链表的删除方法
}其中调用了链表的get()、put()、delete()方法。
散列表的大小问题：目标是既不会因为空链表太多而浪费大量内存，也不会因为链表太长而在查询方面耗费太长时间。可以动态调整数组大小以保持短小的链表。
2 线性探查法
当碰撞发生时，直接检测散列表中的下一位置。这样线性探测可能发生三种结果：
- 命中--该位置的键和被查找的键相同
- 未命中--键为空（该位置没有键）
- 继续查找--该位置的键和被查找的键不同
开放地址类的散列表的核心思想是与其将其内存用作链表，不如将它们作为散列表中的空元素。这些空元素可以作为查找结束的标志。
算法实现：
查询和插入：
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之间。