第 5 关 | 算法的备胎 hash 和找靠山的队列：1.青铜挑战—

1. Hash 基础

1.1. Hash 的概念以及基本特征

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

很多人可能想不明白，这里的映射是什么意思，为啥访问的时候时间复杂度为O(1)？我们只要看存和读的时候分别怎么映射就知道了。

我们现在假设数组 array 存放的是 1 到 15 这些数，现在要存一个大小为 7 的 Hash 表，应该怎么存了》我们存储的位置公式是

index = number % 7

这时候我们将 1 到 6 存入的时候，图示如下：

这个没有疑问，因为就是简单地取模，然后继续存 7 到 13 ，结果就是下面这个样子：

最后再存 14 和 15：

这个时候就我们会发现，有些数据被存到了同一个位置，我们后面再讨论。接下俩，我们看看如何取。

假如我要测试 13 在不在这个结构里面，这同样使用上面这个公式来进行，很明显，13 % 7 =6 ，直接访问 array【6】这个位置，很明显，返回 true。

假如我要测试 20 在不在这个结构里面，同样使用上面这条公式，很明显 20 % 7 = 6，所以直接访问array【6】这个位置，会发现该位置只有 6 和 13，所以返回 false。

理解这个例子我们就理解了 Hash 是如何进行最基本的映射的，以及为什么有时候访问的复杂度是O(1).

1.2. 碰撞处理方法

在上面这个例子中，我们发现有些数字在Hash 中可能很多个位子要存两个甚至以上个元素，很明显单纯的数组是不行的，这种两个不同的输入值，根据同一个散列函数计算出的散列值相同的现象称之为碰撞。

那应该怎么解决呢？

常见的方法有：开放地址法和链地址发、再哈希法、建立公共溢出区，后面两种用的比较少，我们重点看前面两个。

1.2.1. 开放地址法

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

例如，上面这个如果要继续存 7、8、9的时候，7没问题，可以直接存到索引为 0 的位置，8本来就应该存在索引为1 的位置，但是已经满了，所以继续往后找，索引3的位置是空的，所以 8 存到 3 位置，同理 9 存在索引 6 位置。

这里你是否有一个疑惑：这样鸠占鹊巢的方法会不会引起混乱？再比如存入3和6的话，本来自己的位置是好好的，但是给外来户占领了，该如何处理呢？这个问题在 Java 里面的 ThreadLocal 解开了，具体的过程可以学习一下相关内容，这里主要说一下基本思想。ThreadLoacl有专门一个存储元素的ThreadLoaclMap，每次 get 和 set 的时候，会先将目标位置前后的空间搜索一下，将标记为 null 的位置回收掉，这样大部分不用的位置就收回起来了。这就像假期后的你回到公司，每个人都将自己的位置打扫得非常干净，结果整个工作区就很干净了。当然那Hash 处理该问题的整个过程非常复杂，涉及弱引用等等。

1.2.2. 链地址法

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

这种处理方法的问题就是处理起来代价非常高，要落地很多优化，例如 java 中的 ConcurrentHashMap 中就使用了这种方式，其中涉及元素尽量均匀、访问和操作速度要快、线程安全、扩容等许多问题。

接下里来看这个 Hash 结构，下面的图中有两处非常明显的错误，请你先想想是啥。

首先是数组的长度必须是 2 的 n 次幂，这里的长度是 9 ，，面向有错，然后 entry 的个数不能大于数组长度的 75%，如果大于就会触发扩容机制进行扩容，这里明显是大于 75%的，正确的图如下：

数组的长度是 2 的 n 次幂，而且他的size又不大于数组长度的 75%。HashMap 实现的原理是想要找到存放数组的下标，如果是空的就存进去，如果不是空的就判断 key 值是否一样，如果一样就替换，如果不一样就以链表的形式存在（从 JDK 8 开始，根据元素的数量选择使用链表还是红黑树存储）。

2. 队列基础知识

2.1. 队列的概念和基本特征

队列的特点就是节点的排队次序和入队次序按入队时间先后确定，先入队者先出队，后入队者否出队，也就是我常说的FIFO(First In Frist Out)先进先出，队列的实现有两种方式，基于数组和链表。基于链表的方式可能多一点，因为链表的长度是可变的，实现起来比较建党，如果基于数组，可能会有点麻烦，我们将其放在黄金挑战里面，这里只看一下基于链表实现的方法。

2.2. 实现队列

基于链表实现队列还是比较好处理的，只要在尾部添加元素，在 front 删除元素即可。

package com.qinyao.queue;

import org.w3c.dom.Node;

/**
 * @ClassName LinkQueue
 * @Description
 * @Version 1.0.0
 * @Author LinQi
 * @Date 2023/09/10
 */
public class LinklistQueue<T> {
    private Node front;
    private Node rear;
    private int size;

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

    /**
     * 入队
     */
    public  void push(int value){
        Node newNode = new Node(value);
        Node temp = front;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = newNode;
        rear = newNode;
        size++;
    }

    /**
     * 出队
     */
    public T pull(){
        if(front.next == null){
            System.out.println("队列为空，没有要出队的元素");
        }
        Node firstNode = front.next;
        front.next = firstNode.next;
        size--;
        return (T) firstNode.data;
    }

    /**
     * 遍历队列
     */
    public void traverse(){
        if(front.next == null){
            System.out.println("队列为空");
            return;
        }
        Node temp = front.next;
        while(temp != null){
            System.out.println(temp.data + "\t");
            temp = temp.next;
        }
    }


    private class Node<T> {
        T data;
        Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node(T data) {
            this.data = data;
        }
    }
}

第 5 关 | 算法的备胎 hash 和 找靠山的队列：1.青铜挑战——队列和 Hash 的特征-灵析社区