public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private SequentialSearchST<Key, Value>[] st;
//构造函数, 使用INIT_CAPACITY传入有参构造函数, 实际上这个数字就是数组的长度
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
//创建长度为m的链表数组
public SeparateChainingHashST(int m) {
this.m = m;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
//哈希函数, 除以m取余数
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
//取键值, 先找到对应的数组的索引, 再从链表中符号表中取出key
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
int i = hash(key);
return st[i].get(key);
}
//存入的时候同样先计算hash, 找到对应的链表, 再进行存储
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
//这里其实要调整数组的长度了, 目前可以先忽略
if (n >= 10*m) resize(2*m);
//计算hash值, 找到对应的链表, 然后存入值.
int i = hash(key);
if (!st[i].contains(key)) n++;
st[i].put(key, val);
}
}
public class LinearProbingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
//键值对总数
private int n;
//数组的长度, 两个数组一个存放键一个存放值
private int m;
private Key[] keys;
private Value[] vals;
//构造函数, 使用INIT_CAPACITY作为数组初始的长度
public LinearProbingHashST() {
this(INIT_CAPACITY);
}
public LinearProbingHashST(int capacity) {
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
}
//插入函数
public void put(Key key, Value val) {
//依然是先判断键和值为空的情况
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
//如果已插入键值对的数量超过了数组长度的一半, 就扩充一倍的数组
if (n >= m/2) resize(2*m);
int i;
//计算键的hash值, 然后开始搜索直到null的位置.
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
如果发现了键, 就更新值
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
//循环结束之后如果没找到, 则i停留在null的位置, 将当前键值插入的两个数组的i索引处
keys[i] = key;
vals[i] = val;
n++;
}
//查询函数
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
//与插入类似, 一样的循环, 在找到null之前如果找到了, 就返回对应的值
for (int i = hash(key); keys[i] != null; i = (i + 1) % m)
if (keys[i].equals(key))
return vals[i];
//for循环结束之后说明没找到, 返回null, 表明不存在该键
return null;
}
//删除函数
public void delete(Key key) {
//检测键是否为空和是否存在
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
if (!contains(key)) return;
//先找到对应的i索引
int i = hash(key);
while (!key.equals(keys[i])) {
i = (i + 1) % m;
}
//将两个数组对应的索引设置为空
keys[i] = null;
vals[i] = null;
//这一步操作很关键, 由于设置了为null, 就是一个搜索终点, 其后的元素如果不调整位置, 就不会被找到
i = (i + 1) % m;
//从i+1的位置向后不断寻找
while (keys[i] != null) {
//用临时变量保存键和值, 然后设置当前位置为null, 数量也减少1, 然后重新插入这个键
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
//这个n--是删除要删除的元素的操作, 放到了最后, 在所有其后的元素重新插入完成之后, 再将总键值数量减少1
n--;
//删除之后也记得要调整大小
if (n > 0 && n <= m/8) resize(m/2);
assert check();
}
//所有键的队列实现, 比较简单, 挨个将不是null的Key放入Queue中, 返回这个Queue即可.
//由于Queue实现了迭代器, 所以可以对返回的Queue使用增强for循环
public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++)
if (keys[i] != null) queue.enqueue(keys[i]);
return queue;
}
}
