1. 用散列函数将被查找的键转化为数组的一个索引
  2. 处理碰撞冲突：拉链法和线性探测法

3.4.1　散列函数

3.4.1.2　正整数

除留余数法(k%M，M是素数)

3.4.1.3　浮点数

将键表示为二进制数然后再使用除留余数法

3.4.1.4　字符串

除留余数法也可以处理较长的键，例如字符串，我们只需将它们当作大整数即可

1
2
3

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;//R进制值

3.4.1.5　组合键

如果键的类型含有多个整型变量，我们可以和 String 类型一样将它们混合起来

3.4.1.6　Java 的约定

hashCode() 方法必须和 equals() 方法一致

3.4.1.7　将 hashCode() 的返回值转化为一个数组索引

将默认的 hashCode() 方法和除留余数法结合起来产生一个0到M-1的整数

1
2

private int hash(Key x)
{ return (x.hashCode() & 0x7fffffff) % M; }//将符号位屏蔽（将一个 32 位整数变为一个 31 位非负整数）

3.4.1.8　自定义的 hashCode() 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class Transaction
{
    ...
    private final String who;
    private final Date when;
    private final double amount;
    public int hashCode()
    {
        int hash = 17;
        hash = 31 * hash + who.hashCode();
        hash = 31 * hash + when.hashCode();
        hash = 31 * hash + ((Double) amount).hashCode();
        return hash;
    }
    ...
}

3.4.1.9　软缓存

每个键的散列值缓存起来

3.4.2　基于拉链法的散列表

将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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 val){ st[hash(key)].put(key, val); }
    public Iterable<Key> keys()
}

3.4.3　基于线性探测法的散列表

用大小为M的数组保存N个键值对，其中M>N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。开放地址散列表中最简单的方法叫做线性探测法：当碰撞发生时（当一个键的散列值已经被另一个不同的键占用），我们直接检查散列表中的下一个位置（将索引值加 1）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

public class LinearProbingHashST<Key, Value>
{
    private int N; // 符号表中键值对的总数
    private int M = 16; // 线性探测表的大小
    private Key[] keys; // 键
    private Value[] vals; // 值
    public LinearProbingHashST()
    {
        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> 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;
    }
    public void put(Key key, Value val)
    {
        if (N >= M/2) resize(2*M); // 将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)
    {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key)) 
                return vals[i];
        return 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 keyToRedo = keys[i];
            Value valToRedo = vals[i];
            keys[i] = null;
            vals[i] = null;
            N--;
            put(keyToRedo, valToRedo);
            i = (i + 1) % M;
        }
        N--;
        if (N > 0 && N == M/8) resize(M/2);
    }
}