哪有做网站公司城乡建设学校官方网站

当前位置： 首页 > news >正文

哪有做网站公司,城乡建设学校官方网站,龙文区城乡建设局网站,唐山微网站建设价格目录 1、介绍 1.1 Map和Set 1.2 模型 2、Map集合 2.1 Map集合说明 2.2 Map.EntryK#xff0c;V 2.3 Map常用方法 2.4 Map注意事项及实现类 3、Set集合 3.1 Set集合说明 3.2 Set常用方法 3.3 Set注意事项及其实现类 4、TreeMapTreeSet 4.1 集合类TreeM…目录 1、介绍 1.1 Map和Set 1.2 模型 2、Map集合 2.1 Map集合说明 2.2 Map.EntryKV 2.3 Map常用方法 2.4 Map注意事项及实现类 3、Set集合 3.1 Set集合说明 3.2 Set常用方法 3.3 Set注意事项及其实现类 4、TreeMapTreeSet 4.1 集合类TreeMapKey-Value模型 4.1.1 底层结构 4.2 集合类TreeSet纯Key模型 4.2.1 底层结构 4.3 TreeMap与TreeSet之间的关系 4.3.1 再谈TreeSet之构造方法 4.3.2 再谈TreeSet之add方法 4.4 TreeMapTreeSet总结 5、哈希表 5.1 概念 5.2 冲突-概念 5.2 冲突-避免 5.2.1 设计合理的哈希函数 5.2.2 调节负载因子 5.3 冲突-解决 5.3.1 闭散列 5.3.2 开散列/哈希桶/开链法 5.4 HashMapHashSet 5.4.1 hashCode与equals方法 5.5 性能分析 5.6 总结 1、介绍 1.1 Map和Set Map和Set是一种专门用来进行搜索的容器或者数据结构其搜索的效率与其具体的实例化子类有关。 Map和Set能够在查找时进行一些插入和删除的操作即动态查找。 1.2 模型 一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对所以模型会有两种 纯Key模型数据仅包含关键字。Key-Value模型数据除关键字外还有关键字所对应的值。例如统计文件中每个单词出现的次数统计结果是每个单词都有与其对应的次数单词单词出现的次数。 Map集合是Key-Value模型而Set集合是纯Key模型。 2、Map集合 2.1 Map集合说明 Map是一个接口类该接口没有继承自Collection是一个单独的接口为Key-Value模型存储的是KV结构的键值对并且K一定是唯一的不能重复。  K不可重复V可重复 2.2 Map.EntryKV Entry是Map接口的一个内部接口是用来存放KeyValue键值对映射关系的内部接口。 内部接口Map.EntryKV主要提供了KeyValue的获取Value的设置以及Key的比较方式。 注意Map.EntryKV并没有提供设置Key的方法 Key无法修改 同样实现Map接口的类也需要实现Entry接口 这里以TreeMap的内部类Entry为例Entry实现了的Map.Entry接口而Entry就相当于我们之前所学二叉树的一个节点TreeNode。 TreeMap的底层是一个红黑树下文详解TreeMap的内部类Entry就相当于红黑树的一个节点有key、value等属性。 2.3 Map常用方法 演示如下 若我们使用get方法来获取一个不存在的key的value值时返回的value为null 所以当value为Integer类型时最好使用包装类Integer接收若使用int基本类型接收会自动拆箱可能抛出空指针异常 需要注意的是keySet、values、entrySet方法 keySet可以将key值放在Set集合中返回Set集合values可以将value值放在Collection集合中返回Collection集合entrySet可以将key-value映射关系放在Set集合中返回Set集合。 注意Map系列集合是不能用迭代器实现遍历的若想使用迭代器遍历需要使用keySet、values、entrySet方法转换为Set集合再使用迭代器遍历 2.4 Map注意事项及实现类 Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap Map中存放键值对的Key不能重复value是可以重复的 在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。TreeMap底层是一颗红黑树涉及key之间的比较HashMap的key和value都可以为空。Map中的Key可以全部分离出来存储到Set中来进行访问(Key不能重复)。 Map中的value可以全部分离出来存储在Collection的集合中若存储在其子集中则强转为Collection(value可以有重复)。Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入。 TreeMap和HashMap是实现Map的集合类 TreeMap与HashMap 下文细讲TreeMap与HashMap。  3、Set集合 3.1 Set集合说明 Set集合是纯Key模型也就是说Set只存储了Key。 Set集合中的Key值也不能重复存在能够达到天然去重的效果。 Set与Map主要的不同有两点 Set是继承自Collection的接口类。Set是纯Key模型只存储了Key。 3.2 Set常用方法 因为Set是是继承自Collection的接口类所以其方法很多与我们之前学的Collection接口下的类是相同的这里不再赘述。 需要注意的是 如果将其他集合的元素添加到Set集合中可以到达天然去重的效果Set集合可以使用迭代器遍历 3.3 Set注意事项及其实现类 Set是继承自Collection的一个接口类。Set中只存储了key并且要求key一定要唯一。TreeSet的底层是使用TreeMap来实现的其使用Key与Object的一个默认对象作为键值对插入到Map中。Set最大的功能就是对集合中的元素进行去重。实现Set接口的常用类有TreeSet和HashSet下文细讲还有一个LinkedHashSetLinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入 TreeSet中不能插入null的key底层为搜索二叉树涉及key的比较HashSet可以。 TreeSet与HashSet 4、TreeMapTreeSet 为什么要将TreeMap和TreeSet放到一起说呢因为这两者间是有关系的。 4.1 集合类TreeMapKey-Value模型 4.1.1 底层结构 TreeMap是Map集合下的一个集合类底层是一颗红黑树红黑树是一颗二叉搜索树所以其Key值必须具备可比较功能。 也就是说如果其Key是自定义类型则这个自定义类必须实现Comparable接口或者给TreeMap的构造方法提供比较器。 因为TreeMap底层为红黑树故其插入删除查找元素的时间复杂度为OlogN 4.2 集合类TreeSet纯Key模型 4.2.1 底层结构 TreeSet是Set集合下的一个集合类底层也是一颗红黑树红黑树是一颗二叉搜索树所以其Key值也必须具备可比较功能。 故TreeSet插入删除查找元素的时间复杂度也为OlogN 同样如果其Key是自定义类型则这个自定义类必须实现Comparable接口或者给TreeSet的构造方法提供比较器。 4.3 TreeMap与TreeSet之间的关系 虽然TreeMap是Map下的集合TreeSet是Set下的集合 但是细心的小伙伴已经发现TreeMap和TreeSet的底层结构不仅都是红黑树而且他们的Key值都不能重复出现那么他们之间是不是有什么关系呢 没错其实TreeSet的底层是使用TreeMap来实现的。 可是为什么呢接下来让我们从TreeSet的源码中找到原因。 4.3.1 再谈TreeSet之构造方法 我们可以看到当我们调用TreeSet的无参构造方法创建TreeSet对象时其实是创建了一个TreeMap对象并传给了带一个参数的构造方法并用NavigableMap类型的成员变量m将这个TreeMap对象引用起来。 而NavigableMap是什么呢我们点过去后发现是一个接口并且拓展了SortedMap接口而我们发现SortedMap接口拓展了Map接口。 我们再观察TreeMap发现TreeMap实现了NavigableMap接口。 所以其实TreeMap有着下图的实现结构 也就是说NavigableMap可以用来接收TreeMap对象实现向上转型同时也说明当我们实例化一个TreeSet对象时实际上创建的是一个TreeMap对象。 也就是说TreeSet的底层其实就是TreeMap 4.3.2 再谈TreeSet之add方法 因为TreeSet的底层是TreeMap所以添加元素add时实际上调用的是TreeMap的put方法而其value值是PRESENT而PRESENT永远都是一个Object对象。  所以不管add的Key是什么东西其value值永远都是一个Object对象。 4.4 TreeMapTreeSet总结 TreeMap底层是一颗红黑树二叉搜索树。TreeSet的底层是TreeMap所以TreeSet也是一颗红黑树二叉搜索树。TreeSet的底层是TreeMap所以其Key不可重复具有Map的去重功能。 5、哈希表 5.1 概念 在顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码Key的多次比较。顺序查找时间复杂度为ON平衡树中为树的高度即OlogN搜索的效率取决于搜索过程中 元素的比较次数。 而哈希表可以通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系不经过任何比较一次直接从表中得到要搜索的元素。 该方式即为哈希散列方法哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表或者称散列表。 插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放 查找元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若 关键码相等则搜索成功  哈希表 插入/删除/查找操作的时间复杂度为 O1。 5.2 冲突-概念 不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为同义词。 由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的 这就导致一个问题冲突的发生是必然的但我们能做的应该是尽量的降低冲突率 5.2 冲突-避免 避免冲突有两个办法一个是设计合理的哈希函数一个是调节负载因子。 5.2.1 设计合理的哈希函数 哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 常见哈希函数 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 在实际应用中其实也轮不到我们来设计哈希函数…hhh 5.2.2 调节负载因子 负载因子的计算公式为负载因子 已有键值对数量 / 散列表容量。 它表示在散列表中当插入一个新的键值对时可以允许的最大填充程度。 负载因子越大散列表的填充程度越高冲突的发生率越高。相反负载因子越小散列表的填充程度越低插入和查找操作的性能可能会更好冲突的发生率越低但空间利用率会降低。 因为我们不能降低元素填入个数所以我们只能扩容哈希表来降低冲突率。 当元素个数和散列表容量的比值接近或等于负载因子时就要对哈希表进行扩容操作。 换句话说哈希表就是以空间换取时间的一种数据结构。 Java中定义的负载因子大小为0.75。 5.3 冲突-解决 我们知道冲突的发生是必然的那么当冲突发生后我们该如何做呢 解决哈希冲突两种常见的方法是闭散列和开散列。 5.3.1 闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的下一个空位置中去。 找下一个”空位置有两种方法  线性探测法从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。线性探测的缺陷是产生冲突的数据堆积在一块二次探测法采用移动数值的平方次来找空位置。例如如果键15的哈希值对应的空间已经被占用算法可能会尝试使用平方数序列如1^2 -1^2 2^2 -2^2 …来计算新的哈希值直到找到一个空位置为止。这种方法有助于避免哈希表中数据的聚集提高哈希表的性能和数据的均匀分布。‌ 5.3.2 开散列/哈希桶/开链法 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 拉链法解决冲突的特点 将所有关键字为同义词的结点链接在同一个单链表中。拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短。 即 数组链表模式 也就是说开散列中每个桶中放的都是发生哈希冲突的元素。 HashMap采用的就是开散列法解决冲突。 但是当冲突严重时链表的长度就会过于长这样会影响搜索性能 在Java中当 数组长度超过64 链表长度超过8 链表就会转化为红黑树。 5.4 HashMapHashSet 5.4.1 hashCode与equals方法 hashCode方法的作用是生成哈希值通过哈希值计算出key在数组中的位置下标。equals方法的作用是判断两个key的内容是否相等。 例如在使用put或者getValue方法时通过hashCode找到元素的位置下标后还需要使用equals方法一个一个的和链表中的元素比较找到该元素在链表中的具体位置若equals为true说明找到了该元素。 故当哈希表中的key为自定义类时一定要重写equals和hashCode方法  注意 若两个key通过equals比较结果为true说明两个key的内容相同说明通过hashCode得到的哈希值一定是相等的但是若两个key 通过hashCode得到的哈希值相等那么只能说明这两个key在数组中的位置是相同的不能说明两个key的内容相同也就是说equals可能为true也可能为flase。 总结如果equals为true那么hashCode出的哈希值一定相等 如果hashCode出的哈希值相等那么equals不一定为true 5.5 性能分析 虽然哈希表一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个数是可控的 也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。 5.6 总结 HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 SetHashMap 和 HashSet 中使用的是 哈希桶/开散列 方式解决冲突的java 会在冲突链表长度大于一定阈值后将链表转变为搜索树红黑树java 中计算哈希值实际上是调用的类的 hashCode 方法进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作 HashMap 的key值或者 HashSet 的key值必须重写 hashCode 和 equals 方法。equals 相等的对象hashCode 一定是一致的。hashCode一致equals不一定相等。HashMap和HashSet不涉及元素之间的比较所以不用像TreeMap或TreeSet具备可比较功能。