【java数据结构】HashMap和HashSet

目录

一.认识哈希表：

1.1什么是哈希表？

之前的学习中，如果我们要查找一个元素，肯定是要经过比较的，那有没有一种办法，可以不用经过比较，直接就能拿到呢？

如果我们能构造一种存储结构，通过一种函数 (hashFunc) 使元素的存储位置与函数得出的关键码之间能够建立一一映射的关系，那么在查找某个元素的时候，就能通过这个函数来很快的找到该元素所在的位置。

🐻🐻🐻这种函数就叫做哈希(散列)函数，上述所说构造出来的结构，叫做哈希表或者称为散列表。

 哈希表简介：

哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

1.2哈希表的表示： 

 举个栗子：为了记录一个班的学生的信息，分别包括学号和姓名。我们就可以用哈希表（数组加链表）来记录，这里学号(关键值key)通过哈希函数得到一个数组下标，这个下标就是这个学生信息存放在对应数组中的位置，同时学生的信息（姓名和学号）叫做键值对，又称作Entry

 使用方法：

• 🦉🦉🦉向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
• 🦉🦉🦉在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。
• 🦉🦉🦉实现哈希表： 数组+链表 或者  数组+二叉树

1.3常见哈希函数：

• 🐞直接定值法–（常用）：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况
• . 🐞除留余数法–-(常用) ： 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
• 例如：

 二.认识HashMap和HashSet:

 HashMap和HashSet是Java集合框架中的两个常用类，它们都实现了Set接口，但在实现原理和用途上有一些区别。

• HashMap:HashMap是基于哈希表的实现，它使用键值对（key-value）的方式存储数据。HashMap允许存储null键和null值，并且可以存储重复的值，但不允许重复的键。HashMap内部使用哈希函数将键映射到哈希表的索引位置，以实现快速的插入、删除和查找操作。HashMap的查找操作是通过键来进行的，因此可以根据键快速地获取对应的值。
• HashSet:HashSet也是基于哈希表的实现，它存储唯一的元素，不允许重复值。HashSet允许存储null值，但只能存储一个null元素。HashSet内部使用哈希函数将元素映射到哈希表的索引位置，以实现快速的插入、删除和查找操作。HashSet的查找操作是通过元素来进行的，因此可以根据元素快速地判断是否存在于集合中。

2.1关于Map.Entry<K, V>的说明:

🧐🧐🧐Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了 <key, value>的获取，value的设置以及Key的比较方式。

注意：Map.Entry<K,V>并没有提供设置Key的方法

2.2Map常用方法说明：

2.3HashMap的使用案例：

基础操作：

Map<String, String> m = new HashMap<>();
        // put(key, value):插入key-value的键值对
        // 如果key不存在，会将key-value的键值对插入到map中,返回null
        m.put("林冲", "豹子头");
        m.put("鲁智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及时雨");
        String str = m.put("李逵", "黑旋风");
        m.remove("武松","行者");

        System.out.println("map的大小（size）：" + m.size());
        System.out.println("map中的元素：" + m);

        System.out.println("这时str为空： " + str);// put(key,value): 注意key不能为空，但是value可以为空
        m.put("无名", null);      // key如果为空，会抛出空指针异常
        System.out.println("当前map的大小： " + m.size());

        str = m.put("李逵", "铁牛");
        System.out.println("返回旧的value值： " + str);
        System.out.println("得到Key所对应的value值: " + m.get("李逵"));

运行结果：

GetOrDefault()和containKey(key)：

//GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println("=========================================");
        System.out.println("李逵存在，返回key对应的value： " + m.getOrDefault("李逵", "牛牛"));
        System.out.println("史进不存在，返回一个默认值： " + m.getOrDefault("史进", "九龙纹"));
        System.out.println("=========================================");
        //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        System.out.println(m.containsValue("豹子头"));
        System.out.println(m.containsValue("行者"));

运行结果：

三种遍历方法：

System.out.println("-----key ------value -----Entry的遍历方法：----------");
        System.out.println("key遍历:  ");
        for (String s : m.keySet()) {
            System.out.print(s + " ");
        }
        System.out.println();
        System.out.println("value遍历:  ");
        for (String s : m.values()) {
            System.out.print(s + " ");
        }
        System.out.println();
        System.out.println("entry遍历: ");
        for (Map.Entry<String, String> entry : m.entrySet()) {
            System.out.println(entry.getKey() + "--->" + entry.getValue());
        }

运行结果：

注意：

1. 😺Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap2. 😺Map中存放键值对的Key是唯一的，value是可以重复的3. 😺Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。4. 😺Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。5. 😺Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

2.4Set常见方法说明：

 2.5HashSet使用案例：

System.out.println("================HashSet===============");
        Set<String> s = new HashSet<>();
        boolean isIn = s.add("apple");
        s.add("orange");
        s.add("peach");
        s.add("banana");
        System.out.println(s.size());
        System.out.println(s);
        System.out.println("add(key): 如果key不存在，则插入，返回true: " + isIn);
        isIn = s.add("apple");
        System.out.println("add(key):如果key存在，则返回false: " + isIn);
        // contains(key): 如果key存在，返回true，否则返回false
        System.out.println(s.contains("apple"));
        System.out.println(s.contains("watermelen"));
        s.remove("apple");// remove(key): key存在，删除成功返回true
        System.out.println(s);// key不存在，删除失败返回false , key为空，
        System.out.println("迭代器遍历：");
        Iterator<String> it = s.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }

运行结果：

注意：

1.🐳 Set是继承自Collection的一个接口类2.🐳 Set中只存储了key，并且要求key一定要唯一 3. 🐳Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的4.🐳 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。5.🐳 Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入6. 🐳Set中不能插入null的key

源码：

import java.util.TreeMap;
import java.util.Set;
import java.util.Map;

public class Test1 {

    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        // put(key, value):插入key-value的键值对
        // 如果key不存在，会将key-value的键值对插入到map中,返回null
        m.put("林冲", "豹子头");
        m.put("鲁智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及时雨");
        String str = m.put("李逵", "黑旋风");
        m.remove("武松","行者");

        System.out.println("map的大小（size）：" + m.size());
        System.out.println("map中的元素：" + m);

        System.out.println("这时str为空： " + str);// put(key,value): 注意key不能为空，但是value可以为空
        m.put("无名", null);      // key如果为空，会抛出空指针异常
        System.out.println("当前map的大小： " + m.size());

        str = m.put("李逵", "铁牛");
        System.out.println("返回旧的value值： " + str);
        System.out.println("得到Key所对应的value值: " + m.get("李逵"));
        //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println("=========================================");
        System.out.println("李逵存在，返回key对应的value： " + m.getOrDefault("李逵", "牛牛"));
        System.out.println("史进不存在，返回一个默认值： " + m.getOrDefault("史进", "九龙纹"));
        System.out.println("=========================================");
        //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        System.out.println(m.containsValue("豹子头"));
        System.out.println(m.containsValue("行者"));

        System.out.println("-----key ------value -----Entry的遍历方法：----------");
        System.out.println("key遍历:  ");
        for (String s : m.keySet()) {
            System.out.print(s + " ");
        }
        System.out.println();
        System.out.println("value遍历:  ");
        for (String s : m.values()) {
            System.out.print(s + " ");
        }
        System.out.println();
        System.out.println("entry遍历: ");
        for (Map.Entry<String, String> entry : m.entrySet()) {
            System.out.println(entry.getKey() + "--->" + entry.getValue());
        }

        System.out.println("================HashSet===============");
        Set<String> s = new HashSet<>();
        boolean isIn = s.add("apple");
        s.add("orange");
        s.add("peach");
        s.add("banana");
        System.out.println(s.size());
        System.out.println(s);
        System.out.println("add(key): 如果key不存在，则插入，返回true: " + isIn);
        isIn = s.add("apple");
        System.out.println("add(key):如果key存在，则返回false: " + isIn);
        // contains(key): 如果key存在，返回true，否则返回false
        System.out.println(s.contains("apple"));
        System.out.println(s.contains("watermelen"));
        s.remove("apple");// remove(key): key存在，删除成功返回true
        System.out.println(s);// key不存在，删除失败返回false , key为空，
        System.out.println("迭代器遍历：");
        Iterator<String> it = s.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！