数据结构————map,set详解

今天带来map和set的详解，保证大家分清楚

一，概念

map和set是一种专门用来搜索的容器或数据结构

map能存储两个数据类型，我们称之为<key-value>模型

set只能存储一个数据类型，我们称之为纯<key>模型

它们的效率都非常非常高，我们来一个一个了解。

二，详解map

1，map的说明

map是一个接口，所以我们不能直接创建map对象，我们可以使用Treemap和HashMap，我们先不讲treemap和Hashmap底层是怎么实现的，我们先只需要了解他们怎么使用就行（后期还是要学），treeMap的底层是使用红黑树来实现的，而Hashmap底层是哈希表，哈希表由一系列哈希桶组层，也很难，后期要掌握。

2，map中的具体方法

V put(K key, V value) 设置 key 对应的 value

开头V的意思是返回value的类型。

这个方法是添加元素，注意，实现的对象在treemap的时候k是不可以存null的，而Hashset是可以存null的，因为treemap底层的红黑树涉及比较，而Hashset主要是根据哈希函数查找，

key值如果相同的话，后添加的会把map中已经存在的key值对应的value覆盖掉，而不同key值间的value是可以相同的。

Map<String,Integer> map = new HashMap<>();map.put("ujm",12321);map.put("abs",12321);map.put("tdh",12321);map.put("yre",12321);

我们来向map中添加键值对，来调试

成功添加了键值对。

V remove(Object key) 删除 key 对应的映射关系

map中的删除方法，map中的key值是不可以修改的，只能进行删除操作，之后再重新修改。

        map.remove("ujm");map.remove("abs");map.remove("tdh");map.remove("yre");

我们看到了map中不含任何元素了。

V get(Object key) 返回 key 对应的 value

我们使用get方法来获取key———对应的value值，就是我们的查找了。

我们查找刚才添加元素的abs.

int a = map.get("abs");System.out.println(a);

我们成功找到了abs字符串

V getOrDefault(Object key, V defaultValue) 返回 key 对应的 value，key 不存在，返回默认值

但是我们这次如果没有找到对应的key,就返回我们设定的值

int a = map.getOrDefault("bswr",1000);System.out.println(a);

Set keySet()返回所有 key 的不重复集合

我们用keySet()方法来获得map中的所有key

Map<String,Integer> map = new HashMap<>();map.put("ujm",12321);map.put("abs",12321);map.put("tdh",12321);map.put("yre",12321);Set<String> set = map.keySet();

那么value呢

Collection values()返回所有 value 的可重复集合

我们用这个方法来获得所有的value

Map<String,Integer> map = new HashMap<>();map.put("ujm",12321);map.put("abs",12321);map.put("tdh",12321);map.put("yre",12321);Collection<Integer> collection = map.values();

Map.Entry<k,v>

这是map中提供的一个获取键值对的类，我们可以通过这个类来获得k,v的值，我们还可以将v替换成其他的v值，我们经常使用这个类来遍历的打印键值对。

这个类中有三个方法，

K getKey() 返回 entry 中的 key

V getValue() 返回 entry 中的 value

V setValue(V value) 将键值对中的value替换为指定value

这里先不介绍。

Set<Map.Entry<k,v>> entrySet() 返回所有的 key-value 映射关系

我们创建一个set类型,Set类型的具体数据类型是我们的键值对类型，我们对map进行.entry Set() 传给我们的set类型，我们就得到我们所有的键值对关系，这个是最重要的。

 Map<String,Integer> map = new HashMap<>();map.put("ujm",4647);map.put("abs",123);map.put("tdh",1351);map.put("yre",6856);Set<Map.Entry<String,Integer>> set = map.entrySet();for (Map.Entry<String,Integer> entry1 : set){System.out.println(entry1);}

我们使用for each遍历,

成功打印所以的键值对。

boolean containsKey(Object key) 判断是否包含 key

在map中找key，找到返回true，没有返回false

   boolean a = map.containsKey("abs");System.out.println(a);a = map.containsKey("scawcw");System.out.println(a);

boolean containsValue(Object value)判断是否包含 value

在map中找value，找到返回true，没有返回false

 boolean b = map.containsValue(123);System.out.println(b);b = map.containsValue(213124);System.out.println(b);

Map底层结构	TreeMap	HashMap
底层结构	红黑树	哈希桶
插入/删除/查找时间复杂度	O(log2n)	O(1)
是否有序	关于key有序	无序
线程安全	不安全	不安全
插入/删除/查找区别	需要进行元素比较	需要哈希函数计算地址
比较与覆写	不可以放null会抛异常	需要覆写HashCode和equals函数
应用场景	key有序最好	不关心，开辟大量内存换取时间

三，详解set

1.set的说明

Set也是一个接口，我们要想创建对象就要使用TreeSet，HashSet，Set是纯key模型，不能重复，我们常常使用Set来去重。

2.set中的具体方法

boolean add(E e) 添加元素，但重复元素不会被添加成功

向set中添加元素，set中的key不能重复

Set<Integer> set = new HashSet<>();set.add(13);set.add(46);set.add(768);

我们看到set中成功添加了三个元素

void clear() 清空集合

set.add(13);set.add(46);set.add(768);set.add(2);set.clear();

boolean contains(Object o) 判断 o 是否在集合中

        Set<Integer> set = new HashSet<>();set.add(13);set.add(46);set.add(768);set.add(2);boolean a = set.contains(12);boolean b = set.contains(2);System.out.println(a + "   " + b);

boolean remove(Object o)

set.remove(13);

移除13。

Iterator iterator() 返回迭代器

这个方法我们主要用来遍历打印我们的Set，因为set实现了我们的Iterator接口

Iterator<Integer> iterator = set.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}

其他方法

Set底层结构	TreeSet	HashSet
底层结构	红黑树	哈希桶
插入/删除/查找时间复杂度	O(log2n)	O(1)
是否有序	关于key有序	无序
线程安全	不安全	不安全
插入/删除/查找区别	需要进行元素比较	需要哈希函数计算地址
比较与覆写	不可以放null会抛异常	需要覆写HashCode和equals函数
应用场景	key有序最好	不关心，开辟大量内存换取时间

四，练题

好了，终于讲完我们的基础了，我们来三道小练习题
1给一组元素，统计元素出现的次数
2给定一组元素去重
3找到一组数据中第一个重复的数据

1，给一组元素，统计元素出现的次数

        int[] arr = new int[]{23,352,46,47,84,1,44,6,1,23};Map<Integer,Integer> map = new HashMap<>();for (int i = 0; i < arr.length; i++) {if(map.get(arr[i])==null){map.put(arr[i],1);}else {map.put(arr[i], map.get(arr[i])+1);}}Set<Map.Entry<Integer,Integer>> set = map.entrySet();for (Map.Entry<Integer,Integer> entry: set){System.out.println(entry);}

2，给定一组元素去重

int[] arr = new int[]{23,352,46,47,84,1,44,6,1,23};Set<Integer> set = new HashSet<>();for (int i = 0; i < arr.length; i++) {set.add(arr[i]);}Iterator<Integer> iterator = set.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}

3，找到一组数据中第一个重复的数据

int[] arr = new int[]{23,352,46,47,84,1,44,6,1,23};Set<Integer> set = new HashSet<>();for (int i = 0; i < arr.length; i++) {if (!set.contains(arr[i])){set.add(arr[i]);}else {System.out.println(arr[i]);return;}}