海南哪家公司做网站做的好,如何用书签 做网站接口,国外网站建设 网站,wordpress纯html静态#x1f512;文章目录#xff1a;
1.❤️❤️前言~#x1f973;#x1f389;#x1f389;#x1f389;
2. Map和Set的基础概念
3.Map的基础使用 4.Set的基础使用
5. TreeMap的本质——红黑树 5.1二叉搜索树的概念
5.2二叉搜索树的模拟实现
二叉搜索树——查找 二…文章目录
1.❤️❤️前言~
2. Map和Set的基础概念
3.Map的基础使用 4.Set的基础使用
5. TreeMap的本质——红黑树 5.1二叉搜索树的概念
5.2二叉搜索树的模拟实现
二叉搜索树——查找 二叉搜索树——添加 二叉搜索树——删除
总代码及测试
5.3 二叉搜索树的性能分析
5.4TreeMap的本质——红黑树
6.TreeMap的高阶使用
7.HashMap的本质——哈希桶
7.1哈希表的概念
7.2哈希冲突的概念
7.3哈希冲突的避免 哈希冲突的避免——哈希函数设计 哈希冲突的避免——负载因子调节
7.4哈希冲突的解决 哈希冲突的解决——闭散列
哈希冲突的解决——哈希桶开散列
7.5模拟一个简易的哈希桶实现map一些功能 插入
扩容
查找
总代码及测试 7.6 hashCode方法和equals方法
7.7 HashMap的模拟实现该哈希桶可存放任意类型
7.8 HashMap的性能分析
8.HashMap的高阶使用
9.TreeMap和HashMap的区别
10.TreeSet和HashSet的本质TreeSet和HashSet的区别
11.总结 1.❤️❤️前言~ Hello, Hello~ 亲爱的朋友们这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章请别吝啬你的点赞❤️❤️和收藏。如果你对我的内容感兴趣记得关注我以便不错过每一篇精彩。 当然如果在阅读中发现任何问题或疑问我非常欢迎你在评论区留言指正️️。让我们共同努力一起进步 加油一起CHIN UP 个人主页E绵绵的博客 所属专栏 1. JAVA知识点专栏 深入探索JAVA的核心概念与技术细节 2.JAVA题目练习 实战演练巩固JAVA编程技能 3.c语言知识点专栏 揭示c语言的底层逻辑与高级特性 4.c语言题目练习 挑战自我提升c语言编程能力 持续更新中敬请期待❤️❤️ 这篇文章就给大家带来map和set的详细讲解同时还会讲解搜索树和哈希表的概念超级详细uu们可以认真观看下~ 2. Map和Set的基础概念 Map和Set是一种专门用来进行搜索的容器或者数据结构它的搜索效率与其具体的实例化例子有关。 Map和Set是动态查找相比较与静态查找比如直接查找。二分查找等其优点是可以在查找过程中对区间进行一些插入和删除的操作。 一般把搜索的数据称为关键字Key把关键字对应的称为值Value将其称为Key-value的键值对一般模型有两种 1. 纯 key 模型Set中存储的就是key 比如查找 某本书中是否有一个名词 2. Key-Value模型Map中存储的就是key-value的键值对 比如统计 某本书中某几个名词出现的次数 下面我们展示下在集合框架中的Map和Set 这里我们可知map和set都是接口实例化对象可以是HashMap和TreeSetHashMap和HashSet那么肯定会有人有疑问了它们两有什么区别呢别急它们本质是不同的区别很大待我后面叙叙道来~ 3.Map的基础使用 Map是一个接口类该类没有继承自Collection该类中存储的是结构的键值对并且K一定是唯一的不能重复。 以下是Map的常用方法 这里需要注意一些点 1.Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap它们两存在区别后面会讲~。 2. Map中存放键值对的Key是唯一的value是可以重复的所以用put放入同样的key那就会覆盖之前的key的value。 3. get能够将put放入的key和Value都打印出来如果没有就打印null getOrDefault能够能够设置一个默认的key的value如果之前没有put这个默认的key那就打印出这个key和设置的value 4.在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。关于这点可能大家现在还理解不了等到这篇文章后面讲述它们的本质时大家就会懂了 5. Map中的Key可以通过keySet全部分离出来存储到Set中来进行访问(因为Key不能重复)。 6. Map中的value可以通过values全部分离出来存储在Collection的任何一个子集合中(value可能有重复)。 7. Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入。 8.Map里面重写了toString所以用println直接打印map可以打印出其内部的内容。 9.在这些方法中entrySet是个很重要的方法SetMap.EntryK, V entrySet() 返回所有的 key-value 映射关系Entry是Map接口中的内部接口所以才用Map.Entryk,v表示, Map.Entry 作为Map内部实现的用来存放键值对映射关系的内部接口该内部接口中主要提供了key 的获取value的获取value的设置。 注意这个知识点很重要以后做题时可能都会用到。 以下是Map的基础使用代码还请认真观看 public class Test1 {public static void main(String[] args) {MapString, Integer map new TreeMap();map.put(key, 25);System.out.println(map.get(key));System.out.println(map.getOrDefault(key, 15));map.put(key, 35);System.out.println(map.get(key));System.out.println(map.getOrDefault(key, 15));map.remove(key);System.out.println(map.get(key));System.out.println(map.getOrDefault(key, 15));map.put(a, 3);map.put(b, 4);map.put(c, 5);map.put(d, 6);map.put(e, 7);map.put(f, 7);map.put(g, 6);SetString set map.keySet();System.out.println(set);CollectionInteger collection map.values();System.out.println(collection);System.out.println(map);System.out.println(map.containsKey(e));System.out.println(map.containsValue(6));SetMap.EntryString, Integer set1 map.entrySet();for (Map.EntryString,Integer entry:set1){entry.setValue(10);System.out.print(entry.getKey() entry.getValue());System.out.println();}// map.put(null,null); 报错MapString, Integer map1 new HashMap();map1.put(null, null);}
}4.Set的基础使用 Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。 以下是Set的常用方法 注意 1. Set是继承自Collection的一个接口类 2. Set中只存储了key并且要求key一定要唯一 3. Set最大的功能就是对集合中的元素进行去重 4. 实现Set接口的常用类有TreeSet和HashSet 5. Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入 6. TreeSet中不能插入null的keyHashSet可以之所以这样后面讲到其本质时会讲到。 对于这些方法都很简单我们就不一一讲述了直接上其方法的使用代码 public class Test2 {public static void main(String[] args) {SetString set new TreeSet();set.add(a);set.add(b);set.add(c);set.add(d);set.add(e);set.add(f);set.add(g);System.out.println(set.size());System.out.println(set.isEmpty());set.remove(a);System.out.println(set.contains(b));System.out.println(set);ArrayListString arrayList new ArrayList();arrayList.add(k);arrayList.add(t);arrayList.add(t);arrayList.add(t);arrayList.add(t);System.out.println(set.containsAll(arrayList));set.addAll(arrayList);System.out.println(set);set.clear();System.out.println(set);//set.add(null);报错SetString set1 new HashSet();set1.add(null);}
} 5. TreeMap的本质——红黑树 下面我们要了解红黑树就要先了解二叉搜索树这个概念因为准确来说红黑树是一颗高级的二叉搜索树。 5.1二叉搜索树的概念 二叉搜索树又叫二叉排序树它或者是一棵空树或者是具有下列性质的二叉树 1 若它的左子树不空则左子树上所有结点的值均小于它的根节点的值 2若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 3它的左、右子树也分别为二叉搜索树。 二叉搜索树作为一种经典的数据结构它既有链表的快速插入与删除操作的特点又有数组快速查找的优势。主要用于在文件系统和数据库系统中一般会采用这种数据结构进行高效率的排序与检索操作。 并且在二叉搜索树给它进行中序遍历他是顺序递增的。 为了对二叉搜索树有更加深刻的认识我们等会会对其进行模拟一颗二叉搜索树。 5.2二叉搜索树的模拟实现 先根据二叉搜索树写出它的结构 public class SearchTree {class Node{int value;Node left;Node right;public Node(int value) {this.value value;}}Node root; 接着我们模拟其二叉搜索树的各个方法。 二叉搜索树——查找 根据这图我们能设计出以下代码 //搜索树的查找public boolean search(int key){Node curroot;while(cur!null){if(cur!nullcur.valuekey)curcur.left;if (cur!nullcur.valuekey)curcur.right;if(cur!nullcur.valuekey)return true;}return false;} 二叉搜索树——添加 根据这图我们能设计出以下代码 //搜索树的添加public void add(int key){Node curroot;if(curnull) {root new Node(key);return;}Node parentnull;while(cur!null){parentcur;if(cur!nullcur.valuekey)curcur.left;if (cur!nullcur.valuekey)curcur.right;}if(parent.valuekey)parent.leftnew Node(key);if (parent.valuekey)parent.rightnew Node(key);} 二叉搜索树——删除 这个比较复杂分为三种情况。 设待删除结点为 cur其中有两个双亲结点。 1要删除结点如果一边为null一边不为null的情况 2下面分析一下两边都不为空的情况 需要使用替换法进行删除。 替换法的核心是找到删除节点左子树中的最大值即子树中的最右节点这个节点一定没有右右子树或者删除节点右子树中的最小值即子树中的最左节点这个节点一定没有左子树用它的值填补到被删除节点中再来处理该结点的删除问题。 以下讲解使用替换删除节点右子树的最小节点 首先找到最小节点tmp以及最小节点的父亲tmpPrev如图所示结构紧着cur.val tmp.val替换值然后删除tmp节点删除步骤如图所示即tmpPrev.left tmp.right。 值得注意的是有一种情况会被忽略即当cur.right 节点无左子树时此时tmpPrev仍然是cur而tmp即为cur.right此时删除tmp节点的步骤就变为了tmpPrev.right tmp.right 所以根据这种思路可以设计出以下代码 //搜索树的删除public boolean remove(int key){Node curroot;Node parentnull;while(cur!null){if(cur!nullcur.valuekey){parentcur;curcur.left;}if (cur!nullcur.valuekey){parentcur;curcur.right;}if (cur!nullcur.valuekey)break;}if (curnull)return false;if(cur.leftnull){if(rootcur)rootroot.right;if(parent.rightcur)parent.rightcur.right;if (parent.leftcur)parent.leftcur.right;return true;}if(cur.rightnull){if(rootcur)rootroot.left;if(parent.rightcur)parent.rightcur.left;if (parent.leftcur)parent.leftcur.left;return true;}if(cur.right!nullcur.left!null){Node minParentParentnull;Node mincur.right;Node minParentcur;while(min!null){minParentParentminParent;minParentmin;minmin.left;}int tmpminParent.value;minParent.valuecur.value;cur.valuetmp;if(minParentminParentParent.right)minParentParent.rightminParent.right;elseminParentParent.leftminParent.right;}return true;}
} 总代码及测试 public class SearchTree {class Node{int value;Node left;Node right;public Node(int value) {this.value value;}}Node root;//搜索树的查找public boolean search(int key){Node curroot;while(cur!null){if(cur!nullcur.valuekey)curcur.left;if (cur!nullcur.valuekey)curcur.right;if(cur!nullcur.valuekey)return true;}return false;}//搜索树的添加public void add(int key){Node curroot;if(curnull) {root new Node(key);return;}Node parentnull;while(cur!null){parentcur;if(cur!nullcur.valuekey)curcur.left;if (cur!nullcur.valuekey)curcur.right;}if(parent.valuekey)parent.leftnew Node(key);if (parent.valuekey)parent.rightnew Node(key);}//搜索树的删除public boolean remove(int key){Node curroot;Node parentnull;while(cur!null){if(cur!nullcur.valuekey){parentcur;curcur.left;}if (cur!nullcur.valuekey){parentcur;curcur.right;}if (cur!nullcur.valuekey)break;}if (curnull)return false;if(cur.leftnull){if(rootcur)rootroot.right;if(parent.rightcur)parent.rightcur.right;if (parent.leftcur)parent.leftcur.right;return true;}if(cur.rightnull){if(rootcur)rootroot.left;if(parent.rightcur)parent.rightcur.left;if (parent.leftcur)parent.leftcur.left;return true;}if(cur.right!nullcur.left!null){Node minParentParentnull;Node mincur.right;Node minParentcur;while(min!null){minParentParentminParent;minParentmin;minmin.left;}int tmpminParent.value;minParent.valuecur.value;cur.valuetmp;if(minParentminParentParent.right)minParentParent.rightminParent.right;elseminParentParent.leftminParent.right;}return true;}
}public class Test {public static void main(String[] args) {SearchTree searchTreenew SearchTree();searchTree.add(10);searchTree.add(13);searchTree.add(12);searchTree.add(11);searchTree.add(2);searchTree.add(6);searchTree.add(1);searchTree.add(8);searchTree.add(5);searchTree.remove(11);searchTree.remove(1);searchTree.remove(13);searchTree.remove(6);searchTree.remove(2);searchTree.remove(8);System.out.println(searchTree.search(11));System.out.println(searchTree.search(12));System.out.println(searchTree.search(13));System.out.println(searchTree.search(10));System.out.println(searchTree.search(15));System.out.println(searchTree.search(1));System.out.println(searchTree.search(6));System.out.println(searchTree.search(2));System.out.println(searchTree.search(8));System.out.println(searchTree.search(5));}} 5.3 二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。比较次数越多证明其效率越低 所以 最优情况下二叉搜索树为完全二叉树其平均比较次数为 最差情况下二叉搜索树退化为单支树其平均比较次数为 所以如果退化成单支树二叉搜索树的性能就失去了而为了改进这一缺陷就有了AVL树。 AVL树是最先发明的自平衡二叉搜索树。在AVL树中任何节点的两个子树的高度最大差别为1所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 本篇博客的重点不在AVL树上因此不对AVL树进行展开讲解可自行搜索了解。 虽然AVL树已经很高效了但因为AVL树的翻转会经历很多次还是比较麻烦所以我们可以使其变的更高效那就是添加一些额外的颜色标记规则即每个节点被标记为红色或黑色这样翻转也就少了很多次更加高效了而这样的树就叫红黑树。 我们的TreeMap本质上就是红黑树 5.4TreeMap的本质——红黑树 对于红黑树如何模拟实现以及一些其他更多的细节这里我们就不过多讲述后面的文章会细讲。你现在只要知道TreeMap本质是红黑树就行。 因为本质是红黑树二叉搜索树在进行查找、插入和删除操作时会对Map中的key类进行compareTo比较从而确定新元素应该插入到哪个位置使其更加高效。 所以这样就带来一个问题如果一个key类没有重写compareTo方法没实施comparable接口就直接想要添加到TreeMap中那就会报错因为无法进行比较。所以我们的key类一定要实施comparable接口重写compareTo方法这样才能正常进行。对于包装类像StringInteger都自动实施了comparable接口无需担心我们要担心的往往都是自定义类 这也就能解释TreeMap为什么输入key为null的数据时会报错因为null跟其他类根本比较不了所以会直接报错。而HashMap本质为哈希桶无需比较所以可以输入key为null的数据。 6.TreeMap的高阶使用 那么在讲清楚本质后我们就带来TreeMap的高阶使用——当Map中的key为自定义类时我们去操作TreeMap的代码演示 //TreeMap的高阶使用对于TreeSet的高阶使用也是如此这里就不展示代码了
public class Test2 {public static void main(String[] args) {MapStudent1,Integer mapnew TreeMap();map.put(new Student1(123,456),25);map.put(new Student1(125,457),30);map.put(new Student1(123,456),80);map.put(new Student1(129,457),30);System.out.println(map.get(new Student1(123, 524)));map.remove(new Student1(123,25));System.out.println(map.get(new Student1(123, 524)));System.out.println(map.get(new Student1(129, 524)));System.out.println(map.containsKey(new Student1(125, 524)));}
}class Student1 implements ComparableStudent1{String id;String name;public Student1(String name, String id) {this.name name;this.id id;}Overridepublic int compareTo(Student1 o) {return o.name.compareTo(this.name);}
} 7.HashMap的本质——哈希桶 下面我们要知道哈希桶这个概念前要先知道哈希表这个概念。 7.1哈希表的概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( )搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若 关键码相等则搜索成功 该方式即为哈希方法哈希方法中使用的转换函数称为哈希函数构造出来的结构称为哈希表 例如数据集合{176459 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 我们发现用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快 那么现在出现了个问题按照上述哈希方式向集合中插入元素44会出现什么问题 会发生哈希冲突~ 7.2哈希冲突的概念 对于两个数据元素的关键字 和 (i ! j)有 ! 但有Hash( ) Hash( )即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 这个现象是很不好的往往会影响效率甚至结果。 7.3哈希冲突的避免 那我们应该怎么避免哈希冲突呢 首先我们需要明确一点由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的这就导致一个问题冲突的发生是必然的但我们能做的应该是尽量的降低冲突率。 哈希冲突的避免——哈希函数设计 引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则 1.哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1 之间 2.哈希函数计算出来的地址能均匀分布在整个空间中 3.哈希函数应该比较简单 常见哈希函数: 1. 直接定制法--(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单,均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 2. 除留余数法常用 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数 Hash(key) key% p(pm将关键码转换成哈希地址。(注意这个是我们最常用的哈希函数法) 除此之外还有平方取中法 折叠法 随机数法 数学分析法这些方法都不常用可以自行去网上了解一下这里就不多说了 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 哈希冲突的避免——负载因子调节 负载因子和冲突率的关系粗略演示 所以当冲突率达到一个无法忍受的程度时我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。所以一般当负载因子填入表中的个数/数组的长度大于等于0.75时我们就会将哈希表中的数组扩容并把之前已经填入表中的数再次全部重新填入扩容后的数组中。 7.4哈希冲突的解决 解决哈希冲突两种常见的方法是闭散列和开散列我们又常把开散列叫成哈希桶 哈希冲突的解决——闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢 1. 线性探测 比如上面的场景现在需要插入元素44先通过哈希函数计算哈希地址下标为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他 元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标 记的伪删除法来删除一个元素。 2. 二次探测 总而言之二次探测就是将线性探测每次向后探测的步长由 1 步变为 index 1*1、index 2*2、index 3*3、index 4*4 … 依次增加直到找到未被占用的地方为止. 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。 因此闭散列最大的缺陷就是空间利用率比较低而下面我们要讲的第二种方法哈希桶开散列相比于闭散列更加完美所以哈希桶是我们必须要重点掌握的方法。 哈希冲突的解决——哈希桶开散列 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 以下是哈希桶的特点 1.哈希桶由数组链表红黑树组成。 一般正常情况下是数组链表当链表的长度大于等于64的情况时链表就会转化为红黑树因为链表越长就会导致查询越慢而红黑树恰好解决这一问题。而如果不存在链表的长度大于等于64的情况时那又会变回来变为数组链表。 2.当哈希桶的负载因子填入表中的个数/数组的长度大于等于0.75时会对数组自动进行扩容把之前已经填入表中的数再次全部重新填入扩容后的数组中。 3.链表中的插入是用尾插法进行的相比头插法更高效安全 知道哈希桶以上特点我们就自己模拟一个简易的哈希桶去实现map的一些功能。
7.5模拟一个简易的哈希桶实现map一些功能 我们需要模拟的哈希桶如上其key属于int类型通过key%capacity去得到对应的哈希值地址位置。这是其核心纲领话不多说开始模拟吧~ 在写哈希桶的每个方法之前我们要把准备工作做好代码如下 public class HashBucket {public Node[] array new Node[10];public final double bound 0.75;public int size;static class Node {int key;int value;Node next;public Node(int key, int value) {this.value value;this.key key;}} 插入 以下为其步骤 定义索引(index): 使用取模运算符 % 计算给定键值(key)对数组长度的索引以便将元素插入到正确的存储位置。 遍历链表: 初始化当前节点 cur 为该索引处的元素。如果链表不为空就遍历链表直到找到对应的键或者到达链表的末尾。 a. 如果找到匹配的键则更新其值(value)并增加大小(size)然后跳出循环。 b. 如果遇到空节点(cur.next null)说明链表结束添加新节点并将size加一然后也跳出循环。 如果整个链表为空就直接添加新节点并增加size。 扩容检查: 当哈希表接近满载这里设置的阈值为0.75触发resize()方法扩容数组从而降低负载因子。 public void put(int key, int value) {int index key % this.array.length;Node cur;for(cur this.array[index]; cur ! null; cur cur.next) {if (cur.key key) {cur.value value;break;}if (cur.next null) {cur.next new Node(key, value);size;break;}}if (cur null) {this.array[index] new Node(key, value);size;}if (size * 1.0 / array.length 0.75) {this.resize();}}
扩容 注意resize的一些扩容细节 扩容后数组的长度会变为原本的两倍因此其中每个key值根据新的哈希函数的计算结果跟原来的计算结果可能会不同所以它们要全部重新填入到新的数组中在填入完后新的数组的引用要赋值给旧的数组的引用。 public void resize() {Node[] arrayNew new Node[2 * this.array.length];Node tmpnull;for(int i 0; i this.array.length; i) {for(Node node this.array[i]; node ! null; node tmp) {int newIndex node.key % arrayNew.length;Node newCurnull;for(newCur arrayNew[newIndex]; newCur ! null; newCur newCur.next) {if (newCur.next null) {newCur.next node;break;}}if (newCur null) {arrayNew[newIndex] node;}tmp node.next;node.next null;}}this.array arrayNew;}
查找 首先计算键 key 对数组长度取模的结果作为在数组中查找的起始位置。接着进入一个循环从当前位置 this.array[index] 开始逐个检查链表中的节点。如果找到一个节点其键等于给定的 key那么就返回对应的value值。如果遍历完整个链表都没有找到匹配的键说明该键不存在于当前哈希表中此时就打印一条消息“找不到对应的数”并返回 -1 表示请求的键未找到。 public int get(int key) {int index key % this.array.length;for(Node cur this.array[index]; cur ! null; cur cur.next) {if (cur.key key) {return cur.value;}}System.out.println(找不到对应的数);return -1;}
总代码及测试
public class HashBucket {public Node[] array new Node[10];public final double bound 0.75;public int size;static class Node {int key;int value;Node next;public Node(int key, int value) {this.value value;this.key key;}}public void put(int key, int value) {int index key % this.array.length;Node cur;for(cur this.array[index]; cur ! null; cur cur.next) {if (cur.key key) {cur.value value;break;}if (cur.next null) {cur.next new Node(key, value);size;break;}}if (cur null) {this.array[index] new Node(key, value);size;}if (size * 1.0 / array.length 0.75) {this.resize();}}public void resize() {Node[] arrayNew new Node[2 * this.array.length];Node tmpnull;for(int i 0; i this.array.length; i) {for(Node node this.array[i]; node ! null; node tmp) {int newIndex node.key % arrayNew.length;Node newCurnull;for(newCur arrayNew[newIndex]; newCur ! null; newCur newCur.next) {if (newCur.next null) {newCur.next node;break;}}if (newCur null) {arrayNew[newIndex] node;}tmp node.next;node.next null;}}this.array arrayNew;}public int get(int key) {int index key % this.array.length;for(Node cur this.array[index]; cur ! null; cur cur.next) {if (cur.key key) {return cur.value;}}System.out.println(找不到对应的数);return -1;}}
public class Test {public static void main(String[] args) {HashBucket hashBucket new HashBucket();hashBucket.put(10, 10);hashBucket.put(20, 5);hashBucket.put(30, 15);hashBucket.put(40, 25);hashBucket.put(50, 35);hashBucket.put(60, 45);hashBucket.put(70, 55);hashBucket.put(80, 65);hashBucket.put(43, 61);hashBucket.put(67, 32);System.out.println(hashBucket.get(43));System.out.println(hashBucket.get(50));System.out.println(hashBucket.get(67));System.out.println(hashBucket.get(70));}
} 7.6 hashCode方法和equals方法 在模拟了一个简易的哈希桶后我们就有个疑问了 既然哈希值地址位置是整数那么当我们的key类不为整形类时为String类或自定义类等一些其他类那么怎么确定key类的哈希值地址位置 为了解决这个问题Object类就存在一个hashCode方法它能返回一个基本类型的整数作为类的哈希值地址位置下面我们直接看下代码及测试结果。 public class Test {public static void main(String[] args) {Student student1new Student(10);Student student2new Student(10);System.out.println(student1.hashCode());System.out.println(student2.hashCode());}
}
class Student{int a;public Student(int a) {this.a a;}
} 由上我们发现在object类中的hashcode求出的哈希值是根据对象的地址去得出的而这样我们往往很难定位到对象所以一般情况下我们都会将hashCode重写使哈希值依据对象的某个成员值去得出这样能更加精确定位出对象。 这里我们的hashCode重写在idea中是可以用快捷键快速生成的如下是一个例子 随后我们可以选择哈希值以该类的什么成员为依据得出值这里我们选择成员b为依据对象当然也可以全选不过全选后只有当a和b的值都全部相等哈希值才能相等 public class Test {public static void main(String[] args) {Student student1new Student(10,25);Student student2new Student(30,25);System.out.println(student1.hashCode());System.out.println(student2.hashCode());}
}
class Student{int a;int b;public Student(int a,int b) {this.a a;this.bb;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return b student.b;}Overridepublic int hashCode() {return Objects.hashCode(b);}
} 所以我们现在就能搞清楚hashcode的机制了那这里又有个疑问在快捷键中hashcode为什么和equals是一块生成的两者为什么有联系 我们之前也模拟过哈希桶实现map的一些功能HashMap的主旨思想跟其类似其中不但会进行哈希值地址位置的生成还会对key类进行比较判断是否相等。计算哈希值是调用的类的hashCode 方法进行 key 的相等性比较是调用 key的equals方法所以就需要对hashcode和equals都进行重写并且还需注意hashcode所依据的类的成员必须跟equals所依据的类的成员一致这样才不会对结果产生干扰。所以在快捷键中它们是一块生成的~ 往往需要重写hashCode和equals的是自定义类包装类如String类已经给hashcode和equals重写好了 7.7 HashMap的模拟实现该哈希桶可存放任意类型 那么在了解完上面的知识点之后我们就能模拟出一个HashMap出来这跟我们之前模拟的一个简易哈希桶不同我们接下来要模拟的HashMap适用于任何类而之前的那个哈希桶只是针对于int类型较为简单,这个偏复杂,可存放任意类型。 这里的思路跟之前简易哈希桶的模拟一样就不多说了代码如下。 public class HashBucketk,v {public Node[] array new Node[10];public final double bound 0.75;public int size;static class Nodek,v {k key;v value;Node next;public Node(k key, v value) {this.value value;this.key key;}}public void put(k key, v value) {int key1 key.hashCode();int index key1 % this.array.length;Node cur;for(cur this.array[index]; cur ! null; cur cur.next) {if (cur.key.equals(key) ) {cur.value value;break;}if (cur.next null) {cur.next new Node(key, value);size;break;}}if (cur null) {this.array[index] new Node(key, value);size;}if (size * 1.0 / array.length 0.75) {this.resize();}}public void resize() {Node[] arrayNew new Node[2 * this.array.length]; Node tmpnull;for(int i 0; i this.array.length; i) {for(Node node this.array[i]; node ! null; node tmp) {int key1 node.key.hashCode();int newIndex key1 % arrayNew.length;Node newCurnull;for(newCur arrayNew[newIndex]; newCur ! null; newCur newCur.next) {if (newCur.next null) {newCur.next node;break;}}if (newCur null) {arrayNew[newIndex] node;}tmp node.next;node.next null;}}this.array arrayNew;}public Object get(k key) {int key1key.hashCode();int index key1 % this.array.length;for(Node cur this.array[index]; cur ! null; cur cur.next) {if (cur.key.equals(key)) {return cur.value;}}return null;}} 但我们还是要多说三个点 1.这里由于要适用任意类型所以用到了泛型更复杂了。 2.由于它适用任意类型所以在求哈希值时我们都是用hashCode求并不像之前简易的哈希桶因为只存放int类型所以可以不用hashcode就能求哈希值。 3.之前的模拟因为是存放int类型所以判断key相等时它们用号就行而我们是判断类是否相等所以必须用equals。 我们现在对其进行测试
public class Test {public static void main(String[] args) {HashBucketString,Integer hashBucket new HashBucket();hashBucket.put(a, 10);hashBucket.put(b, 5);hashBucket.put(c, 15);hashBucket.put(d, 25);hashBucket.put(e, 35);hashBucket.put(f, 45);hashBucket.put(g, 55);hashBucket.put(h, 65);hashBucket.put(i, 61);hashBucket.put(g, 32);System.out.println(hashBucket.get(a));System.out.println(hashBucket.get(i));System.out.println(hashBucket.get(g));System.out.println(hashBucket.get(e));System.out.println(hashBucket.get(t));System.out.println();HashBucketStudent,Integer hashBucket1new HashBucket();hashBucket1.put(new Student(123,123),40);hashBucket1.put(new Student(126,123),60);System.out.println(hashBucket1.get(new Student(123, 123)));System.out.println(hashBucket1.get(new Student(126, 123)));System.out.println(hashBucket1.get(new Student(126, 121)));}
}class Student{String id;String name;public Student(String name, String id) {this.name name;this.id id;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return Objects.equals(id, student.id) Objects.equals(name, student.name);}Overridepublic int hashCode() {return Objects.hash(id, name);}} 由上可知测试结果跟我们预想结果一模一样模拟成功~ 7.8 HashMap的性能分析 虽然哈希桶一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的 也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。 8.HashMap的高阶使用 那么在讲清楚本质后我们就带来HashMap的高阶使用——当Map中的key为自定义类时我们去操作HashMap的代码演示 //HashMap的高阶使用对于HashSet的高阶使用也是如此这里就不展示代码了
public class Test1 {public static void main(String[] args) {MapStudent,Integer mapnew HashMap();map.put(new Student(123,456),25);map.put(new Student(125,457),30);map.put(new Student(123,456),80);map.put(new Student(129,457),30);System.out.println(map.get(new Student(123, 524)));map.remove(new Student(123,25));System.out.println(map.get(new Student(123, 524)));System.out.println(map.get(new Student(129, 524)));System.out.println(map.containsKey(new Student(125, 524)));}
}
class Student{String id;String name;public Student(String name, String id) {this.name name;this.id id;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return Objects.equals(name, student.name);}Overridepublic int hashCode() {return Objects.hashCode(name);}
}9.TreeMap和HashMap的区别 在彻底了解完了TreeMap和HashMap的本质之后我们也就更容易清楚它们的区别其区别如下这里我就不多说了讲了这么久大家应该也能看懂了~ 综上所述作者个人认为HashMap比TreeMap要更高效毕竟不用进行元素比较时间复杂度更低。 10.TreeSet和HashSet的本质TreeSet和HashSet的区别 由上图中的源码可知TreeSet的底层是使用TreeMap来实现的其使用key与Object的一个默认对象作为键值对插入到TreeMap中所以其实TreeSet和TreeMap的本质是一样的都是红黑树实现方式和思路也全都一样。 同理也由上图源码可知HashSet的底层也是通过HashMap实现其本质也都一样都是哈希桶其实现方式和思路一模一样。 由于TreeSet本质是红黑树HashSet本质是哈希桶所以它们之间的区别也就跟TreeMap和HashMap的区别一模一样。如下 同样作者个人认为HashSet比TreeSet也要更高效毕竟也不用进行元素比较时间复杂度也更低。 11.总结 所以我们的Map和Set就讲解完了下篇文章将会讲解反射、枚举以及lambda表达式。在此我们诚挚地邀请各位大佬们为我们点赞、关注并在评论区留下您宝贵的意见与建议。让我们共同学习共同进步为知识的海洋增添更多宝贵的财富❤️❤️ 本人的一些废话 这篇文章总共写了22000多个字这也是本人第一次写这么长的文章 制作不易还希望铁汁们点个赞互三下呀大家一起加油
