Hash表

Hash表

Hash表采用了数组加链表的结构，即一个数组元组中不再是存储单个元素，而是存储一个链表，就好比包租婆收租的时候，一个握把上面挂了一连串的钥匙一样。Hash表的引出是为了减少查询数据库操作所带来的时间问题，将数据直接存放在哈希表中，方便查阅。当然，现在也可以用redis来做缓存操作。

从小往大看，每一个节点代表一个对象，并采用单链表的形式将每个节点串联起来，因此要先创建一个节点，该节点用于存储信息以及关联下一个节点

//表示一个雇员
class Emp{
    private int id;
    private String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

注意：这里的Emp next属性必须设置为public，否则访问不到哦

创建好每个节点后，就可以创建一个单链表了，用于对新增节点的关联、整个节点的遍历输出、单个节点的查找以及单个节点的删除操作

/创建EmpLinkedList,一条链表
class EmpLinkedList{
    private Emp head = null;
    //添加员工信息
    public void add(Emp emp){
        if (head == null){
            head = emp;
            return;
        }
        Emp temp = head;
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = emp;
    }
    //遍历链表
    public void list(int id){
        if (head == null){
            System.out.println("第"+(id+1)+"条链表为空");
            return;
        }
        Emp temp = head;
        while (true){
            System.out.println(temp);
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        System.out.println();
    }
    //查找
    public Emp find(int id){
        if (head == null){
            System.out.println("员工不存在");
            return null;
        }
        Emp temp = head;
        while (true){
            if (id == temp.getId()){
                break;
            }
            if (temp.next == null){
                temp =null;//最后没有找到
                break;
            }
            temp = temp.next;

        }
        return temp;
    }

    //删除
    public void delete(int id){
        if(head == null){
            System.out.println("该用户不存在");
            return;
        }
        else {
            if (head.next == null){
                if (head.getId() == id){
                    head = null;
                    return;
                }else {
                    System.out.println("该用户不存在");
                    return;
                }
            }else {
                if (head.getId() == id){
                    head = head.next;
                }else {
                    Emp temp = head;
                    while (true){
                        if (temp.next == null) {
                            System.out.println("该用户不存在");
                            break;
                        }
                        if (id == temp.next.getId()){
                            temp.next = temp.next.next;
                        }

                        temp = temp.next;
                }

                }
            }
        }
    }

此时对一个单链表的增删改查操作已经完成，接下来就是创建一个Hash表用于存储多个链表了，也就是创建一个链表数组

class HashTab{
    private EmpLinkedList[] empLinkedLists;//数组，数组里面放链表
    private int size;

    public HashTab(int size) {
        this.size =size;
        empLinkedLists = new EmpLinkedList[size];
        for (int i = 0;i<size;i++){
            empLinkedLists[i] = new EmpLinkedList();
        }
    }
    //添加员工
    public void add(Emp emp){
        //首先我们应该得到该员工的id，根据id判断该员工应该放在那一个链表下
        empLinkedLists[hashFun(emp.getId())].add(emp);

    }
    //遍历所有链表
    public void list(){
        for (int i=0;i<size;i++){
            empLinkedLists[i].list(i);
        }
    }
    //查找方法
    public void findById(int id){
        int no = hashFun(id);
        Emp emp = empLinkedLists[no].find(id);
        System.out.println(emp);
    }
    //删除员工
    public void deleteById(int id){
        int no = hashFun(id);
        empLinkedLists[no].delete(id);
    }


    //散列函数，用于根据用户id决定该用户放在哪一条链表
    public int hashFun(int id){
        return id%size;
    }


}

在创建Hash表的时候，需要创建链表数组，一定要对数组的每个元素进行链表初始化，和普通数组不一样，普通数组只需要简单的指定数组长度，默认初始化为0或者null

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FZjZvU1Z-1594258468879)(C:\Users\admin\AppData\Roaming\Typora\typora-user-images\image-20200708112507318.png)]

将员工插入到Hash表中，首先根据员工的id来决定该员工应该放入哪一个链表中，由此引出散列函数，本文采用最简单的散列函数，通过将id对真个链表数组长度进行求模

//散列函数，用于根据用户id决定该用户放在哪一条链表
    public int hashFun(int id){
        return id%size;
    }

在hash表以及链表中都有对应的增删改查函数，hash表中曾删改是通过用户的id经过散列函数找到对应的链表，在定位到链表后，通过链表中的增删改是遍历整个链表找到id对应的节点（默认id是不重复的），其中删除最麻烦（个人认为）

//删除员工   将id通过散列函数找到对应的链表
    public void deleteById(int id){
        int no = hashFun(id);
        empLinkedLists[no].delete(id);
    }

//删除   
    public void delete(int id){
        if(head == null){
            System.out.println("该用户不存在");
            return;
        }
        else {
            if (head.next == null){
                if (head.getId() == id){
                    head = null;
                    return;
                }else {
                    System.out.println("该用户不存在");
                    return;
                }
            }else {
                if (head.getId() == id){
                    head = head.next;
                }else {
                    Emp temp = head;
                    while (true){
                        if (temp.next == null) {
                            System.out.println("该用户不存在");
                            break;
                        }
                        if (id == temp.next.getId()){
                            temp.next = temp.next.next;
                        }

                        temp = temp.next;
                }

                }
            }
        }

这里删除之所以觉得麻烦是因为在构造链表的时候，head节点也赋值了，本人首先判断了head是否为空，在不为空的情况下，判断是否只有head节点，如果只有一个head节点就可直接判断是否是要删除的节点。如果head不为空并且也不止一个节点，此时就可以判断temp.next是否为空了，为空则说明已经遍历到最后一个节点了，则可直接退出，找到删除节点的条件是temp.next.getId() == id,单链表在删除的时候必须判断当前节点的下一个节点是否为目的节点，这样才能通过语句temp.next = temp.next.next来实现删除目标节点。

加入head里面不存放数据只是一个标志节点，我们改如何删除呢？

public void deleteById(int id)
    if(head.next == null){
        system.out.println("当前删除用户不存在！");
       return;
    }
	Emp temp = head;
	while(true){
        if(head.next == null){
            return;
        }
        if(id = temp.next){
            temp.next = temp.next.next;
        }
        temp = temp.next;
    }

测试代码：

public static void main(String[] args) {
        //创建一个hash表
        HashTab hashTab = new HashTab(7);
        Emp emp01 = new Emp(12,"张三");
        Emp emp02 = new Emp(14,"李四");
        hashTab.add(emp01);
        hashTab.add(emp02);
        hashTab.list();
        hashTab.findById(5);
        hashTab.findById(12);
        hashTab.deleteById(12);
        System.out.println("==========");
        hashTab.list();

    }

结果显示：

Emp{id=14, name='李四'}

第2条链表为空
第3条链表为空
第4条链表为空
第5条链表为空
Emp{id=12, name='张三'}

第7条链表为空
null
Emp{id=12, name='张三'}
==========
Emp{id=14, name='李四'}

第2条链表为空
第3条链表为空
第4条链表为空
第5条链表为空
第6条链表为空
第7条链表为空

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

}

结果显示：

```java
Emp{id=14, name='李四'}

第2条链表为空
第3条链表为空
第4条链表为空
第5条链表为空
Emp{id=12, name='张三'}

第7条链表为空
null
Emp{id=12, name='张三'}
==========
Emp{id=14, name='李四'}

第2条链表为空
第3条链表为空
第4条链表为空
第5条链表为空
第6条链表为空
第7条链表为空