网站设计团队分工,长沙美容网站建设,seo搜索引擎优化策略,分销商城模式系统开发前言
我们将学习 Map 与 Set 这两个接口下的 TreeMap 与 TreeSet #xff0c;HashMap 与 HashSet #xff0c;在学习这四个类使用之前#xff0c;我们需要先学习 二叉搜索树与 哈希表的知识。
二叉搜索树
在学习二叉树的时候#xff0c;我们就已经了解过二叉搜索树的概念…前言
我们将学习 Map 与 Set 这两个接口下的 TreeMap 与 TreeSet HashMap 与 HashSet 在学习这四个类使用之前我们需要先学习 二叉搜索树与 哈希表的知识。
二叉搜索树
在学习二叉树的时候我们就已经了解过二叉搜索树的概念与性质性质我们来回顾以下
二叉搜索树Binary Search Tree也称为二叉查找树或二叉排序树是一种特殊的二叉树。它的定义基于以下性质
若它的左子树不空则左子树上所有节点的值都小于根节点的值。 若它的右子树不空则右子树上所有节点的值都大于根节点的值。 它的左、右子树也分别为二叉搜索树。 此外二叉搜索树的一个重要特性是它的中序遍历结果一定是有序的。这意味着在二叉搜索树中如果按照中序遍历的方式访问所有节点将得到一个有序的节点值序列。 二叉搜索树的这些性质使得它在数据检索、排序等算法中具有高效性尤其是在需要频繁查找、插入或删除数据的场景中二叉搜索树的操作效率通常优于其他数据结构。
现在我们来模拟实现二叉搜索树先创建好类
public class BinarySearchTree {static class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val val;}}public TreeNode root;
}搜索
搜索可以类比成二分查找当根节点数值大于要查找的数值就去左子树继续查找当根节点的数值小于要查找的数值就去右子树继续查找。 public TreeNode search(int key) {TreeNode cur root;while(cur ! null) {if(cur.val key) {return cur;} else if(cur.val key) {cur cur.left;} else {cur cur.right;}}return null;}当二叉搜索树是一颗均匀分布的完全二叉树时搜索的时间复杂度最佳为O(logN) 当二叉搜索树为一颗单分支的树此时搜索效率最差为O(N) 插入
插入和搜索类似。
这里要注意的是如果插入的数值已经存在于二叉树中就不能继续插入也就是说二叉搜索树只能保存一份数据无法保存两份及以上的相同的数据。 public void insert(int key) {TreeNode node new TreeNode(key);if(root null) {root node;return;}TreeNode cur root;TreeNode prev null;while(cur ! null) {if(cur.val key) {return;} else if(cur.val key) {prev cur;cur cur.left;} else {prev cur;cur cur.right;}}if(key prev.val) {prev.right node;} else {prev.left node;}}删除
先找到要删除的结点我们既要得到删除的结点还要直到删除的结点的双亲结点这样才可以进行下一步的删除。 public void remove(int key) {TreeNode prev null;TreeNode cur root;while(cur ! null) {if(cur.val key) {prev cur;cur cur.left;} else if(cur.val key) {prev cur;cur cur.right;} else {removeNode(prev,cur);return;}}}分情况讨论del 左子树为空del 右子树为空del 左右子树均不为空。
当del 左子树为空del 有两种情况一个是在 parent 的左边另一种是在 parent 的右边根据不同的情况我们直接将del 的右子树直接连接到 parent 左/右 上 这里要注意如果 del 是根节点的话我们的 root 就要改变。 if(del.left null) {if(del root) {root del.right;} else if(parent.left del) {parent.left del.right;} else {parent.right del.right;}}当del 右子树为空del 有两种情况一个是在 parent 的左边另一种是在 parent 的右边根据不同的情况我们直接将del 的左子树直接连接到 parent 左/右 上 这里要注意还有第三种情况如果 del 是根节点的话我们的 root 就要改变。 else if(del.right null) {if(del root) {root del.left;} else if(parent.left del) {parent.left del.left;} else {parent.right del.left;}}第三种情况 del 的左右子树均不为空 在这种情况下直接去删除这个结点是一件很麻烦的事情如果采用直接删除我们需要重新在其子树找到合适的结点然后将其变为新的双亲结点 并且要连接好两颗子树。 因此为了方便我们采用替换删除法替换删除法是找到一个合适的结点将这个结点的数值直接覆盖到你要删除的结点的数值域里这样就变相删除了这个结点然后再将这个合适的结点删除掉。 什么是合适的结点 由于这是一颗二叉搜索树所以该树的根节点大于左子树小于右子树所以合适的结点就要满足这两个条件比左子树的大比右子树的小 这个合适的结点是从要删除的结点的左子树或者右子树出发寻找根据二叉搜索树的性质根节点的左子树任意结点都比根节点的右子树任意结点小那么我们只要找到左子树最大的结点的数值将其覆盖到要删除结点的数值。而左子树的最大结点为左子树最右边的结点 如果是从右子树出发那我们就要寻找到右子树的最小结点也就是右子树的最左边的结点。 这里我以找寻右子树最左边的结点为例子 这里要注意如果 while 循环没有进去也就是 prev delcur del.right那么 prev 的右边是否为 cur 如果循环进去了那结果就是 prev 的左边为 cur 所以最后删除的时候要分类讨论一下。 else {TreeNode prev del;TreeNode cur del.right;while(cur.left ! null) {prev cur;cur cur.left;}del.val cur.val;if(prev.right cur) {prev.right cur.right;} else {prev.left cur.right;}}removeNode 最终代码 private void removeNode(TreeNode parent,TreeNode del) {if(del.left null) {if(del root) {root del.right;} else if(parent.left del) {parent.left del.right;} else {parent.right del.right;}} else if(del.right null) {if(del root) {root del.left;} else if(parent.left del) {parent.left del.left;} else {parent.right del.left;}} else {TreeNode prev del;TreeNode cur del.right;while(cur.left ! null) {prev cur;cur cur.left;}del.val cur.val;if(prev.right cur) {prev.right cur.right;} else {prev.left cur.right;}}}Map 与 Set 的简单介绍 Map和set是一种专门用来进行搜索的容器或者数据结构其搜索的效率与其具体的实例化子类有关。 回顾之前我们学习到的搜索假设有一组数据需要查找某一个数据的时候我们会考虑到两种方法一种是直接遍历时间复杂度为O(N) 另一种是二分查找时间复杂度为O(logN)二分查找的前提是数据必须是有序的。
上面两种查找方式比较适合静态类型的查找即一般不会对数据有插入和删除的操作
但是在现实中我们的查找有 1.根据姓名查找个人信息 2.找到不重复的集合即筛选掉重复的数据只保留一份数据。
这些查找可能会伴随一些插入和删除的操作这就是动态查找那么我们就不适合使用上面两种静态查找的方式了这时候Java 给我们提供了两个容器 Map 和 Set 两个适合动态查找的容器。
两个模型
一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种
1.纯 key 模型 比如有一个英文词典快速查找一个单词是否在词典中 快速查找某个名字在不在通讯录中
2.Key-Value 模型 比如统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数单词单词出现的次数 梁山好汉的江湖绰号每个好汉都有自己的江湖绰号 Map中存储的就是key-value的键值对Set中只存储了Key。
哈希表
概念
在顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O(logN)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
当向该结构中 插入元素: 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素
搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(HashTable)(或者称散列表)
举个例子现在有一组数据 { 159247} 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 存储空间大小为 10 在存储的时候我们按照哈希函数来确定数据的具体位置在搜索的时候将要搜索的元素通过哈希函数计算出具体的下标然后直接去该处拿去元素。 可见哈希表的存储和搜索的时间复杂度为 O(1) 冲突
概念
对于两个数据元素的关键字 a 和 b ,在进行插入的时候通过哈希函数的计算发现Hash(a) 等于Hash(b) 即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
首先我们需要明确一点由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的这就导致一个问题冲突的发生是必然的但我们能做的应该是尽量的降低冲突率。
避免冲突 —— 哈希函数设计
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单
常见哈希函数设方法: 1.直接定制法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况
当我们事先直到数据的分布情况我们可以朝着线性分布的方向继续设计哈希函数也就是一次函数HashKey A*Key B让数据在哈希表中分布均匀。
2.除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址
3.平方取中法 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址 再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况
4.折叠法 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况
5.随机数法 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
6.数学分析法 设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。
数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突
负载因子调节重点
哈希表的负载因子定义为 a 填入表中的元素个数 / 散列表的长度
现在我们来看一下负载因子和冲突率的关系图 可以得出一个结论当负载因子越大冲突率就会越高而负载因子的大小又与填入表中元素的个数成正比。 对于开放定址法负载因子是一个很关键的因素应该严格限制在 0.7 - 0.8以下。超过0.8查表是的CPU 缓存不命中cache missing 按照指数曲线上升。 在 Java 的 hash 库中负载因子被定义在 0.75一旦超过这个数值就会对哈希表进行扩容 解决冲突
解决哈希冲突两种常见的方法是闭散列和开散列
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。
线性探测 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素。
举个例子在上面我们已经插入了一组数据 { 159247} 现在又要插入一个数据这个数据是 17由于 hash(17) 17 10 7而 7 下标已经插入了数据这时候会发生哈希冲突使用线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止发现 8 下标的位置为空那么我们直接将 17 插入到 8 小标里面。 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他 元素的搜索。比如删除元素7如果直接删除掉17查找起来可能会受影响因为 17 的哈希值为 7 但是 7 下标没有数据那计算机到底是认为存在17 还是不存在 17 呢因此线性探测采用标记的伪删除法来删除一个元素。 线性探测的缺陷是产生冲突的数据堆积在一块这与其 找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找 二次探测 因此二次探测为了避免线性探测的问题找下一个空位置的方法为 H ( H0 i ^2 ) % m 或者 H ( H0 - i ^2 ) % m其中 i 1、2、3…H0 是通过哈希函数 Hash(x) 对元素的关键码 key 进行计算得到的位置m 为表的长度。
举个例子还是插入17 这个元素使用二次探测法插入 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。 因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。 开散列/哈希桶重点
开散列法又叫链地址法(开链法)也就是数组加链表的形式首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。
开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
那么在上面讨论 17 应该插入在哪个位置如果使用链地址法应该放在 7 的后面如下图 冲突严重时的解决办法
刚才我们提到了哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了那如果冲突严重就意味着小集合的搜索性能其实也时不佳的这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化例如
1.每个桶的背后是另一个哈希表 2.每个桶的背后是一棵搜索树
模拟实现哈希表
由于Java 自己的hash 库使用的是 链地址法所以这里我使用数组加单链表的方法来模拟哈希表并且负载因子和 Java 的 0.75 设置一致哈希函数我设置为 hash(x) key % 数组长度 并且插入结点采用头插法 模拟 key - val 模型
public class Hash {static class Node {int key;int val;Node next;public Node(int key, int val) {this.key key;this.val val;}}public Node[] elem new Node[10];private int useSize;private static final double DEFAULT_LOAD_FACTOR 0.75;
}扩容
当负载量超过负载因子的时候我们就要扩容我们先写一个方法用于检测目前的负载量 //检测当前的负载量private double checkCurrentLoad() {return useSize * 1.0 / elem.length;}然后我们来写扩容方法注意哈希表不是简单的扩容扩容意味着原本哈希表存放的数据就要进行移动使之与新表匹配所以我们先创建一个新数组然后遍历旧哈希表将所有结点移动到新哈希表上最后改变 elem 的引用就是实现了哈希表的扩容。 private void resize() {Node[] newArray new Node[elem.length * 2];for (int i 0; i elem.length; i) {Node cur elem[i];while(cur ! null) {Node curN cur.next;int index cur.key % newArray.length;cur.next newArray[index];newArray[index] cur;cur curN;}}elem newArray;}插入
我们先插入数据这里要注意哈希表不能存放两份及以上的相同的 key 如果有则会更新 val 值 这里采用头插法 等到插入完成后要判断此时是否超出负载因子的设置范围如果超过了则要进行扩容。 //插入数据public void put(int key,int val) {//是否已经存在 key ,存在则更新 val 值int index key % elem.length;Node cur elem[index];while(cur ! null) {if(cur.key key) {cur.val val;return;}cur cur.next;}//头插法Node node new Node(key, val);node.next elem[index];elem[index] node;useSize;//检测是否超过负载因子if(checkCurrentLoad() DEFAULT_LOAD_FACTOR) {resize();}}获取 val
直接通过哈希函数获取 key 所在下标然后遍历这个下标的链表获取 val 值 //获取 val 值public int get(int key) {int index key % elem.length;Node cur elem[index];while(cur ! null) {if(cur.key key) {return cur.val;}cur cur.next;}return -1;}泛型类哈希表模拟
在获取key 位置的时候我们不能直接直接通过 key % 数组长度 来获取因为 key 此时是 泛型但是我们可以通过 hashCode() 方法来得知它的哈希值哈希值是整型所以我们可以利用哈希值来算 key 的下标
在比较两个泛型结点的 key 是否相同的时候我们不能直接使用 而是要使用 equals 来比较两个泛型的内容相不相同。
所以我们在使用 HashMap 或者 HashSet 的时候如果插入的是自定义类型那这个自定义类型就啊哟重写好 hashCode() 和 equals 两个方法
public class hash2K,V {static class NodeK,V {K key;V val;NodeK,V next;public Node(K key, V val) {this.key key;this.val val;}}private NodeK,V[] elem new Node[10];private int useSize;private static final double DEFAULT_LOAD_FACTOR 0.75;//插入数据public void put(K key,V val) {//是否已经存在 key ,存在则更新 val 值int index key.hashCode() % elem.length;NodeK,V cur elem[index];while(cur ! null) {if(cur.key.equals(key)) {cur.val val;return;}cur cur.next;}//头插法NodeK,V node new Node(key,val);node.next elem[index];elem[index] node;useSize;//检测是否超过负载因子if(checkCurrentLoad() DEFAULT_LOAD_FACTOR) {resize();}}private void resize() {NodeK,V[] newArray new Node[elem.length * 2];for (int i 0; i elem.length; i) {NodeK,V cur elem[i];while(cur ! null) {NodeK,V curN cur.next;int index cur.key.hashCode() % newArray.length;cur.next newArray[index];newArray[index] cur;cur curN;}}elem newArray;}//检测当前的负载量private double checkCurrentLoad() {return useSize * 1.0 / elem.length;}//获取 val 值public V get(K key) {int index key.hashCode() % elem.length;NodeK,V cur elem[index];while(cur ! null) {if(cur.key.equals(key)) {return cur.val;}cur cur.next;}return null;}
}虽然哈希表一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。 Map 与 Set 的使用
在上面大家已经了解到 二叉搜索树和哈希表现在我们来学习 Map 与 Set 的使用。
在讲解之前我们先讨论一个问题二叉搜索树的搜索的时间复杂度有好有坏我们该如何将二叉搜索树的性能变成最好的当二叉搜索树是一颗完全二叉树的时候性能是最佳的那如何保持为完全二叉树这时候就需要将二叉搜索树调整为平衡树如何调整答案就是使用红黑树这个数据结构维持它能让二叉树保持为一个平衡树也就是无论是插入还是删除红黑树始终能让二叉树保持为一个平衡树。
在Java 中提供的哈希表是使用链地址法也就是数组加链表还有加红黑树即哈希表等于 数组 链表 红黑树 Java 的哈希表一旦数组长度超过 64 并且链表长度超过 8 就会通过红黑树将链表进行树化调整为红黑树保持哈希表优秀的性能 平衡树与红黑树会在后序文章中讲解大家尽情期待~~ 下面我们来看一下 Map 与 Set 两个接口的情况
Map 的使用
Map是一个接口类该类没有继承自Collection该类中存储的是K,V结构的键值对并且K一定是唯一的不能重复。 注意事项
1.Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2.Map中存放键值对的Key是唯一的value是可以重复的
3.在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常并且key 必须是可比较的value可以为空。但是HashMap的key和value都可以为空。
4.Map中的Key可以全部分离出来存储到Set中来进行访问(因为Key不能重复)。
5.Map中的value可以全部分离出来存储在Collection的任何一个子集合中(value可能有重复)。
6.Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入。 TreeMap 与 HashMap
Map底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找的时间复杂度O(logN)O(1)存储的元素是否有序关于key 有序无序线程安全不安全不安全插入/删除/查找的区别需要进行元素的比较通过哈希函数计算哈希地址比较与覆写key 必须能够比较,否则就会抛NullPointerException异常自定义类型需要重写 equals 和 hashCode 方法应用场景要求key有序不关心key 有无序重点关注的是时间性能
Map 常用方法
方法解释V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)返回 key 对应的 value如果 key 不存在则返回默认值V put(K key, V value)设置 key 对应的 valueV remove(Object key)删除 key 对应的映射关系Set K keySet()返回 key 的不重复集合Colletion V values()返回所有 value 的可重复集合SetMap.EntryK,V entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value
代码演示 public static void main(String[] args) {HashMapString,Integer map new HashMap();map.put(abcd,123);map.put(hello,64);map.put(world,256);map.put(error,1024);System.out.println(size: map.size());System.out.println(hello: map.get(hello));System.out.println(map.containsKey(ab));System.out.println(map.containsValue(256));}public static void main(String[] args) {HashMapString,Integer map new HashMap();map.put(abcd,123);map.put(hello,64);map.put(world,256);map.put(error,1024);map.put(null,1024);System.out.println(map.entrySet());map.remove(abcd);System.out.println();System.out.println(map.entrySet());}public static void main(String[] args) {HashMapString,Integer map new HashMap();map.put(abcd,123);map.put(hello,64);map.put(world,256);map.put(error,1024);map.put(null,1024);SetMap.EntryString,Integer set map.entrySet();for(Map.EntryString,Integer x: set) {System.out.println(key: x.getKey() val: x.getValue());}}keySet 方法可以返回所有 key 的不重复合集可以使用 Set 来接收 如果想接收所有的 values 包括重复的 values 的合集可以使用 Collection 来接收 Map.EntryK,V
Map.EntryK, V 是Map内部实现的用来存放key, value键值对映射关系的内部类该内部类中主要提供了key, value的获取value的设置以及Key的比较方式。
方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value)将键值对的 value替换为指定value public static void main(String[] args) {HashMapString,Integer map new HashMap();map.put(abcd,123);map.put(hello,64);map.put(world,256);map.put(error,1024);map.put(null,1024);SetMap.EntryString,Integer set map.entrySet();for(Map.EntryString,Integer x: set) {x.setValue(10256);}System.out.println();System.out.println(检测将每个键值对的 value 设置为 10256是否成功);for(Map.EntryString,Integer x: set) {System.out.println(key: x.getKey() val: x.getValue());}}Set 的使用
Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。
注意事项 1.Set是继承自Collection的一个接口类
2.Set中只存储了key并且要求key一定要唯一
3.TreeSet的底层是使用Map来实现的其使用key与Object的一个默认对象作为键值对插入到Map中的
4.Set最大的功能就是对集合中的元素进行去重
5.实现Set接口的常用类有TreeSet和HashSet还有一个LinkedHashSetLinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6.Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入
7.TreeSet中不能插入null的keyHashSet可以。 TreeSet 与 HashSet
Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找的时间复杂度O(logN)O(1)存储的元素是否有序关于key 有序无序线程安全不安全不安全插入/删除/查找的区别需要进行元素的比较通过哈希函数计算哈希地址比较与覆写key 必须能够比较,否则就会抛NullPointerException异常自定义类型需要重写 equals 和 hashCode 方法应用场景要求key有序不关心key 有无序重点关注的是时间性能 Set 常用方法
方法解释boolean add(E e)添加元素如果添加的是重复元素就不会添加成功void clear()清空集合boolean contains(Object o)判断 o 是否在集合中Iterator E iterator()返回迭代器boolean remove(Object o)删除集合中的 oint size()返回 set 中的元素个数boolean isEmpty()检测 set 是否为空,空则返回true,否则返回falseObject[] toArray()将 set 中的元素转化为数组返回boolean containsAll(Collection ? c)集合 c 中的元素是否在 set 中全部存在是则返回true, 否则返回falseboolean addAll(Collection? extends E c)将集合 c 中的元素添加到 set 中可以达到去重的效果。
代码演示 public static void main(String[] args) {TreeSetInteger treeSet new TreeSet();treeSet.add(10);treeSet.add(100);treeSet.add(85);treeSet.add(32);System.out.println(treeSet.contains(100));IteratorInteger it treeSet.iterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();System.out.println(演示删除);treeSet.remove(100);it treeSet.iterator();while(it.hasNext()){System.out.print(it.next() );}System.out.println();System.out.println(treeSet.size());System.out.println(treeSet.isEmpty());Integer[] arr (Integer[])treeSet.toArray(new Integer[0]);for (int x: arr) {System.out.print(x );}}Java 的 HashMap 部分源码解析 构造方法 将默认 初始容量为 16将负载因子设置为 默认值 0.75 调用了另一个构造方法来设置初始容量但是负载因子还是设置为默认值 0.75 可以设置初始容量以及负载因子。 if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;当默认容量小于 0 会抛异常当初始容量 大于 最大的默认容量也会抛异常。 if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);当负载因子小于 0 或者负载因子不是数字 就会抛异常
下面是 isNaN 的源码 现在我们来看一下 this.threshold tableSizeFor(initialCapacity);是如何设置初始容量的 返回给定目标容量的2次幂。 举个例子如果你设置的初始容量为 10经过一顿操作实际设置的初始容量为 2 ^ 4 16 put
下面是 哈希表 的数组 但是在此之前我们都没有看到一个数组的创建实际上 数组的创建会在 put 方法里体现 put 方法传入了 hash(key) 通过 (h key.hashCode()) ^ (h 16) 会使 Key 分布的更均匀 put 方法 调用了 putVal 方法 if ((tab table) null || (n tab.length) 0)n (tab resize()).length;当数组为 null 或者 数组的长度为 0 就会扩容。 if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);当 key 的哈希值 所在的存储位置为空时直接插入结点。 走到这里的时候说明这个哈希值对应的数组的位置已经被插入了
NodeK,V e; K k;
if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;当哈希值是相同 并且 一个已经被插入的结点的 key 和待插入的结点的 key 的地址是相同又或者 key 不是空并且 两个的 key 的内容是相同的话就将待插入的结点赋值给 e 。 如果不满足上面的条件就说明这个结点是一个要插入到 链表或者红黑树的结点因此下面中的p instanceof TreeNode 会判断此时数组存储的是 链表还是红黑树如果是红黑树 e 就是一个红黑树的结点并通过 putTreeVal() 方法来将 结点插入到红黑树中。
else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);走到这里说明需要需要在链表里插入新结点。
下面就是链表的插入代码
else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}
}要注意其中这一行代码
if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);这行代码是判断是否需要将链表调整为红黑树。 put 源码分析到这里感兴趣可以继续往下分析 get 调用了 getNode() 方法 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) (hash hash(key))]) ! null) 先判断这个 key 是否存在从数组不为空并且数组长度不为 0 并且 key 的哈希值所在的 数组位置不为空才会继续寻找否则直接返回 null if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;检查是不是第一个结点是的话直接返回不是的话说明在第一个结点后面的结点需要继续寻找。 if ((e first.next) ! null) {if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}当第一个结点后面存在下一个结点才继续寻找first instanceof TreeNode 是 true 说明第一个结点是树结点说明数组连接的是红黑树那么就会通过红黑树的搜索方法getTreeNode 来进行搜索如果不是则是以链表的形式进行搜索。
