定义
散列表通过算术操作将键转化为数组的索引来访问数组中的键值对。散列表的查找算法分两步：
- 用散列函数将被查找的键转化为一个数组的索引
- 处理碰撞冲突（拉链法和线性探测法）
优点：常数级别的查找和插入操作
缺点：无法进行有序性相关的操作
散列函数
正整数：将整数散列最常用的方法是除留余数法，选择大小为素数M的数组，对于任意正整数k,计算k除以M的余数
hashCode返回值：将默认的hashCode方法和除留余数法结合起来产生一个0到M-1的整数。通过符号位屏蔽，将一个32位的整数变成一个31位的非负整数。如果直接取余，结果可能是一个负数；如果取绝对值，最大整数可能会返回一个负数。
private int hash(Key x) {
return (x.hashCode() & 0x7fffffff) % M;
}
基于拉链法的散列表
将数组中的每个元素指向一个链表，链表中的每个结点都存储了散列值为该元素索引的键值对。发生冲突时，将冲突的元素存到链表当中。
基于拉链法的散列表示意图
代码实现
package edu.princeton.cs.algs4.chapter3;
/**
* 基于拉链法的散列表
* Created by tianxianhu on 2017/3/14.
*/
public class SeparateChainingHashST<Key, Value> {
private int N; //键值对的总数
private int M; //散列表的大小
private SequentialSearchST<Key, Value>[] st; // 存放链表对象的数组
public SeparateChainingHashST() { this(997); }
public SeparateChainingHashST(int M) {
// 创建M条链表
this.M = M;
st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
// 对每一个链表初始化
for (int i = 0; i < M; i++) {
st[i] = new SequentialSearchST();
}
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key) {
return (Value) st[hash(key)].get(key);
}
public void put(Key key, Value value) {
st[hash(key)].put(key,value);
}
public void delete(Key key) {
st[hash(key)].delete(key);
}
}
基于线性探测法的散列表
线性探测法是使用大小为M的数组保存N个键值对，其中M > N。当发生线性碰撞的时候，直接检查散列表中的下一个位置（将索引值加1）
代码实现
package edu.princeton.cs.algs4.chapter3;
/**
* 基于线性探测的符号表
* Created by tianxianhu on 2017/3/14.
*/
public class LinearProbingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n; // 符号表中键值对的总数
private int m; // 线性探测表的大小
private Key[] keys; // 键
private Value[] vals; // 值
public LinearProbingHashST() {
this(INIT_CAPACITY);
}
public LinearProbingHashST(int capacity) {
m = capacity;
n = 0;
keys = (Key[]) new Object[m];
vals = (Value[]) new Object[m];
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
private void resize(int cap) {
LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(cap);
for (int i = 0; i < m; i++) {
if (keys[i] != null) {
temp.put(keys[i], vals[i]);
}
}
keys = temp.keys;
vals = temp.vals;
m = temp.m;
}
public void put (Key key, Value val) {
// 超过一半，将数组长度翻倍
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 Value get (Key key) {
int i;
// 探测
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key)) {
return vals[i];
}
}
// 没有改键，返回空
return null;
}
public boolean contains(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to contains() is null");
return get(key) != null;
}
// 删除指定键，并将簇中被删除键的右侧的所有键重新插入散列表中
public void delete(Key key) {
if (!contains(key))
return;
int i = hash(key);
// 找到键所在的时机位置，然后删除
while (!keys[i].equals(key)) {
i = (i + 1) % m;
}
keys[i] = null;
vals[i] = null;
// 将该元素后面的键值对全部重新插入
i = (i + 1) % m;
while (keys[i] != null) {
Key keyToRedo = keys[i];
Value valueToRedo = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRedo, valueToRedo);
i = (i + 1) % m;
}
n--;
if (n > 0 && n == m/8)
resize(m / 2);
}
}
所有符号表实现的效率总结
符号表实现的时间复杂度
