个人网站可以备案了吗,孝感市网站建设,知名的网站制作公司需要多少钱,自己给网站做优化怎么做#x1f308;个人主页#xff1a;SKY-30 ⛅个人推荐#xff1a;基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解 ⚡学好数据结构#xff0c;刷题刻不容缓#xff1a;点击一起刷题 #x1f319;心灵鸡汤#xff1a;总有人要赢#xff0c;为什么不能是我呢
个人主页SKY-30 ⛅个人推荐基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解 ⚡学好数据结构刷题刻不容缓点击一起刷题 心灵鸡汤总有人要赢为什么不能是我呢
Map 和Set 概念
map和set是一种用来搜索的数据结构其搜索效率与具体实例化的子类有关之前我们搜索的方法有
直接遍历利用for循环暴力求解事件复杂度为O(N)二分查找时间复杂度O(logN),搜索之前要求序列是有序的
但是如果我们对于存储的数据经常要执行修改和删除的操作那么上述的两种操作就非常不适合了我们这里就引出两个新的数据结构-map和set。
模式
对于map来说它的存储形式是形如K-keyV-value这种类似于键值对的这种形式进行存储而set则是只有key这一种形式。
Map Map是一个接口没有继承collection该类的存储形式是K,V并且这里的K是唯一的不能重复。
Map.EntryK,V
Map.EntryK,V是Map内部用来存放key,value键值对的映射关系的一个内部类该类提供了Key,value获取value的设置即Key的比较形式
方法解释K getKey()返回 entry中的keyV getValue返回entry中的valueV 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(){
MapString, String 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.EntryString, String 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和TreemapTreeSet中的key不能插入null,HashSet则可以插入null在这里插入代码片
import java.util.TreeSet;
import java.util.Iterator;
import java.util.Set;
public static void TestSet(){
SetString 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);
IteratorString 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(pm),将关键码转换成哈希地址。 除此之外我们还发现哈希冲突与负载因子有关所以如何利用负载因子降低冲突率呢首先负载因子的计算公式是填入表中的数据的个数/散列表的长度 由于我们无法改变插入表中的数据所以我们只能改变表的长度了。 ⚡⚡⚡冲突-解决-闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以 把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢 这里我们介绍一种比较常见的方法 线性探测 比如现在需要插入元素44先通过哈希函数计算哈希地址下标为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 但是线性探测这种方法存在一定的问题比如他会导致数据全部聚集在同一块区域导致我们后面插入数据的时候可能要讲过多次的查找操作所以我们为了解决这个问题发明了另一种探测方法。
二次探测 相比与线性探测二次探测通过制定的函数可以将数据均匀的插入到数组当中避免数据扎堆的情况。 找下一个空位置的方法为 H (H0 i*i )% m, 其中i 1,2,3… 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置 m是表的大小。
研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情 况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。 因此比散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。
⚡⚡⚡冲突-解决-开散列/哈希桶重点掌握
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。
开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。
// key-value 模型
public class HashBucket {
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 array.length; i) {
Node next;
for (Node cur array[i]; cur ! null; cur next) {
next cur.next;
int index cur.key % newArray.length;
cur.next newArray[index];
newArray[index] cur;
}
}
array newArray;
}
private double loadFactor() {
return size * 1.0 / array.length;
}
public HashBucket() {
array new Node[8];
size 0;
}
public int get(int key) {
int index key % array.length;
Node head array[index];
for (Node cur head; cur ! null; cur cur.next) {
if (key cur.key) {
return cur.value;
}
}
return -1;
}
}⚡⚡⚡关于HashMap和HashSet的注意事项
HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Setjava 中使用的是哈希桶方式解决冲突的java 会在冲突链表长度大于一定阈值后将链表转变为搜索树红黑树java 中计算哈希值实际上是调用的类的 hashCode 方法进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值必须覆写 hashCode 和 equals 方 法而且要做到 equals 相等的对象hashCode 一定是一致的。
