JAVA中的双列集合

Collection是单列集合，Map是双列集合,值得注意的是，Map接口是独立的接口，并没有继承Collection接口，现在重点介绍Map。

Map的常见API

??????? Map是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用

????????HashMap是Map接口最常用的实现类，存储Key Value键值对，HashMap不保证元素的顺序但保证Key必须唯一。

V put(K key,V value)                    添加元素
V remove(Object key)                    根据键删除键值对元素
void clear()                            移除所有的键值对元素
boolean containsKey(Object key)         判断集合是否包含指定的键
boolean containsValue(Object value)     判断集合是否包含指定的值
boolean isEmpty()                       判断集合是否为空
int size()                              集合的长度，也就是集合中键值对的个数

1.1 添加元素

使用HashMap添加元素有以下3个方法：

1. put
2. putIfAbsent
3. putAll

首先看下put()方法的使用方法：

HashMap<String, String> platformMap = new HashMap<>();

// 添加元素
System.out.println(platformMap.put("cnblogs.com", "博客园"));
System.out.println(platformMap.put("juejin.im", "掘金"));
System.out.println(platformMap.put("map.weixin.qq.com", "微信公众号"));
System.out.println(platformMap.put("zwwhnly.com", "个人博客"));

// 添加重复的Key,没有添加成功,但是会更新Key对应的Value值
// 不过代码不会报错,而是返回已经存在Key对应的Value
System.out.println(platformMap.put("zwwhnly.com", "个人博客"));

?

2. Hashtable使用

Hashtable也是Map接口的实现类，值得注意的是，它的方法都是同步的，即是线程安全的。

public synchronized int size() {
    return count;
}

public synchronized boolean isEmpty() {
    return count == 0;
}

HashTable类的代码声明如下所示：

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
{
	......
}

从以上代码也能看出，Hashtable的基类是Dictionary，而HashMap的基类是AbstractMap（这里是重点，面试常问）。

HashTable类的使用方法和HashMap基本一样，只需修改下声明处的代码即可：

Hashtable<String, String> platformMap = new Hashtable<>();
Hashtable<String, String> majorPlatfromMap = new Hashtable<>();
Hashtable<String, String> otherPlatformMap = new Hashtable<>();

?

?

?这个是具体的使用

public class A01_MapDemo1 {
    public static void main(String[] args) {
        /*
            V put(K key,V value)                    添加元素
            V remove(Object key)                    根据键删除键值对元素
            void clear()                            移除所有的键值对元素
            boolean containsKey(Object key)         判断集合是否包含指定的键
            boolean containsValue(Object value)     判断集合是否包含指定的值
            boolean isEmpty()                       判断集合是否为空
            int size()                              集合的长度，也就是集合中键值对的个数
        */

        //创建Map集合的对象
        Map<String,String> m = new HashMap<>();

        //添加元素
        //put键会覆盖原来，不存在则添加到Map集合中；不存在则覆盖
        //
        m.put("李良熙","丁美兮");
        m.put("林彧","宝莲");
        m.put("阿珍","阿强");

        String result = m.remove("李良熙");
        System.out.println(result);

        //清空
        //m.clear();

        //判断是否包含
        /*boolean keyResult = m.containsKey("阿珍");
        System.out.println(keyResult);

        boolean valueResult = m.containsValue("段应九");
        System.out.println(valueResult);*/

        boolean result02 = m.isEmpty();
        System.out.println(result02);
        System.out.println(m);
    }
}

放一道leetcode.219上面的题目吧

给你一个整数数组?nums?和一个整数?k?，判断数组中是否存在两个?不同的索引?i?和?j?，满足?nums[i] == nums[j]?且?abs(i - j) <= k?。如果存在，返回?true?；否则，返回?false?。

示例?1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false
提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

?在下拙见如下：

class Solution {
    /**
     * 判断数组中是否存在重复元素，并且重复元素的索引差不超过k
     * @param nums 给定的整数数组
     * @param k 索引差的最大值
     * @return 存在重复元素且索引差不超过k返回true，否则返回false
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 创建一个HashMap用于存储元素和对应的索引
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            // 如果map中已经存在该元素，并且当前索引与之前存储的索引差不超过k，则返回true
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }
            // 将元素和对应的索引存入map中
            map.put(num, i);
        }
        // 遍历完数组后仍未找到满足条件的重复元素，返回false
        return false;
    }
}

?/*
??????? 每个班级80名学生，现在需要组织活动
??????? 班长提供了四个景点依次是（A，B，C，D）
??????? 每个学生只能选择一个景点，请统计处哪个景点去的人最多

??????? */

public class A06_HashMapDemo2 {
    public static void main(String[] args) {
       /*
        每个班级80名学生，现在需要组织活动
        班长提供了四个景点依次是（A，B，C，D）
        每个学生只能选择一个景点，请统计处哪个景点去的人最多

        */
        String[] arr = {"A","B","C","D"};
        ArrayList<String> list = new ArrayList<>();
        Random r = new Random();
        for(int i = 0; i<80;i++){
            int index = r.nextInt(arr.length);
            list.add(arr[index]);
        }

        HashMap<String,Integer> hm = new HashMap<>();

        for (String name : list){
            if (hm.containsKey(name)) {
                int count = hm.get(name);
                count++;
                hm.put(name,count);
            }else{
                hm.put(name,1);

            }
        }

        // 找出人数最多的景点
        int maxCount = 0;
        String maxSpot = "";
        for (Map.Entry<String, Integer> entry : hm.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                maxSpot = entry.getKey();
            }
        }

        System.out.println("人数最多的景点是：" + maxSpot);
    }
}

?四种遍历方法

public static void main(String[] args) {
Map<String,String> map=new HashMap<String,String>();
    map.put("1", "value1");
    map.put("2", "value2");
    map.put("3", "value3");
    map.put("4", "value4");
    
    //第一种：普通使用，二次取值(性能差)
    System.out.println("\n通过Map.keySet遍历key和value：");  
    for(String key:map.keySet())
    {
     System.out.println("Key: "+key+" Value: "+map.get(key));
    }
    
    //第二种(性能比第一种好，一次取值)
    System.out.println("\n通过Map.entrySet使用iterator遍历key和value: ");  
    Iterator map1it=map.entrySet().iterator();
    while(map1it.hasNext())
    {
     Map.Entry<String, String> entry=(Entry<String, String>) map1it.next();
     System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
    }
    
    //第三种：推荐，尤其是容量大时  
    System.out.println("\n通过Map.entrySet遍历key和value");  
    for(Map.Entry<String, String> entry: map.entrySet())
    {
     System.out.println("Key: "+ entry.getKey()+ " Value: "+entry.getValue());
    }
    
    //第四种  
    System.out.println("\n通过Map.values()遍历所有的value，但不能遍历key");  
    for(String v:map.values())
    {
     System.out.println("The value is "+v);
    }

?

3. LinkedHashMap使用

LinkedHashMap也是Map接口的实现类，相比于HashMap，它使用到了链表，因此可以保证元素的插入顺序，即FIFO(First Input First Output 先进先出)。

LinkedHashMap类的代码声明如下所示：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	......
}

从以上代码也能看出，LinkedHashMap类继承了HashMap类。

LinkedHashMap类的使用方法和HashMap基本一样，只需修改下声明处的代码即可：

LinkedHashMap<String, String> platformMap = new LinkedHashMap<>();
LinkedHashMap<String, String> majorPlatfromMap = new LinkedHashMap<>();
LinkedHashMap<String, String> otherPlatformMap = new LinkedHashMap<>();

4. TreeMap使用

TreeMap也是Map接口的实现类，值得注意的是，TreeMap中的元素是有序的，默认的排序规则是按照key的字典顺序升序排序。

TreeMap类的代码声明如下所示：

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
	......
}

TreeMap类的使用方法和HashMap基本一样，只需修改下声明处的代码即可：

TreeMap<String, String> platformMap = new TreeMap<>();
TreeMap<String, String> majorPlatfromMap = new TreeMap<>();
TreeMap<String, String> otherPlatformMap = new TreeMap<>();

5. HashMap、Hashtable、LinkedHashMap、TreeMap的区别(面试常问)

5.1 相同点

1)HashMap、Hashtable、LinkedHashMap、TreeMap都实现了Map接口

2)四者都保证了Key的唯一性，即不允许Key重复

5.2 不同点

5.2.1 排序

HashMap不保证元素的顺序

Hashtable不保证元素的顺序

LinkHashMap保证FIFO即按插入顺序排序

TreeMap保证元素的顺序，支持自定义排序规则

空口无凭，上代码看效果：

HashMap<String, String> hashMap = new HashMap<>();
Hashtable<String, String> hashtable = new Hashtable<>();
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
TreeMap<String, String> treeMap = new TreeMap<>();

String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
    hashMap.put(letter, letter);
    hashtable.put(letter, letter);
    linkedHashMap.put(letter, letter);
    treeMap.put(letter, letter);
}

System.out.println("HashMap(我不保证顺序):" + hashMap);
System.out.println("Hashtable(我不保证顺序):" + hashtable);
System.out.println("LinkedHashMap(我保证元素插入时的顺序):" + linkedHashMap);
System.out.println("TreeMap(我按排序规则保证元素的顺序):" + treeMap);

上面代码的输出结果为：

HashMap(我不保证顺序):{A=A, B=B, C=C, D=D, E=E}

Hashtable(我不保证顺序):{A=A, E=E, D=D, C=C, B=B}

LinkedHashMap(我保证元素插入时的顺序):{B=B, A=A, D=D, C=C, E=E}

TreeMap(我按排序规则保证元素的顺序):

5.2.2 null值

HashMap，LinkedHashMap允许添加null值(Key和Value都允许)，所以以下代码是合法的：

HashMap<String, String> hashMap = new HashMap<>();
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();

hashMap.put(null, null);
linkedHashMap.put(null, null);

TreeMap不允许Key有null值，但允许Value有null值，所以以下代码是合法的：

TreeMap<String, String> treeMap = new TreeMap<>();

treeMap.put("cnblogs.com", null);

但是treeMap.put(null, null);会引发java.lang.NullPointerException异常：

Hashtable不允许添加null值(Key和Value都不允许)，添加null值时会抛出java.lang.NullPointerException异常。

Hashtable<String, String> hashtable = new Hashtable<>();

hashtable.put("cnblogs.com", null);
hashtable.put(null, null);

运行上面的代码，报错信息如下所示：

5.2.3 线程安全

HashMap、LinkedHashMap、TreeMap不是线程安全的。

Hashtable是线程安全的，这是它的优点，同时也导致在理论情况下，Hashtable的效率没有HashMap高。

所以如果对线程安全没有要求，建议使用HashMap。

5.2.4 继承

Hashtable的父类是Dictionary。

HashMap的父类是AbstractMap。

LinkedHashMap的父类是HashMap，HashMap的父类是AbstractMap，所以LinkedHashMap也继承了AbstractMap。

TreeMap的父类是AbstractMap。

6. TreeMap的两种排序方式(面试常问)

TreeMap默认的排序规则是按照key的字典顺序升序排序。

先来看下TreeMap存储String类型的例子：

TreeMap<String, String> treeMap = new TreeMap<>();

String[] letterArray = new String[]{"B", "A", "D", "C", "E"};
for (String letter : letterArray) {
    treeMap.put(letter, letter);
}

for (String key : treeMap.keySet()) {
    System.out.println("key:" + key + ",Value:" + treeMap.get(key));
}

输出结果：

key:A,Value:A

key:B,Value:B

key:C,Value:C

key:D,Value:D

key:E,Value:E

那如果TreeMap中放入的元素类型是我们自定义的引用类型，它的排序规则是什么样的呢？

带着这个疑问，我们新建个Student类如下：

package collection;

public class Student {
    private String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

然后添加如下验证代码：

TreeMap<Student, Student> studentTreeMap = new TreeMap<>();

Student student1 = new Student("zhangsan", 20);
Student student2 = new Student("lisi", 22);
Student student3 = new Student("wangwu", 24);
Student student4 = new Student("zhaoliu", 26);

Student student5 = new Student("zhangsan", 22);

studentTreeMap.put(student1, student1);
studentTreeMap.put(student2, student2);
studentTreeMap.put(student3, student3);
studentTreeMap.put(student4, student4);
studentTreeMap.put(student5, student5);

for (Student student : studentTreeMap.keySet()) {
    System.out.println("name:" + student.getName() + ",age:" + student.getAge());
}

满心欢喜的运行代码想看下效果，结果却发现报如下错误：

为什么会这样呢？

这是因为我们并没有给Student类定义任何排序规则，TreeMap说我也不知道咋排序，还是甩锅抛出异常吧，哈哈。

怎么解决呢？有以下两种方式：

1. 自然排序
2. 比较器排序

6.1 自然排序

自然排序的实现方式是让Student类实现接口Comparable，并重写该接口的方法compareTo，该方法会定义排序规则。

package collection;

public class Student implements Comparable<Student> {
    // 省略其它代码

    @Override
    public int compareTo(Student o) {
        return 0;
    }
}

使用IDEA默认生成的compareTo()方法如上所示。

这个方法会在执行add()方法添加元素时执行，以便确定元素的位置。

如果返回0，代表两个元素相同，只会保留第一个元素

如果返回值大于0，代表这个元素要排在参数中指定元素o的后面

如果返回值小于0，代表这个元素要排在参数中指定元素o的前面

因此如果对compareTo()方法不做任何修改，直接运行之前的验证代码，会发现集合中只有1个元素：

name:zhangsan,age:20

然后修改下compareTo()方法的逻辑为：

@Override
public int compareTo(Student o) {
    // 排序规则描述如下
    // 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
    // 如果姓名的长度相同，按字典顺序比较String
    // 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面

    int orderByNameLength = this.name.length() - o.name.length();
    int orderByName = orderByNameLength == 0 ? this.name.compareTo(o.name) : orderByNameLength;
    int orderByAge = orderByName == 0 ? this.age - o.age : orderByName;

    return orderByAge;
}

再次运行之前的验证代码，输出结果如下所示：

name:lisi,age:22

name:wangwu,age:24

name:zhaoliu,age:26

name:zhangsan,age:20

name:zhangsan,age:22

6.2 比较器排序

比较器排序的实现方式是新建一个比较器类，继承接口Comparator，重写接口中的Compare()方法。

注意：使用此种方式Student类不需要实现接口Comparable，更不需要重写该接口的方法compareTo。

package collection;

import java.util.Comparator;

public class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        // 排序规则描述如下
        // 按照姓名的长度排序,长度短的排在前面,长度长的排在后面
        // 如果姓名的长度相同，按字典顺序比较String
        // 如果姓名完全相同,按年龄排序,年龄小的排在前面,年龄大的排在后面

        int orderByNameLength = o1.getName().length() - o2.getName().length();
        int orderByName = orderByNameLength == 0 ? o1.getName().compareTo(o2.getName()) : orderByNameLength;
        int orderByAge = orderByName == 0 ? o1.getAge() - o2.getAge() : orderByName;

        return orderByAge;
    }
}

然后修改下验证代码中声明studentTreeSet的代码即可：

TreeMap<Student, Student> studentTreeMap = new TreeMap<>(new StudentComparator());

输出结果和使用自然排序的输出结果完全一样。

?