哈希表，哈希桶及配套习题

我们今天带大家简单了解哈希表是怎样的，和简单模拟哈希桶，还有几道练习题

一，哈希表

什么是哈希表，哈希表是一种非常非常高效的数据结构，它用来搜索我们想要的数据，我们之前学过很多查找方法，最快基本时间复杂度就是Olog2(n)，哈希表可以达到O(1)；这是怎么做到的呢，因为哈希表的查找并不是遍历，或是递归，而是根据哈希函数来计算这个数据应该存放的地址，取出时也通过哈希函数拿出我们的元素。

1，哈希函数

我们怎么去设计哈希函数呢，说实话这不是我们能设计的，我们拿来用就好了。

（1）index = y % capacity;

容量我们可以当做数组长度，y就是我们输入的数字，index就是我们获得的新的下标。

我们后面哈希桶用这个方法。

我们比如capacity =10，y为7，那么Index就为7，我们把7放到数组7下标，但是我们方17,17%10=7，那我们还是放到7下标吗，这就引出了哈希冲突。

2，哈希冲突

哈希冲突指的是我们在使用哈希函数时，计算的几个函数的地址都相同，我们叫它哈希冲突或者哈希碰撞，我们无法正常使用我们的数组来搜索对应的函数了。

3，哈希冲突的避免

有问题就要解决，我们如何避免哈希冲突呢，哈希冲突的发生是必然的，我们既然根据刚才的哈希函数，可以知道，添加数据越多，哈希冲突发生概率越大，那我们就可以扩容，降低哈希冲突的发生概率，我们还可以改变哈希函数，

常见哈希函数

1. 直接定制法--(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况

2. 除留余数法--(常用）

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法--(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法--(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

6. 数学分析法--(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如 1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

4，负载因子

我们刚才谈过了，负载因子就是填入表中的个数 / 散列表长度，我们通常控制负载因子在7.5，超过7.5，冲突率发生的概率就大大提升。

5，解决冲突

解决冲突的方法分两种，开散列和闭散列，

我们这里重点掌握哈希桶，

哈希桶是啥意思，哈希桶是存放哈希元素冲突元素的地方。

我们通常在每个哈希表的下标中放入链表来延长每个哈希表下标的元素，比如4,44,14，我们都存在4下标的一个链表中。

我们来模拟实现一下。

public class HashBucket<K,V> {
    private static class Node<K,V> {
        private K key;
        private V value;
        Node<K,V> next;


        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }


    private Node<K,V>[] array = (Node<K, V>[]) new Node[DEFAULT_SIZE];
    private int size;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 10;//默认桶的大小

    public void put(K key, V value) {
        Node<K,V> newNode = new Node<>(key, value);
        int index = key.hashCode() % array.length;
        Node<K,V> cur = array[index];
        Node<K,V> p = null;
        if(cur==null){
            array[index] = newNode;
            size++;
            if (loadFactor()>LOAD_FACTOR){
                resize();
            }
        }
        else {
            while (cur!=null){
                if(cur.key.equals(key)){
                    cur.value = value;
                    return;
                }
                p = cur;
                cur = cur.next;
            }
            p.next = newNode;
            size++;
            if (loadFactor()>LOAD_FACTOR){
                resize();
            }
        }
    }


    private void resize() {
        Node<K,V>[] newArray = (Node<K, V>[]) new Node[2*array.length];
        Node<K,V> cur = null;
        Node<K,V> p = null;
        for (int i = 0; i < array.length; i++) {
            cur = array[i];
            while (cur!=null){
                int newIndex = cur.key.hashCode() % newArray.length;
                p = cur.next;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = p;
            }
        }
        array = newArray;
    }


    private double loadFactor() {
        return size * 1.0 / array.length;
    }



    public V get(K key) {
        Node<K,V> cur = null;
        int index = key.hashCode() % array.length;
        cur = array[index];
        while (cur!=null){
            if(cur.key.equals(key)){
                return cur.value;
            }
        }
        return null;
    }
}

我们来练几道题

二，题目练习

138. 随机链表的复制 - 力扣（LeetCode）

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

代码实现：

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            //遍历链表，将链表的每个节点放到key复制一份放到value
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur!=null){
            //再次遍历链表，用map找到每次创建的新节点，在通过map找到其next,random需要指向的节点。
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

链接：旧键盘 (20)__牛客网
来源：牛客网

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
肯定坏掉的那些键。

输入描述:

输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。

输出描述:

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

示例1

输入

7_This_is_a_test<br/>_hs_s_a_es

输出

7TI

代码示例：

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        input = input.toUpperCase();
        String output = in.nextLine();
        output = output.toUpperCase();
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<output.length();i++){
            char a = output.charAt(i);
            if(map.get(a)==null){
                map.put(a,1);
            }else{
                map.put(a,map.get(a)+1);
            }
        }

        for(int i=0;i<input.length();i++){
            char w = input.charAt(i);
            if(map.get(w)==null){
                System.out.print(w);
                map.put(w,1);
            }
        }

    }
}

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

771. 宝石与石头 - 力扣（LeetCode）

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

提示：

1 <= jewels.length, stones.length <= 50
jewels 和 stones 仅由英文字母组成
jewels 中的所有字符都是 唯一的

代码示例：

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Map<Character,Integer> map = new HashMap<>();
         for(int i=0;i<jewels.length();i++){
            char c = jewels.charAt(i);
            map.put(c,1);
         }
         int count = 0;
         for(int i=0;i<stones.length();i++){
            char c = stones.charAt(i);
            if(map.get(c)!=null){
                count++;
            }
         }
         return count;
    }
}

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

136. 只出现一次的数字 - 力扣（LeetCode）

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次.

代码示例：

class Solution {
    public int singleNumber(int[] nums) {
        //方法1
        // int num = nums[0];
        // for(int i=1;i<nums.length;i++){
        //     num = num ^ nums[i];
        // }
        // return num;

        //方法2
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.get(nums[i])==null){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i])+1);
            }
        }

        for(int i=0;i<nums.length;i++){
            if(map.get(nums[i])==1){
                return nums[i];
            }
        }
        return -1;
    }
}