八、Java数据结构-符号表(Map)

什么是符号表

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

• 我们使用符号表这个词来描述一张抽象的表格，我们会将信息(值)存储在其中，然后按照指定的键来搜索并获取这些信息。

• 符号表有时也被称为字典。键就是单词，值就是单词对应的定义，发音和词源。

• 符号表有时又叫做索引。键就是术语，值就是书中该术语出现的所有页码。

在实现前，我们遵循以下规则：

1. 每个键只对应一个值；
2. 当向表中存入的键值对和表中的已有的键冲突时，新的值会替代旧的值。
3. 键不能为空
4. 根据键值有小到大排序插入

代码实现（通过双向链表来实现）

public class MySymbolTable<Key extends Comparable<Key>,Value> implements Iterable<Key>{
    Node head ;
    int N;

    public MySymbolTable(){
        this.head = new Node(null, null, null);
        this.N = 0;
    }


    private class Node{

        public Key key ;
        public Value val;
        public Node next;

        public Node(Key key ,Value val,Node next){
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public  boolean isEmpty(){
        return this.N == 0;
    }

    public int size(){
        return this.N;
    }

    public Value get(Key key){
        Node n = this.head;
        while (n.next!=null){
            n = n.next;
            if(n.key.equals(key)){
                return n.val;
            }
        }
        System.out.println("没有找到你要的数据");
        return null;
    }
    public void put(Key key,Value val){
        Node n = this.head;
        Node pre = this.head;
        while (n.next!=null ){
            pre = n;
            n = n.next;
            if(n.key.equals(key)){
                n.val = val;
                return;
            }else if(n.key.compareTo(key)>0){
                System.out.println(n.key.compareTo(key) + "");
                pre.next = new Node(key,val,n);
                this.N ++ ;
                return;
            }
        }
        n.next = new Node(key,val,null);
        this.N ++ ;
    }

    public void delete(Key key){
        Node n = this.head;
        while (n.next!=null){
            if(n.next.key.equals(key)){
                n.next = n.next.next;
                this.N --;
                return;
            }
            n = n.next;
        }
    }

    @Override
    public Iterator<Key> iterator() {
        return new MyIterator();
    }
    private class MyIterator implements Iterator<Key>{
        Node n = head;
        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Key next() {
            n=n.next;
            return n.key;
        }
    }
}