【HashMap和HashSetyi以及散列表的拉链法，线性探测法详解】
🌈个人主页：SKY-30
⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
⚡学好数据结构，刷题刻不容缓：点击一起刷题
🌙心灵鸡汤：总有人要赢，为什么不能是我呢
📢📢📢Map 和Set 概念
map和set是一种用来搜索的数据结构，其搜索效率与具体实例化的子类有关，之前我们搜索的方法有：
- 直接遍历：利用for循环，暴力求解，事件复杂度为O(N)
- 二分查找：时间复杂度：O(logN),搜索之前要求序列是有序的
但是如果我们对于存储的数据，经常要执行修改和删除的操作，那么上述的两种操作就非常不适合了，我们这里就引出两个新的数据结构-map和set。
📢📢📢模式
对于map来说，它的存储形式是形如K-（key），V-（value），这种类似于键值对的这种形式，进行存储，而set，则是只有key这一种形式。
📢📢📢Map
Map是一个接口，没有继承collection，该类的存储形式是并且这里的K是唯一的，不能重复。
📢📢📢Map.Entry
Map.Entry是Map内部用来存放键值对的映射关系的一个内部类，该类提供了获取，value的设置，即Key的比较形式
方法 解释 K getKey() 返回 entry中的key V getValue 返回entry中的value V setValue 将键值对中的value替换为指定的value 📢📢📢Map的一些常用方法
📢📢📢Map的一些注意事项
- Map是一个接口，不能直接实例化对象，如果要实例化，我们只能实例实现其接口的类，TreeMap和HashMap。
- Map中Key的元素是唯一的，Value可以重复的
- 在Treemap中插入元素时，Key不能为空，否则会报错，value却可以为空，需要注意在HashMap中是可以插入为空的
- Map中的Key是不能修改的，要想修改的话，只能删除对应的数据，然后重新插入，但是Value是可以重新修改的。
- Treemap和HashMap的区别，这个后面说
import java.util.TreeMap; import java.util.Map; public static void TestMap(){ Map m = new TreeMap(); // put(key, value):插入key-value的键值对 // 如果key不存在，会将key-value的键值对插入到map中,返回null m.put("林冲", "豹子头"); m.put("鲁智深", "花和尚"); m.put("武松", "行者"); m.put("宋江", "及时雨"); String str = m.put("李逵", "黑旋风"); System.out.println(m.size()); System.out.println(m); // put(key,value): 注意key不能为空，但是value可以为空 // key如果为空，会抛出空指针异常 //m.put(null, "花名"); str = m.put("无名", null); System.out.println(m.size()); // put(key, value): // 如果key存在，会使用value替换原来key所对应的value，返回旧value str = m.put("李逵", "铁牛"); // get(key): 返回key所对应的value // 如果key存在，返回key所对应的value // 如果key不存在，返回null System.out.println(m.get("鲁智深")); System.out.println(m.get("史进")); //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值 System.out.println(m.getOrDefault("李逵", "铁牛")); System.out.println(m.getOrDefault("史进", "九纹龙")); System.out.println(m.size()); //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN) // 按照红黑树的性质来进行查找 // 找到返回true，否则返回false System.out.println(m.containsKey("林冲")); System.out.println(m.containsKey("史进")); // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N) // 找到返回true，否则返回false System.out.println(m.containsValue("豹子头")); System.out.println(m.containsValue("九纹龙")); // 打印所有的keyfor(String s : m.keySet()){ System.out.print(s + " "); } System.out.println(); // 打印所有的value // values()是将map中的value放在collect的一个集合中返回的 for(String s : m.values()){ System.out.print(s + " "); } System.out.println(); // 打印所有的键值对 // entrySet(): 将Map中的键值对放在Set中返回了 for(Map.Entry entry : m.entrySet()){ System.out.println(entry.getKey() + "--->" + entry.getValue()); } System.out.println(); } // keySet是将map中的key防止在Set中返回的 }
📢📢📢Set-详解
Set与Map很大的一个不同就是Set继承了collection而map并没有。
⚡⚡⚡一些常见的方法
⚡⚡⚡针对Set的一些注意事项
- Set是继承了collection的一个接口类
- Set中只存储了Key，并且要求他是唯一的，不能重复
- Set的最大的一个特点就是对数据去重。
- 实现Set接口的两个常见的类是HashSet和Treemap
- TreeSet中的key不能插入null,HashSet则可以插入null
- 在这里插入代码片
import java.util.TreeSet; import java.util.Iterator; import java.util.Set; public static void TestSet(){ Set s = new TreeSet(); // add(key): 如果key不存在，则插入，返回ture // 如果key存在，返回false boolean isIn = s.add("apple"); s.add("orange"); s.add("peach"); s.add("banana"); System.out.println(s.size()); System.out.println(s); boolean isIn= s.add("apple"); // add(key): key如果是空，抛出空指针异常 //s.add(null); // contains(key): 如果key存在，返回true，否则返回false System.out.println(s.contains("apple")); System.out.println(s.contains("watermelen")); // remove(key): key存在，删除成功返回true // key不存在，删除失败返回false // key为空，抛出空指针异常 s.remove("apple"); System.out.println(s); s.remove("watermelen"); System.out.println(s); Iterator it = s.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); }
📢📢📢哈希表
不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
- 当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功！！！
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)
⚡⚡⚡冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
如何解决哈希碰撞呢，这里几种不同的方法给大家具体说明一下。
⚡⚡⚡解决哈希冲突的及汇总方法
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见的哈希函数：
除留余数法：
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p private static class Node { private int key; private int value; 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 int put(int key, int value) { int index = key % array.length; // 在链表中查找 key 所在的结点 // 如果找到了，更新 // 所有结点都不是 key，插入一个新的结点 for (Node cur = array[index]; cur != null; cur = cur.next) { if (key == cur.key) { int oldValue = cur.value; cur.value = value; return oldValue; } } Node node = new Node(key, value); node.next = array[index]; array[index] = node; size++; if (loadFactor() = LOAD_FACTOR) { resize(); } return -1; } private void resize() { Node[] newArray = new Node[array.length * 2]; for (int i = 0; i
⚡⚡⚡关于HashMap和HashSet的注意事项
- HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set
- java 中使用的是哈希桶方式解决冲突的
- java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）
- java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方
法，而且要做到 equals 相等的对象，hashCode 一定是一致的。
- 当向该结构中：
