队列和hash问题解析

一.Hash

1什么是散列表

哈希(Hash)也称为散列,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,这个输出值就是散列值。

散列表有几个重要的特性:

1.散列函数计算出的索引值大于等于0

2.两个数相同时,计算出的索引一定相同

3.索引相同不一定两个数相同(散列冲突)

2.储存映射过程

我们现在假设数组array存放的是1到15这些数,现在要存在一个大小是7的Hash表中,该如何存呢?我们存储的位置计算公式是 :

index=number 模 7

image-20231012224850209

3.Hash碰撞处理方法

常见的方法有:

  • 开放定址法(Java里的Threadlocal)
  • 链地址法(Java里的ConcurrentHashMap)
  • 再哈希法(布隆过滤器)
  • 建立公共溢出区

后两种用的不多,常见前两种

1.开放寻址

开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

2.拉链法

将哈希表的每个单元作为链表的头结点,所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。例如:

image-20231012225946913

二.队列基础知识

1.什么是队列FIFO

队列的特点是节点的排队次序和出队次序按入队时间先后确定,即先入队者先出队,后入队者后出队,即我们常说的FIFO(first in first out)先进先出。队列实现方式也有两种形式,基于数组和基于链表。 对于基于链表,因为链表的长度是随时都可以变的,实现起来比较简单。如果是基于数组的,会有点麻烦,我们将其放在黄金挑战里再看,这里只看一下基于链表实现的方法。

2.队列的实现(链表)

实现的方法很多

public class Queue {
    private Node front;
    private Node rear;
    private int size;

    public Queue() {
        this.front = new Node(0);
        this.rear = new Node(0);
    }

    public void push(int value) {
        Node node = new Node(value);
        node.next = front.next;
        front.next = node;
    }

    public int pull() {
        int result=0;
        if (front.next == null) {
            System.out.println("队列已空");
        } else {
            Node point = front.next;
            while (point.next != null) {
                rear = point;
                point = point.next;
            }
             result =front.next==point?rear.val: rear.next.val;
        }

        rear.next = null;
        return result;

    }

    static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println("第一个出队的元素为:" + queue.pull());
        System.out.println("第二个出队的元素为:" + queue.pull());
        System.out.println("第三个出队的元素为:" + queue.pull());
        queue.push(5);
        queue.push(6);
        System.out.println("第四个出队的元素为:" + queue.pull());
        System.out.println("第四个出队的元素为:" + queue.pull());
        System.out.println("第四个出队的元素为:" + queue.pull());
//        linkQueue.traverse();
    }
}