概述

散列表（Hash table，也叫哈希表、符号表）是根据关键码值（Key Value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

无序符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。（键值对）符号表中，键具有唯一性。

API设计

结点类
类名：Node<Key,Value>
构造方法：Node(Key key,Value value,Node next)：创建Node对象
成员变量
	public Key key：存储键
	public Value value：存储值
	public Node next：存储下一个结点

符号表
类名：SymbolTable<Key, Value>
构造方法：SymbolTable()：创建SymbolTable对象
成员方法
	public Value get(Key key)：根据键key，找对应的值
	public void put(Key key,Value val)：向符号表中插入一个键值对
	public void delete(Key key)：删除键为key的键值对
	public int size()：获取符号表的大小
成员变量
	private Node head：记录首结点
	private int n：记录符号表中键值对的个数

代码实现

//无序符号表
public class SymbolTable<K,V> {

    //记录首结点
    private Node head;
    //记录符号表中键值对的个数
    private int n;

    public SymbolTable() {
        //初始化
        head = new Node(null,null,null);
        n = 0;
    }

    //根据键key，找对应的值
    public V get(K key) {
        Node node = head;
        // 遍历，取出key
        while (node.next != null) {
            node = node.next;
            if (node.key.equals(key)) {
                // 找到了
                return (V) node.value;
            }
        }
        return null;
    }

    // 向符号表中插入一个键值对
    // 如果key不存在，返回null
    // 如果key存在，返回旧的value
    public V put(K key,V value) {
        //先从符号表中查找键为key的键值对
        Node node = head;
        while (node.next != null) {
            node = node.next;
            if (node.key.equals(key)) {
                //说明代插入的key已经存在，直接替换value
                //取出旧的value
                Object oldValue = node.value;
                node.value = value;
                return (V) oldValue;
            }
        }
        //循环完毕没有结束，说明key在表中不存在
        Node oldFirst = head.next;
        //创建一个新结点，头插法，每一个新的结点都在第一个元素的位置
        Node<K, V> newFirst = new Node<>(key, value, oldFirst);
        head.next = newFirst;
        //个数+1
        n++;
        return null;
    }

    // 删除键位key的键值对，并将删除的值给返回
    public V delete(K key) {
        // 遍历符号表，找出要删除的key
        Node node = head;
        while (node.next != null) {
            if (node.next.key.equals(key)) {
                // 说明找到了key，删除下一个节点
                Object value = node.next.value;
                node.next = node.next.next;
                // 个数-1
                n--;
                return (V) value;
            }
            // 每次遍历，都将node的下一个节点赋值给node
            node = node.next;
        }
        return null;
    }

    //获取符号表的大小
    public int size() {
        return n;
    }

    private class Node<K,V> {
        public K key;
        public V value;
        //下一个结点
        public Node next;
        public Node(K key,V value,Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

符号表的操作方式和HashMap相似，但是HashMap和符号表是两回事，HashMap的实现方式是数组+链表（JDK8之后引入了红黑树）。

有序符号表

在实际生活中，有时候我们需要根据键的大小进行排序，插入数据时要考虑顺序。

此时需要修改put()方法即可。

// 向符号表中插入一个键值对
// 如果key不存在，返回null
// 如果key存在，返回旧的value
public String put(Integer key, String value) {
    // 记录当前节点
    Node currentNode = head.next;
    // 记录上一个节点
    Node pre = head;
    // 如果key大于当前节点的key，则一直找到下一个结点
    while (currentNode != null && key > currentNode.key) {
    // 把currentNode记录给上一个节点
        pre = currentNode;
        currentNode = currentNode.next;
    }
    // 到这里，就遍历到了我们想要的位置
    // 如果当前结点currentNode的key和将要插入的key一样，则替换
    if (currentNode != null && key.equals(currentNode.key)) {
        String tempV = currentNode.value;
        currentNode.value = value;
        return tempV;
    }
    // key不相等，把新的结点插入到currentNode之前。
    Node newNode = new Node(key, value, currentNode);
    pre.next = newNode;
    return null;
}