HashMap和HashSet

🕗 发布于 2024-10-10 17:42 数据结构

在这里插入图片描述

前言

在谈及HashMap和HashSet前，我们需要先了解一下哈希表的概念

1. 哈希表

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(LogN)，搜索的效率取决于搜索过程中
元素的比较次数。

而我们希望有一种搜索方法，可以不经过任何比较，一次直接从表中得到需要搜索的元素。换句话来说，就是希望元素的存储位置与它的关键码之间能够建立一一映射的关系，从而在查找时，能够很快通过它们的关系函数找到该元素。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)

1.1 冲突

我们通常将哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。我们希望通过哈希函数计算出来的哈希值对于不同关键字能够拥有唯一不同的位置，但是实际情况下，对于两个数据元素的关键字和 (i != j)，有 Ki != Kj，但有：Hash( Ki) == Hash(Kj),也就是说冲突总会发生。

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
例如：数据集合{1 , 3 , 11 , 4 ,6 };

1.2 冲突的避免

冲突的发生是必然的，我们能做的只有尽量的降低冲突率。为什么说冲突的发生是必然的呢？哈希表底层数组的容量往往是小于实际要存储的关键字的数量的。

如何降低冲突率呢？

设计合理的哈希函数

常见的几种哈希函数设计(简单介绍):

直接定制法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

. 除留余数法

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

平方取中法

将关键字数字平方，取其中的几位数为哈希地址

数学分析法

调节负载因子（重要）

冲突率和负载因子的关系图：
在这里插入图片描述

1.3 冲突的解决(降低冲突率)

解决哈希冲突主要有两种常见的方法：闭散列和开散列；我们这里主要介绍开散列这种解决方法。

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

在这里插入图片描述

上面的图示展现了一个哈希桶，也就是说哈希桶的底层是数组加链表来实现的。

//哈希桶的模拟实现
public class HashBucket<K,V> {  
    //完善哈希桶  
    //定义每个结点  
    static class Node<K,V> {  
        public  K key;  
        public V val;  
        public Node<K,V> next;  
        public Node(K key,V val) {  
            this.key = key;  
            this.val = val;  
        }  
    }  
  
    public Node<K,V>[] array = (Node<K,V>[])new Node[10];//数组加链表  
    private int size;  
    private static final double DEFAULT_LOADFACTOR = 0.75;  
  
    //放元素  
    public void push(K key,V val) {  
        int hashCode = key.hashCode();  
        int index = hashCode % array.length;  
        Node<K,V> cur = this.array[index];  
        Node<K,V> parent = null;  
        while(cur != null) {  
            parent = cur;  
            if(cur.key.equals(key)) {  
                cur.val = val;//找到相同的更新val  
                return ;  
            }  
            cur = cur.next;  
        }  
        Node<K,V> newNode = new Node<>(key,val);  
        //尾插  
        if(this.array[index] == null) {  
            this.array[index] = newNode;  
        }else {  
            parent.next = newNode;//尾插新的结点  
        }  
        this.size++;  
        //尾插完新节点后判断负载因子大小，负载因子过大时调节负载因子，降低冲突率  
        //负载因子==插入表中元素/散列表长度  
        if(judgeLoadFactor() >= DEFAULT_LOADFACTOR) {  
            resize();//调节负载因子大小  
        }  
    }  
  
    private void resize() {  
        Node<K,V>[] newArray = (Node<K, V>[]) new Node[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;  
                addLast(cur,newArray);//尾插原数组的结点  
                cur = next;  
            }  
        }  
        this.array = newArray;//更新散列表  
    }  
  
    private void addLast(Node<K,V> cur,Node<K,V>[] newArray) {  
        //尾插的是原数组的结点，先将原数组节点的next置为空  
        cur.next = null;  
        int newIndex = cur.key.hashCode() % newArray.length;  
        if(newArray[newIndex] == null) {  
            newArray[newIndex] = cur;  
        }else {  
            Node<K,V> curNew = newArray[newIndex];  
            while(curNew.next != null) {  
                curNew = curNew.next;  
            }  
            curNew.next = cur;  
        }  
  
    }  
  
    private double judgeLoadFactor() {  
        return this.size * 1.0 / array.length;  
    }  
  
    //获得元素  
    public V getVal(K key) {  
        int index = key.hashCode() % array.length;  
        Node<K,V> cur = array[index];  
        while(cur != null) {  
            if(cur.key.equals(key)) {  
                return cur.val;  
            }  
            cur = cur.next;  
        }  
       return null;  
    }  
}

在哈希桶中通过调整负载因子来降低冲突率。需要注意的是扩容调节负载因子的时候，我们应该将原数组的每个元素重新哈希，因为数组大小变化对应计算出来的哈希值也会发生变化。
在这里插入图片描述

2. `HashMap`和`HashSet`（参照Map和Set）

HashSet 和 HashMap 是 Java 集合框架中的两个重要类，它们都基于哈希表（Hash Table）实现，在很多方面存在相同的特性，但是也保有各自一定的特点

2.1 `HashMap`

HashMap是一个实现Map接口的类，它是一个提供了键值对（key-value模型）存储信息的数据结构，HashMap的底层用到哈希桶，有别于搜索树，所以HashMap中可以插入不能比较大小的数据。

方法	介绍
V get(Object key)	返回 key 对应的 value
V put(K key, V value)	将Key和Value作为键值对，添加到Map中
boolean containsKey(Object key)	如果Map中存在key则返回true
V getOrDefault(Object key, V defaultValue)	如果Map中有关于key对应的value 则返回Map中的value, 否则返回默认设置的value
Set<Map.Entry<K,V>> entrySet()	返回一个set集合，里面的元素是Map.Entry<K, V>
#`Map.Entry<K,V>`:Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

方法	介绍
K getKey()	获得entry 中的 key
V getValue()	获得entry 中的 value

import java.util.HashMap;  
import java.util.Map;  
  
public class Test {  
    public static void main(String[] args) {  
        Map<String, Integer> hashMap = new HashMap<>();  
  
        //put（Key,Value）存放键值对Key-Value    
        //Key在这里是String类型的name    
        //Value在这里是Integer类型的age    
System.out.println("-----put(Key,Value)....");  
        hashMap.put("张三", 18);  
        hashMap.put("李四", 22);  
        hashMap.put("王五", 21);  
  
        //get(Key)获取Key"王五"对应的Value年龄    
System.out.println("-----get(Key)....");  
        Integer age = hashMap.get("王五");  
        System.out.println(age);  
  
        //查看treeMap里是否有"李四"    
System.out.println("-----containsKey(Object key)....");  
        boolean ret = hashMap.containsKey("李四");  
        System.out.println(ret);  
  
        //getOrDefault(Object key, V defaultValue)    
System.out.println("-----getOrDefault(Object key , V defaultValue)....");  
        System.out.println(hashMap.getOrDefault("张三", 20));  
        System.out.println(hashMap.getOrDefault("钱七", 20));  
  
        //将treeMap转化为一个Set集合    
//获取Entry对象，然后获取key和value    
System.out.println("-----Set<Map.Entry<K,V>> entrySet()....");  
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {  
            System.out.println("Key == " + entry.getKey() + "   Value == " + entry.getValue());  
        }  
  
    }  
}

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

HashMap的特点：

无序性：HashMap中的元素没有特定的顺序，迭代时的顺序并不反映插入时的顺序。
扩容：随着元素的增加，HashMap会自动扩容来维持其性能，通过重新哈希所有元素到更大的数组中实现。
时间复杂度：平均情况下，HashMap插入、删除和查找操作的时间复杂度为O(1)。

2.2 `HashSet`

Java中的HashSet是一个实现了Set接口的集合类，Set是天然去重的，也就是说我们可以利用Set来完成我们的去重操作。

方法	解释
boolean add(E e)	添加集合中不存在元素，重复元素不会被添加成功
boolean contains(Object o)	判断 o 是否在集合中
Iterator< E > iterator()	返回迭代器对象
boolean remove(Object o)	删除集合中的 o
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
void clear()	清空集合
int size()	返回set中元素的个数

import java.util.*;  
  
public class Test {  
    public static void main(String[] args) {  
        Set<String> hashSet = new HashSet<>();  
  
        //add（Key）添加元素  
        System.out.println("-----add(Key).....");  
        hashSet.add("张三");  
        hashSet.add("李四");  
        hashSet.add("王五");  
        hashSet.add("钱七");  
  
        //remove(Key)删除元素 "张三"  
        System.out.println("-----remove(Key).....");  
        hashSet.remove("张三");  
  
        //是否包含元素 "钱七"  
        System.out.println("-----contains(Key).....");  
        boolean isContain = hashSet.contains("钱七");  
        System.out.println("是否包含元素钱七: " + isContain);  
  
        //集合是否为null  
        System.out.println("-----isEmpty().....");  
        boolean empty = hashSet.isEmpty();  
        System.out.println("集合是否为空: " + empty);  
  
        //得到集合元素个数  
        System.out.println("-----size().....");  
        int size = hashSet.size();  
        System.out.println("元素个数: " + size);  
  
        //迭代器遍历得到Set集合内容  
        System.out.println("-----iterator().....");  
        System.out.print("集合里面的元素:");  
        Iterator<String> iterator = hashSet.iterator();  
        while (iterator.hasNext()) {  
            System.out.print(iterator.next() + " ");  
        }  
        System.out.println();  
  
        //删除所有元素  
        System.out.println("-----clear().....");  
        hashSet.clear();  
    }  
}

运行结果如下：
在这里插入图片描述

HashSet的特点：

无序性：每次遍历HashSet时，元素的顺序可能不同。这是因为HashSet在内部使用哈希表，元素的存储位置由其哈希值决定。
允许null值：HashSet允许存储一个null元素
Set的集合中不包含重复的元素
HashSet中不同于TreeSet，插入的元素不要求能够比较大小，因为HashSet的底层是哈希桶，而TreeSet的底层是搜索树

原文地址：https://blog.csdn.net/2302_79249715/article/details/142825309

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：JAVA如何读取OPC点位数据
下一篇：MedMamba代码解释及用于糖尿病视网膜病变分类

力扣前缀和
找子数组的个数了解前缀和的基础。
阅读更多2024-10-11
【金九银十】笔试通关 + 小学生都能学会的插入排序
插入排序的起源可以追溯到早期计算机科学的发展。它是一种古老且基本的排序算法，其基本思想可以追溯到手工排序的方法。最早的文献中并没有详细说明插入排序的发明者，但它在各种早期的计算机排序算法中被广泛使用。
阅读更多2024-10-11
rabbitmq死信队列详解与使用
死信队列是一个特殊的队列，用于存储那些无法被正常消费的消息。这些消息通常会被转移到死信队列中，以便后续处理、审查或重新入队。
阅读更多2024-10-11
Linux中的chown命令详解
命令是改变文件或目录所有者和组的常用工具。它允许用户或管理员重新分配文件和目录的所有权，以适应不同的使用场景和安全需求。在Linux系统中，文件和目录的权限管理是保证系统安全的重要环节。不存在，此命令
阅读更多2024-10-11
DVWA | DVWA 靶场初识
DVWA（Damn Vulnerable Web Application）是一个 PHP/MySQL 的 Web 应用程序，它被故意设计成包含多种安全漏洞，以便为网络安全专业人员、开发人员和学生提供一
阅读更多2024-10-11
机器学习：神经网络与深度学习的原理、应用场景及优缺点
深度学习是机器学习的一个分支领域，它通过构建具有多个层次的神经网络来自动学习数据的特征表示。神经网络是深度学习的基本模型结构，模拟了生物神经元之间的信息传递方式。
阅读更多2024-10-11
The 2024 ICPC Kunming Invitational Contest K. Permutation（交互期望）
维护两个vector L、R，代表下一步要在[l,mid]和[mid+1,r]分治的vector。这样del里的元素，在并查集上找到其祖先时，可以用to数组确定其应该被放进L还是R。每次将x rand
阅读更多2024-10-11
ubuntu22.04 安装wine9.0 全网首发
博主按照这种方式是失败的，虽然开启了“低调上网”，貌似代理对于终端不起作用，后面会介绍替代方案，一样完美。
阅读更多2024-10-11
SpringMVC Controller返回值技巧：ModelAndView vs String的实战对比
ModelAndView 和String 作为返回值在SpringMVC中的区别
阅读更多2024-10-11
C# 中 List、ArrayList 和数组的区别
C# 中的数组、ArrayList 和 List 在存储方式、功能特性和适用场景上存在着明显的区别。数组具有固定大小和类型安全的特点，适用于已知固定数量的元素和对性能要求极高的场景；ArrayList
阅读更多2024-10-11

HashMap和HashSet

前言

1. 哈希表

1.1 冲突

1.2 冲突的避免

1.3 冲突的解决(降低冲突率)

2. HashMap和HashSet（参照Map和Set）

2.1 HashMap

2.2 HashSet

相关文章

2. `HashMap`和`HashSet`（参照Map和Set）

2.1 `HashMap`

2.2 `HashSet`