散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的 数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 散列函数，存放记录的 数组叫做 散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

使用拉链法处理碰撞

    使用不同的碰撞处理方式，我们便得到了散列表的不同实现。首先我们要介绍的是使用拉链法来处理碰撞的散列表的实现。以这种方式实现的散列表，每个桶里都存放了一个链表。初始时所有链表均为空，当一个键被散列到一个桶时，这个键就成为相应桶中链表的首结点，之后若再有一个键被散列到这个桶（即发生碰撞），第二个键就会成为链表的第二个结点，以此类推。这样一来，当桶数为M，散列表中存储的键值对数目为N时，平均每个桶中的链表包含的结点数为N / M。因此，当我们查找一个键时，首先通过散列函数确定它所在的桶，这一步所需时间为O(1)；然后我们依次比较桶中结点的键与给定键，若相等则找到了指定键值对，这一步所需时间为O(N / M)。所以查找操作所需的时间为O(N / M)，而通常我们都能够保证N是M的常数倍，所以散列表的查找操作的时间复杂度为O(1)，同理我们也可以得到插入操作的复杂度也为O(1)。

    理解了以上的描述，实现基于拉链法的散列表也就很容易了，这里简单起见，我们直接使用前面的SeqSearchList作为桶中的链表，参考代码如下：

public class ChainingHashMap<K, V> { private int num; //当前散列表中的键值对总数 private int capacity; //桶数 private SeqSearchST<K, V>[] st; //链表对象数组 public ChainingHashMap(int initialCapacity) { capacity = initialCapacity; st = (SeqSearchST<K, V>[]) new Object[capacity];//java不允许泛型的数组 for (int i = 0; i < capacity; i++) { st[i] = new SeqSearchST<>(); } } private int hash(K key) { return (key.hashCode() & 0x7fffffff) % capacity; } public V get(K key) { return st[hash(key)].get(key); } public void put(K key, V value) { st[hash(key)].put(key, value); } } 以上代码中还用到了SeqSearchST，实际上这就是一个基于链表的符号表实现，支持向其中添加key-value pair，查找指定键时使用的是顺序查找，它的代码如下： public class SeqSearchST<K, V> { private Node first; private class Node { K key; V val; Node next; public Node(K key, V val, Node next) { this.key = key; this.val = val; this.next = next; } } public V get(K key) { for (Node node = first; node != null; node = node.next) { if (key.equals(node.key)) { return node.val; } } return null; } public void put(K key, V val) { //先查找表中是否已存在相应key Node node; for (node = first; node != null; node = node.next) { if (key.equals(node.key)) { node.val = val; return; } } //表中不存在相应key first = new Node(key, val, first); } }