12、数据结构与算法 - 实战：哈希（散列）表

哈希表

思路：一个数组存多个链表 - 当存东西进入时，根据东西的特性将其添加到某个数组链表中，查找元素时，根据东西特性进行从数组中某个链表进行查找

Student.java

public class Student {
    Integer id;
    String name;
    Integer year;
    public Integer getId() {
        return id;
    }
    public void setId(Integer id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Integer getYear() {
        return year;
    }
    public void setYear(Integer year) {
        this.year = year;
    }
    @Override
    public String toString() {
        return "Student{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", year=" + year +
                '}';
    }
}

MyLinkededList.java

public class MyLinkededList<T> {
    Node<T> head = null;
    // 添加链表节点
    public boolean add(T t) {
        //将数据封装成链表节点
        Node<T> newNode = new Node<T>();
        newNode.setData(t);
        //判断当前链表中是否存在相同ID号的特征节点，存在则添加元素失败
        Integer id = newNode.getId();
        T queryT = this.query(id);
        if(queryT != null) {
            return false;
        }
        //添加链表节点
        //头元素
        if (head == null) {
            head = newNode;
            //非头元素
        } else {
            Node<T> tempNode = head;
            while (true) {
                if (tempNode.next == null) {
                    tempNode.next = newNode;
                    break;
                }
                tempNode = tempNode.next;
            }
        }
        return true;
    }
    public T query(Integer id) {
        if (head == null) {
            return null;
        } else {
            Node<T> curNode = head;
            while (true) {
                int tId;
                try {
                    tId = curNode.getId();
                    if (tId == id)
                        return curNode.getData();
                } catch (Exception e) {
                    e.printStackTrace();
                }
                curNode = head.getNext();
                if (curNode == null) {
                    break;
                }
            }
        }
        return null;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<T> curNode = head;
        boolean flag = false;
        while (true) {
            if (curNode == null) {
                if (flag) {
                    int start = sb.lastIndexOf(", ");
                    sb.replace(start, sb.length(), "");
                }
                break;
            }
            flag = true;
            sb.append(curNode.getData() + ", ");
            curNode = curNode.getNext();
        }
        sb.append("]");
        return sb.toString();
    }
    //内置类 - 即链表节点
    private class Node<T> {
        T data;
        Node<T> next;
        //
        public Integer getId() {
            Integer id = null;
            try {
                Field field = data.getClass().getDeclaredField("id");
                field.setAccessible(true);
                id = (Integer) field.get(data);
            }catch(Exception e) {
                e.printStackTrace();
            }
            return id;
        }
        public T getData() {
            return data;
        }
        public void setData(T data) {
            this.data = data;
        }
        public Node<T> getNext() {
            return next;
        }
        public void setNext(Node<T> next) {
            this.next = next;
        }
    }
}

MyHashTable.java

public class MyHashTable<T> {
    //默认表容器
    private final int DEFAULT_SIZE = 10;
    //当前使用的表容器
    private int curSize = 10;
    //链表数组
    MyLinkededList<T>[] lists;
    MyHashTable() {
        this.lists = new MyLinkededList[DEFAULT_SIZE];
    }
    MyHashTable(int size) {
        curSize = size;
        this.lists = new MyLinkededList[curSize];
    }
    //添加元素 - 如果链表中已经存在特征即相同ID号则添加失败
    public boolean add(T t) {
        Integer id = null;
        try {
            id = (Integer) t.getClass().getDeclaredField("id").get(t);
        } catch (Exception e) {
            e.printStackTrace();
        }
        int index = id % curSize;
        if (lists[index] == null) {
            lists[index] = new MyLinkededList<T>();
        }
        MyLinkededList<T> list = lists[index];
        return list.add(t);
    }
    //根据东西特征即ID号进行查询元素
    public T query(Integer id) {
        int index = id % curSize;
        if (lists[index] == null) {
            return null;
        }
        return lists[index].query(id);
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        for(MyLinkededList list : lists) {
            if(list != null) {
                sb.append("第" + index + "链表的内容为：" + list + "\n");
            }
            index++;
        }
        sb.replace(sb.length()-1, sb.length(), "");
        return sb.toString();
    }
    public static void main(String[] args) {
        Student student = new Student();
        student.setId(1);
        student.setName("lrc");
        student.setYear(23);
        Student student2 = new Student();
        student2.setId(2);
        student2.setName("lcj");
        student2.setYear(26);
        Student student3 = new Student();
        student3.setId(12);
        student3.setName("yth");
        student3.setYear(27);
        Student student4 = new Student();
        student4.setId(12);
        student4.setName("ythfdsfsdf");
        student4.setYear(272);
        MyHashTable<Student> hashTable = new MyHashTable<>();
        hashTable.add(student);
        hashTable.add(student2);
        hashTable.add(student3);
        hashTable.add(student4);
        System.out.println(hashTable);
         System.out.println(hashTable.query(12));
        System.out.println(hashTable.query(100));
    }
}