▶ 书中第三章部分程序，加上自己补充的代码，包括散列表、线性探查表
● 散列表
package package01; import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.SequentialSearchST;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key, Value>
{
private static final int INIT_CAPACITY = 4; // 默认构造函数参数
private int n; // 待插入元素数
private int m; // 散列表尺寸
private SequentialSearchST<Key, Value>[] st; // 散列表 public class01()
{
this(INIT_CAPACITY);
} public class01(int capacity)
{
m = capacity;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} private void resize(int capacity)
{
class01<Key, Value> temp = new class01<Key, Value>(capacity);
for (int i = 0; i < m; i++)
{
for (Key key : st[i].keys())
temp.put(key, st[i].get(key));
}
m = temp.m;
n = temp.n;
st = temp.st;
} public boolean contains(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % m;
} public Value get(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
return st[hash(key)].get(key);
} public void put(Key key, Value val)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
if (val == null)
{
delete(key);
return;
}
if (n >= 10 * m) // 平均链表长度不小于 10，扩容
resize(2 * m);
int i = hash(key);
if (!st[i].contains(key))
n++;
st[i].put(key, val);
} public void delete(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
if (!contains(key))
return;
int i = hash(key);
if (st[i].contains(key))
n--;
st[i].delete(key);
if (m > INIT_CAPACITY && n <= 2 * m) // 平均链表长度小于 2，缩容
resize(m / 2);
} public Iterable<Key> keys()
{
Queue<Key> queue = new Queue<Key>();
for (int i = 0; i < m; i++)
{
for (Key key : st[i].keys())
queue.enqueue(key);
}
return queue;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}
● 线性探查表
package package01; import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key, Value>
{
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private Key[] keys;
private Value[] vals; public class01()
{
this(INIT_CAPACITY);
} public class01(int capacity)
{
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} private void resize(int capacity)
{
class01<Key, Value> temp = new class01<Key, Value>(capacity);
for (int i = 0; i < m; i++)
{
if (keys[i] != null)
temp.put(keys[i], vals[i]);
}
m = temp.m;
keys = temp.keys;
vals = temp.vals; } public boolean contains(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % m;
} public Value get(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) // 表荷载不会超过 1/2，所以不会绕圈
{
if (keys[i].equals(key))
return vals[i];
}
return null;
} public void put(Key key, Value val)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
if (val == null)
{
delete(key);
return;
}
if (n >= m / 2) // 荷载超过一半了，扩容
resize(2 * m);
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 void delete(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
if (!contains(key))
return;
int i = hash(key);
for (; !key.equals(keys[i]); i = (i + 1) % m); // 找到目标元素
keys[i] = null; // 删除目标元素
vals[i] = null;
for (i = (i + 1) % m; keys[i] != null; i = (i + 1) % m) // 在下一个 null 之前，所有元素重新插入
{
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
}
n--;
if (n > 0 && n <= m / 8) // 荷载小于 1/8， 缩容
resize(m / 2);
} 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;
}
private boolean check()
{
if (m < 2 * n) // 检查容量
{
System.err.println("\n<check> m < 2 * n.\n");
return false;
}
for (int i = 0; i < m; i++) // 检查 hash
{
if (keys[i] == null)
continue;
if (get(keys[i]) != vals[i])
{
System.err.println("\n<check> hash error at i = ", i, ", key[i] = ", get(keys[i]), ", val[i] = ", vals[i], ".\n");
return false;
}
}
return true;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}