[Collection与数据结构] Map与Set(二):哈希表

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:🍕 Collection与数据结构 (91平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
在这里插入图片描述

目录

3. 哈希表

3.1 哈希表的概念

顺序结构以及平衡树中,元素关键码与其储存位置没有一一对应的关系,因此在查找一个元素的时候,必须经过关键码的多次比较.顺序查找的时间复杂度为O(N),平衡树中为树的高度O(log2N),搜索效率取决于搜索过程中元素的比较次数.
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
向该结构中:

  • 添加元素:通过函数计算出该元素锁要存放的位置,并按次位置进行存放.
  • 搜索元素:通过函数计算出所要搜索的位置,在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

  • 哈希函数的设置为key = key%capacity,capacity是哈希表的容量.

在这里插入图片描述
但是如果按上述的方式存储元素的话,有一个非常明显的问题,就是如果出现一个key值为14的元素,想要插入哈希表中,计算之后key的结果是4,但是4位置已经有了对应的元素,这时候就会产生冲突.我们称这种冲突为哈希冲突.

3.2 哈希冲突

不同的两个元素关键字k1和k2经过哈希函数计算之后,Hash(k1) = Hash(k2),即:不同的关键字经过哈希函数计算之后,哈希地址相同,这种现象称为哈希冲突或者哈希碰撞.
具有不同的关键码而具有相同哈希地址的元素在哈希表中,我们称为"同义词".

3.3 降低哈希冲突

3.3.1 负载因子

  • 概念
    首先什么是负载因子:哈希表中的元素总个数/哈希表的长度.负载因子和哈希表中元素的个数成正比,当哈希表中总元素的个数越多,负载因子越大,产生哈希冲突的概率也越大.
    负载因子和哈希冲突出现的概率也满足着一定的关系,具体的函数关系如下:
    在这里插入图片描述
    当哈希冲突达到一定的程度的时候,我们就需要通过降低负载因子的方法来降低哈希冲突发生的概率,由于哈希表中的元素个数已经确定了,所以我们需要通过加长哈希表的大小来降低哈希冲突.我们一般认为当负载因子达到0.75的时候,就要降低负载因子了,当然这个值也不是固定的,看具体的应用场景.

3.3.2 降低负载因子(降低哈希冲突)

解决哈希冲突两种常见的方法是：闭散列和开散列.

  • 闭散列
    当发生哈希冲突的时候,如果哈希表为被装满,那么就还有空位置,可以把key存放冲突位置的下一个空位置上.那么如何找到下一个空位置呢?
    1. 线性探测
      从冲突位置开始,依次向后探测,直到找到一个空位置为止.

    举例
    现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突
    通过哈希函数获取待插入元素在哈希表中的位置
    如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到
    下一个空位置，插入新元素
    在这里插入图片描述

    1. 二次探测
      线性探测的缺点就是,冲突的元素都会堆在一起,我们为了避免这种问题,于是我们引入了二次探测.
      查找下一个空位置的方法为:Hi=(H0-i2)%len,其中,i为常数,这个常数可以是任意整数,H0为key通过哈希函数计算出的哈希地址.len为哈希表的长度.

因此:闭散列的缺点就是空间利用率较低.

  • 开散列-哈希桶法(重点)
    散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中.就像净水机的滤芯一样.
    在这里插入图片描述

在这里插入图片描述
从上图中可以看出,每一个桶中都放的是发生哈希冲突的元素.
但是当冲突严重的时候,就是每一个哈希桶中的元素比较多的时候,这时候哈希桶中的链表就会转化成红黑树.

3.4 实现哈希表

import java.util.Arrays;

/**
 * 该哈希表使用哈希桶的方式解决哈希冲突
 */
public class HashBucket {
    //哈希表中的结点
    private static class Node{
        private int key;
        private int value;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node[] array;//存放链表的数组
    private int size;//哈希表大小
    private static final double LOAD_FACTOR = 0.75;//默认负载因子

    public HashBucket() {
        this.array = new Node[10];
        this.size = 0;
    }
    /**
     * 添加元素
     */
    public void put(int key,int value){
        int index = key % array.length;
        //找到哈希表中对应的哈希桶,遍历链表
        for (Node cur = array[index]; cur != null ;cur = cur.next) {
            if (key == cur.key) {//如果要添加的关键字等于已有的关键字,则修改关键字对应的值
                cur.value = value;
            }
        }
        //要添加的关键字在该哈希桶中不存在
        Node node = new Node(key, value);
        node.next = array[index];//使用头插法插入元素
        array[index] = node;
        size++;
        if (LOAD_FACTOR <= loadFactor()){//负载因子阈值大于计算之后的负载因子
            resize();//对哈希表进行重新哈希
        }
    }

    /**
     * 计算负载因子
     * @return 返回负载因子
     */
    private double loadFactor(){
        return size*1.0/array.length;
    }

    /**
     * 对哈希表进行重新哈希
     */
    private void resize(){
        //创建一个新数组
        Node[] newArray = Arrays.copyOf(array,array.length*2);
        for (int i = 0; i < array.length; i++) {//遍历哈希表,重新哈希每个桶中的元素
            Node cur = array[i];
            while (cur != null){
                Node next = cur.next;//这里要记录下来下一个结点的位置,不然之后修改了cur.next的位置,就找不到原来next的位置
                //cur就走不下去了
                int index = cur.key % newArray.length;//重新计算在新数组中对应的哈希地址
                cur.next = newArray[index];
                newArray[index] = cur;//使用头插法进行添加
                cur = next;
            }
        }
        array = newArray;//把引用给回去
    }

    /**
     * 获得key对应的value
     * @param key 关键字
     * @return 返回key对应的value
     */
    public int get(int key){
        int index = key % array.length;
        for (Node cur = array[index]; cur != null; cur = cur.next){//遍历哈希桶
            if (cur.key == key){
                return cur.value;
            }
        }
        return -1;
    }
}

如果哈希表中存储的不仅仅是整数,我们就需要指定哈希表的泛型参数.指定哈希表的泛型参数之后,key就不可以直接用来计算哈希地址了,因为计算哈希地址的公式中涉及到去余数,而引用类型对象不可以直接进行取余.我们要使用类中重写的hashcode方法来计算哈希地址.第二点就是引用类型不可以直接用两个等号比较,我们需要使用类中重写的equals方法来判断key是否相同.

import java.util.Arrays;

/**
 * 该哈希表使用哈希桶的方式解决哈希冲突
 */
public class HashBucket2<K,V> {
    //哈希表中的结点
    private static class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node<K,V>[] array;//存放链表的数组
    private int size;//哈希表大小
    private static final double LOAD_FACTOR = 0.75;//默认负载因子

    public HashBucket2() {
        this.array = new Node[10];
        this.size = 0;
    }
    /**
     * 添加元素
     */
    public void put(K key,V value){
        int index = key.hashCode() % array.length;//这里就要使用类中重写的Hash值
        //找到哈希表中对应的哈希桶,遍历链表
        for (Node<K,V> cur = array[index]; cur != null ;cur = cur.next) {
            if (key.equals(cur.key)) {//如果要添加的关键字等于已有的关键字,则修改关键字对应的值
                //注意在这里使用的时候,应该使用equals方法,因为参数是引用数据类型
                cur.value = value;
            }
        }
        //要添加的关键字在该哈希桶中不存在
        Node<K,V> node = new Node<>(key, value);
        node.next = array[index];//使用头插法插入元素
        array[index] = node;
        size++;
        if (LOAD_FACTOR <= loadFactor()){//负载因子阈值大于计算之后的负载因子
            resize();//对哈希表进行重新哈希
        }
    }

    /**
     * 计算负载因子
     * @return 返回负载因子
     */
    private double loadFactor(){
        return size*1.0/array.length;
    }

    /**
     * 对哈希表进行重新哈希
     */
    private void resize(){
        //创建一个新数组
        Node<K,V>[] newArray = Arrays.copyOf(array,array.length*2);
        for (int i = 0; i < array.length; i++) {//遍历哈希表,重新哈希每个桶中的元素
            Node<K,V> cur = array[i];
            while (cur != null){
                Node<K,V> next = cur.next;//这里要记录下来下一个结点的位置,不然之后修改了cur.next的位置,就找不到原来next的位置
                //cur就走不下去了
                int index = cur.hashCode() % newArray.length;//重新计算在新数组中对应的哈希地址
                cur.next = newArray[index];
                newArray[index] = cur;//使用头插法进行添加
                cur = next;
            }
        }
        array = newArray;//把引用给回去
    }

    /**
     * 获得key对应的value
     * @param key 关键字
     * @return 返回key对应的value
     */
    public V get(K key){
        int index = key.hashCode() % array.length;
        for (Node<K,V> cur = array[index]; cur != null; cur = cur.next){//遍历哈希桶
            if (key.equals(cur.key)){
                return cur.value;
            }
        }
        return null;
    }
}

我们进行一个类的实现,重写hashcode方法和equals方法.其中hashcode方法指定一个成员变量为组织hashcode的关键字.我们可以借助编译器快速按照指定的成员变量生成hashcode方法和equals方法.
在这里插入图片描述

import java.util.Objects;

public class Person {
    public String id;
    public String name;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(id);
    }
}

开始测试:

public class Test {
    public static void main(String[] args) {
        HashBucket2<Person,String> hashBucket2 = new HashBucket2<>();
        Person person = new Person("1234","张三");
        Person person1 = new Person("1234","李四");
        hashBucket2.put(person,"12345");
        hashBucket2.put(person1,"123");
        System.out.println(hashBucket2.get(person));//按1234的身份证号获取到的value为123,说明
        //第二个put的数据把第一个put的数据覆盖掉了,就是两个人的id一样导致了hashcode一样
        //就导致了在哈希表中存在的位置一样
    }
}

运行结果:
在这里插入图片描述