【容器】链式表(LinkedList)与哈希映射(HashMap) - 《Java 网络编程》

手写HashMap

一、链表的基本实现
定义节点类

package LinkList;
/**
 * 定义Node类（节点）
 * @author DaluxC
 *
 */
public class Node {
    //上一节点
    private Node previous;
    //当前结点的内容
    private Object sth;
    //下一节点
    private Node next;
    public Node getPrevious() {
        return previous;
    }
    public void setPrevious(Node previous) {
        this.previous = previous;
    }
    public Object getSth() {
        return sth;
    }
    public void setSth(Object sth) {
        this.sth = sth;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

实现链表容器

package LinkList;
/**
 * 实现链表容器
 * @author DaluxC
 *
 */
public class TestLinklist {
    private Node first;                 //定义首节点
    private Node last;                  //定义末节点
    private int size;                   //记量链表的长度
    //遍历链表的方法，输入你要遍历到第几个节点
    public Node Ergodic(int index) {
        aragecheck(index);
        Node temp = null;
        if(first != null) {
            temp = first;
            for(int i=0;i<index;i++) {  //temp节点依次等于各个节点，到第index个节点时循环停止，temp节点就等于第index个节点了
                temp = temp.getNext();
            }
        }
        return temp;
    }
    public Object get(int index) {
        Node temp = Ergodic(index);
        return temp.getSth();
    }
    //依然是检查越界的方法
    public void aragecheck(int index) { 
        if(index<0||index>size-1) {
            try {
                throw new Exception();
            }catch(Exception e) {
                e.printStackTrace();
            }
        }
    }
    //向链表中顺序添加新节点的方法
    public void SeqAdd(Object sth) {
        Node n = new Node();            //定义一个新节点n
        if(first==null) {               //如果首节点为空，n将成为首节点
            n.setPrevious(null);        //首节点没有上一个节点
            n.setSth(sth);
            n.setNext(null);            //暂且没有下一个节点
            first = n;                  //将节点n定义为第一个节点
            last = n;                   //由于n是第一个添加的节点，所以它目前也是最后一个节点
        }else {                         //如果首节点不为空
            n.setPrevious(last);        //n的上一个节点为曾经的末节点
            n.setSth(sth);
            n.setNext(null);            //暂且没有下一个节点
            last.setNext(n);            //将曾经为空的末节点的next域指向n
            last = n;                   //n成为末节点
        }
        size++;
    }
    //移除链表元素的方法
    public void remove(int index) {
        if(first != last) {                //如果链表中不止一个节点
            Node pre;
            Node nxt;
            Node temp = Ergodic(index);      //遍历链表，找到要删的那一个节点temp
            pre = temp.getPrevious();        //将temp节点的上一个节点命名为pre
            nxt = temp.getNext();            //将temp节点的下一个节点命名为nxt
            pre.setNext(nxt);                //pre节点的next节点本来是temp节点，现在换为nxt节点
            nxt.setPrevious(pre);            //nxt节点的previous节点本来是temp节点，现在换为pre节点
            //上面两步执行完后，temp的上一个节点和下一个节点连接在了一起，而隔过了temp节点，
            //实现了删除temp节点
        }else {
            first = null;                  //如果链表中只有一个节点，就直接给它整空
        }
        size--;
    }
    //获得链表大小的方法
    public int getSize() {
        return size;
    }
}

二、HashMap的基本实现
定义键值对

package Map;
/**
 * 定义Entry类（键值对）
 * @author DaluxC
 *
 */
public class Entry {
    private Object key;
    private Object value;
    public Entry(Object key,Object value) {
        this.key = key;
        this.value = value;
    }
    public Object getKey() {
        return key;
    }
    public void setKey(Object key) {
        this.key = key;
    }
    public Object getValue() {
        return value;
    }
    public void setValue(Object value) {
        this.value = value;
    }
}

实现HashMap

package Map;
import LinkList.TestLinklist;
/**
 * @author DaluxC
 * 同时利用数组和链表来实现map容器
 * map容器储存键值对(key-value)，一个key值对应一个value值
 */
public class TestMap {
    TestLinklist[] arr = new TestLinklist[999];       //定义一个每个元素都是一个链表的数组
    int size;
    //定义向容器中添加数据的方法
    public void put(Object key,Object value) {
        Entry e = new Entry(key,value);
        int m = key.hashCode()%arr.length;            //设置一个int值m，其值为输入的key值的哈希码值与数组arr的长度的模，通过这个模值来找某一个数据的位置
        if(arr[m] == null) {                          //如果数组中第m个链表为空
            TestLinklist l = new TestLinklist();      //新建一个链表
            l.SeqAdd(e);                              //向这个链表中添加第一个节点
            arr[m]=l;                                 //将新建的这个链表赋给数组中的第m个元素
        }else {                                       //如果第m个链表不为空
            for(int i=0;i<arr[m].getSize();i++) {     //遍历链表
                Entry g = (Entry)arr[m].get(i);
                if(g.getKey().equals(key)) {          //如果发现要添加的这个key值已经第m个链表中存在
                    g.setValue(value);                //用新输入的value值覆盖掉这个key值曾经对应的value值
                }
            }
            arr[m].SeqAdd(e);                         //如果要添加的这个key值在第m个链表中不存在，则直接在这个链表后直接添加新节点
        }
        size++;
    }
    //定义从容器中读数据的方法
    public Object get(Object key) {
        int m = key.hashCode()%arr.length;
        if(arr[m] != null) {
            for(int i=0;i<arr[m].getSize();i++) {     //遍历相应的链表
                Entry g = (Entry)arr[m].get(i);
                if(g.getKey().equals(key)) {          //如果找到了与输入的key值相等的key值
                    return g.getValue();              //返回这个key值对应的value值
                }
            }
        }else
            System.out.println("没有找到值");
        return null;                                  //如果相应的链表为空，则输出null
    }
    //定义从容器中移除数据的方法
    public void remove(Object key) {
        int m = key.hashCode()%arr.length;
        if(arr[m] != null) {
            for(int i=0;i<arr[m].getSize();i++) {     //依然是遍历相应链表
                Entry g = (Entry)arr[m].get(i);
                if(g.getKey().equals(key)) {          //如果找到了与输入的key值相等的key值
                    arr[m].remove(i);                 //直接调TestLinklist类的remove方法给它删了
                }
            }
        }
    }
}