HashTable 基于链表地址法

功能上于前面两个HashTable（－） ，HashTable（二） 一致，但实现上采用的链表表示每个Hash桶的位置，这样理论上不用考虑容量问题。实际中HashTable中的每个SortLink太长会导致效率低下，因此HashTable的初始大小比较重要。

链表使用的是有序链表SortLink，这样查找，删除的效率会提高一半，但是新增则会从O(1)降到链表的平均长度的一半。考虑链表不是太长，所以不会对效率产生太大的影响。但终究来说，这种实现更适合查询，不适合大量反复的插入。

关于可以插入的数据的键值，此处假设为整数。

代码中有许多辅助类

其中：

Item：装载有key（关键值）的数据

Node：单向链表的节点

SortLink：单向单端有序链表

HashTable：Hash表

其中SortLink,HashTable中的print方法纯粹是为了测试使用。

HashTable.main提供测试方法

class Item {
    private int key;
    private Object value;
   
    public Item(int key, Object value) {
        this.key = key;
        this.value = value;
    }

    public int key() { return key; }
    public Object value()  { return value; }
}

class Node {
    private Item item;
    private Node next;

    public Node(Item item) {
        this.item = item;
    }
   
    public Item item() {
        return item;
    }

    public void next(Node next) {
        this.next = next;
    }

    public Node next() {
        return next;
    }
}

class SortLink {
    private Node first;
    public void add(Item item) {
        Node node = new Node(item);
           
        Node previous = null;
        Node current = first;
        while(current != null && current.item().key() < item.key()) {
            previous = current;
            current = current.next();
        }
        node.next(current);
        if (previous == null) first = node;
        else previous.next(node);
    }

    public Item remove(int key) {
        if(first ==  null) return null;
        Node previous = null;
        Node current = first;
        while(current != null && current.item().key() < key) {
            previous = current;
            current = current.next();
        }
        if(current != null && current.item().key() == key) {
            Item result = current.item();
            if(previous == null) first = current.next();
            else previous.next(current.next());
            return result;
        }
        return null;
    }

    public Item find(int key) {
        if(first == null) return null;
        Node current = first;
        while(current != null && current.item().key() < key) 
            current = current.next();
        if(current != null && current.item().key() == key) return current.item();
        else return null;
    }

    //测试专用
    void print() {
        Node current = first;
        while(current != null) {
            System.out.print(current.item().key() + ",");
            current = current.next();
        }
        System.out.println();
    }
}

class HashTable {
    private SortLink[] array;
    HashTable(int size) {
        array = new SortLink[size];
    }
    private int getHash(int key) {
        return key % array.length;
    }
    public void add(Item item) {
        int pos = getHash(item.key());
        if(array[pos] == null) array[pos] = new SortLink();
        array[pos].add(item);
    }

    public Item remove(int key) {
        int pos = getHash(key);
        if(array[pos] == null)return null;
        else return array[pos].remove(key);
    }

    public Item find(int key) {
        int pos = getHash(key);
        if(array[pos] == null)return null;
        else return array[pos].find(key);
    }

    //测试专用
    public void print() {
        for(int i=0; i<array.length; i++) {
            if(array[i] != null) array[i].print();
        }
    }
    public static void main(String[] args) {
        HashTable t = new HashTable(5);
        t.add(new Item(1,"hello"));
        t.add(new Item(6,"world"));
        t.add(new Item(11,"temp"));
        t.add(new Item(3,"jason"));
        t.add(new Item(104,"orange"));
        t.add(new Item(9,"peter"));
        t.print();

        System.out.println("====================");

        assert t.find(6).value().equals("world");
        assert t.find(11).value().equals("temp");
        assert t.find(104).value().equals("orange");
        assert t.find(9).value().equals("peter");
        assert t.find(87) == null;
        assert t.remove(3).value().equals("jason");
        assert t.find(3) ==  null;
        assert t.remove(6).value().equals("world");
        assert t.find(6) ==  null;
        t.print();
        System.out.println("====================");
       
        t.add(new Item(6,"temp"));
        assert t.find(6).value().equals("temp");
        t.print();
        System.out.println("==== OK ===");
    }
}