• 前言

这几天看代码碰到了HashMap，HashSet，TreeMap，TreeSet等等这样的结构，虽然早有耳闻，但一直不是很清楚怎么用的，是个什么意思。这篇文章就想写写这 集合（Set） 和 映射（Map） 是个什么东西。

其实集合 和 映射 都算是一种容器，一种数据结构，可以来存放数据的容器。

  • 集合（Set）

    特点是 可以去重（一般来说是这样， 但还有他的对立面： 多重集合，就是允许放入重复的元素，但多重集合很少用，目前还没有碰到过，了解这么一个概念就好。），即不允许放入重复的（相等的）元素。

    • 相关应用场景：
    1. 店里客户统计（相同客户只统计一次），
    2. 文本词汇量统计（这里的自然语言处理，比如英文里什么相同单词的时态，人称数的变化等等，怎么判定他们相等，感兴趣的可以去看看）
    3. 网站IP统计， 等等。
    • 底层实现: （在java里）
    1. 可以基于链表， 哈希表实现： （HashSet， LinkedHashSet）
      这样实现的集合没有顺序可言。 即是 一种 无序集合。
    2. 可以基于搜索树实现： （或者说基于 树 结构来实现） （TreeSet）
      这样实现的集合可以有顺序，即是一种 有序集合。

    一般来说，性能优越是： 哈希表实现 > 树实现 > 链表实现 。

    再来看看LeetCode上的804号问题来帮助理解：

    • 题目 ： 唯一的摩尔斯密码

    • 插图片
    • 思路：
      从单词列表中依次拿出每个单词，对应成相应的摩斯密码后，将这个密码加入到 一个集合中（不可以放入重复的值）， 放回这个集合中的元素个数即可。
    • 上代码 
import java.util.TreeSet;
class Solution {
   
    public int uniqueMorseRepresentations(String[] words) {
   
        TreeSet<String> set = new TreeSet<String>();
		String[] codes = {
   ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
		
		for(String word : words) {
   
			StringBuilder res = new StringBuilder(); 
			for(int i = 0; i < word.length(); i++) {
   
				res.append( codes[ word.charAt(i) - 'a' ] );
			}
			set.add(res.toString());
		}
		
		return set.size(); 
    }
}

  • 映射（Map）

    简单来说就是 一种 K，V结构， 存放key 和 value。
    可以根据key来寻找他对应的value是多少。
    当然也可以去重，即相同的K只能存在一个。但主要是使用 根据key查找value这个功能。（相应的也有多重映射，也是了解概念就好）

    • 存储数据说明： （在Python里映射也称为dict）
数据对象 key value
字典（dictionary） 单词 释译
人 身份证号 名字
数据库 id 相关信息
车 车牌号 相关信息
  • 底层实现（在java里）
  1. 可以基于链表，哈希表实现 ; （LinkedHashMap， HashMap）
    这样实现的映射没有顺序可言，即是 无序映射。
  2. 可以基于 树 实现 （TreeMap）
    这样实现的映射可以有顺序，即是一种 有序映射。

  • 比较

对于集合也好，映射也罢。只不过就是存储数据的一种容器而已。
也可以将 集合当成映射来看，只不过此时的每个value都是空，就只有key值。
也可以将 映射当成集合来看，此时每个元素都是2个属性（key，value），
　　　　　　　　　　　　　依据key的不同来划分的每个元素的不同。

同样的来看看几道题来加深印象：

LeetCode 上编号349题 ：
  • 题目 ：
  • 思路：
    因为打印出每个元素是唯一的。
    对第一个数组里元素全部放入一个集合中，在遍历第二个数组里的元素，有相同的，打印，从集合里删除（这样就不会打印出重复的来了）。
  • 上代码： 
class Solution {
   
    public int[] intersection(int[] nums1, int[] nums2) {
   
        TreeSet<Integer> set = new TreeSet<Integer>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int num : nums1) {
   
			set.add(num);
		}
		
		for(int num : nums2) {
   
			if(set.contains(num)) {
   
				list.add(num);
                set.remove(num);
			}
		}
		
		int[] res = new int[list.size()];
		for(int i = 0; i < list.size(); i++) {
   
			res[i] = list.get(i);
		}
		
		return res;
    }
}
LeetCode 上编号350题 ：

  • 题目 ：

  • 思路 ：
    因为打印出来是允许重复的。
    对第一个数组里的元素全放入到一个映射中去，保留那个元素（key），出现了几次（value）这2个信息。
    遍历第二个数组，遇到有在映射里的，打印，同时映射里的相应的key（元素）的value（出现的次数）的值要减1，减到没有了就删除。

  • 上代码：

class Solution {
   
    public int[] intersect(int[] nums1, int[] nums2) {
   
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int num : nums1) {
   
			if(map.containsKey(num)) {
   
				map.put( num, map.get(num)+1 );
			} else {
   
				map.put(num, 1);
			}
		}
		
		for(int num : nums2) {
   
			if(map.containsKey(num)) {
   
				list.add(num);
				if(map.get(num) > 1) {
   
					map.put( num, map.get(num)-1 );
				} else if(map.get(num) == 1) {
   
					map.remove(num);
				}
			} 
		}
		
		int[] res = new int[list.size()];
		for(int i = 0; i < list.size(); i++) {
   
			res[i] = list.get(i);
		}
		
		return res;
    }
}