侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Map

coydone
2021-02-06 / 0 评论 / 0 点赞 / 320 阅读 / 10,477 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Map接口

我们通过查看Map接口描述,发现Map接口下的集合与Collection接口下的集合,它们存储数据的形式不同。

Collection中的集合,元素是孤立存在的(理解为单身),向集合中存储元素采用一个个元素的方式存储。

Map中的集合,元素是成对存在的(理解为夫妻)。每个元素由键与值两部分组成,通过键可以找对所对应的值。

Collection中的集合称为单列集合,Map中的集合称为双列集合。

需要注意的是,Map中的集合不能包含重复的键,值可以重复;每个键只能对应一个值。

Map中常用的集合为HashMap、LinkedHashMap、TreeMap。HashMap是Map最常用子类。

Map接口常用方法

Map体系的通用方法
Map的特点:
    Map中key不允许重复,如果用重复,重复的key对应的新的value会覆盖掉原有的value
    key的存的顺序和取的顺序不一定一致
    HashMap底层也是使用的哈希算法,哈希算法针对key,key的唯一性原理和HashSet一样

    interface Map<K,V>{//K(key) V(value)
    V put(K key, V value):把key-value的键值对存入到了Map集合
                            当没有key重复的时候,返回null
                            当有key重复的时候,新值会覆盖老值,返回老值

    V get(Object key):根据传入的key从Map中获取对应的value
    V remove(Object key):根据key来移除这个键值对,而且返回被移除的键值对的值(value)
    int size():返回的是Map的键值对个数
    void clear():清空Map中所有的键值对
    boolean containsKey(Object key):判断是否包含指定的key,如果包含返回true,如果不包含返回false
    boolean containsValue(Object key):判断是否包含指定的Value,如果包含返回true,如果不包含返回false
    boolean isEmpty():判断Map中是否有键值对,有返回false,一个都没有才返回true
    Set keySet():获取Map集合中所有的key,存储到Set集合中
    Set<Map.Entry<K,V>> entrySet():返回一个Set基于Map.Entry类型包含Map中所有映射

HashMap

HashMap是Map接口的接口实现类,它采用哈希算法实现,是Map接口最常用的实现类。由于底层采用了哈希表存储数据,所以要求键不能重复,如果发生重复,新的值会替换旧的值。HashMap在查找、删除、修改方面都有非常高的效率。

import java.util.HashMap;
public class Demo {
    public static void main(String[] args) {
        //创建Map对象
        //要求:夫妻姓名信息 夫--妻
        HashMap<String,String> map = new HashMap<>();
        //Map key不允许重复,Map始终保存最后一次存入的键值对
        map.put("邓超","其他明星");
        map.put("邓超","孙俪");
        map.put("文章","马伊琍");
        map.put("黄晓明","杨颖");
        //通过邓超获取媳妇的名字
        System.out.println(map.get("邓超"));//孙俪
        //输出一共几对夫妻
        System.out.println(map.size());//3
        //查询有没有"文章"这个键
        System.out.println(map.containsKey("文章"));//true
        //查询有没有"马伊琍"这个值
        System.out.println(map.containsValue("马伊琍"));//true
    }
}

Map集合的遍历

键集:keyset()遍历key:通过key获取对应的value。

值集:values():遍历value,只能获取值。

键值集:entrySet():一次性获取所有的键值对。

Map.Entry接口的由来

/*
 * 内部类:把一个类定义在另外一个类的内部
 *  class A{
 *    class B{
 *    }
 *  }
 * 内部接口:把一个接口定义在另外一个接口中
 *   interface 接口名1{
 *      interface 接口名2{
 *      }
 *   }
 */
interface Father {// 外部接口
    interface Inner {// 内部接口
        public void method();// Inner接口中的抽象方法
    }
}
class Son implements Father.Inner {// 实现内部接口需要写成 外部接口名.内部接口名
    @Override
    public void method() {
        System.out.println("重写method()方法");
    }
}

public class Demo{
    public static void main(String[] args) {
        Son s=new Son();
        s.method();
    }
}

Map接口中的内部接口

public interface Map<K, V> {//Map外部接口

    interface Entry<K, V> {//Entry上的K,V随着Map上K,V变化

        //内部接口
        //定义了两个抽象方法
        K getKey();
        V getValue();
    }
}

//在HashMap中实现了Map接口的内部接口Entry接口
class HashMap<K, V> {
    static class Entry<K, V> implements Map.Entry<K, V> {//成员内部类,通过一个内部类实现了Map的内部接口
        K key;//定义了key
        V value;//定义value

        //重写getKey方法
        public final K getKey() {//获取key的值
            return key;
        }

        //重写getValue方法
        public final V getValue() {//获取value的值
            return value;
        }
    }
}

结论:Map.Entry中封装了key、value,并且提供了获取key和value的方法(getKey,getValue)

遍历示例

import java.util.*;
public class Demo {
    public static void main(String[] args) {
        HashMap<String,String> map = new HashMap<>();
        map.put("邓超","孙俪");
        map.put("文章","马伊琍");
        map.put("黄晓明","杨颖");

        //获取键集  Set<K> k= map.keySet()
        Set<String> key = map.keySet();
        //增强for
        for (String sKey:key) {
            System.out.println(sKey+"===="+map.get(sKey));
        }
        //迭代器
        Iterator<String> it = key.iterator();
        while (it.hasNext()){
            String k = it.next();
            System.out.println(k+"===="+map.get(k));
        }

        //遍历值集  Collection<V> v = map.values();
        Collection<String> values = map.values();
        //增强for
        for (String v : values) {
            System.out.println(v);
        }
        //迭代器
        Iterator<String> it2 = values.iterator();
        while (it2.hasNext()){
            System.out.println(it2.next());
        }

        //键值对集合 Set<Map.Entry<K,V>> = map.entrySet()
        /*
        * Entry是一个内部类
        * public class A{
        *   //B内部类
        *   class B{}
        *   属性、方法、构造方法
        * }
        * */
        Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry : entries) {
            System.out.println(entry.getKey()+"===="+entry.getValue());
        }
        Iterator<Map.Entry<String, String>> it3 = entries.iterator();
        while (it3.hasNext()){
            Map.Entry<String, String> ks = it3.next();
            System.out.println(ks.getKey()+"===="+ks.getValue());
        }
    }
}

HashMap底层

1、基于哈希表(数组+链表+二叉树(红黑树)),JDK1.8。

2、默认加载因子为0.75,默认数组大小是16。

3、把对象存储到哈希表中,存储原理:

把key对象通过hash()方法计算hash值,然后用这个hash值对数组长度取余数(默认16),来决定该对key对象在数组中存储的位置,当这个位置有多个对象时,以链表结构存储,JDK1.8后,当链表长度大于等于8时,链表将转换为红黑树结构存储。这样的目的,是为了取值更快,存储的数据量越大,性能表现越明显。

4、扩充原理:当数组的容量超过了75%,那么表示该数组需要扩充。扩充的算法是:当前数组容量<<1(相当于是乘2),扩大1倍。扩充次数过多,会影响性能,每次扩充表示哈希表重新散列(重新计算每个对象的存储位置),我们在开发中尽量要减少扩充次数带来的性能问题。

5、线程不安全,适合在单线程中使用。

底层存储

HashMap底层实现采用了哈希表,这是一种非常重要的数据结构。

数据结构中由数组和链表来实现对数据的存储,他们各有特点:

  • 数组:占用空间连续。寻址容易,查询速度快。但是,增加和删除效率非常低。

  • 链表:占用空间不连续。寻址困难,查询速度慢。但是,增加和删除效率非常高。

那么,能不能结合数组和链表的优点(即查询快,增删效率也高)呢?答案就是“哈希表”。哈希表的本质就是”数组+链表”。

在JDK1.8的HashMap中对于数组的初始化采用的是延迟初始化方式。通过resize()方法实现初始化处理。resize()方法既实现数组初始化,也实现数组扩容处理。

计算Hash值

1、获得key对象的hashcode。首先调用key对象的hashcode()方法,获得key的hashcode值。

2、根据hashcode计算出hash值(要求在 [0,数组长度-1] 区间)

hashcode是一个整数,我们需要将它转化成 [0,数组长度-1] 的范围。我们要求转化后的hash值尽量均匀地分布在 [0,数组长度-1] 这个区间,减少“hash 冲突”。

  • 一种极端简单和低下的算法是:hash值= hashcode/hashcode;也就是说,hash值总是1。意味着,键值对对象都会存储到数组索引1位置,这样就形成一个非常长的链表。相当于每存储一个对象都会发生”hash冲突”,HashMap 也退化成了一个“链表”。

  • —种简单和常用的算法是(相除取余算法):hash值 = hashcode%数组长度。这种算法可以让hash 值均匀的分布在 [0,数组长度-1] 的区间。但是,这种算法由于使用了”除法”,效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂,这样采用位运算即可实现取余的效果:hash 值=hashcode&(数组长度-1)

TreeMap

TreeMap和HashMap同样实现了Map接口,所以,对于API的用法来说是没有区别的。HashMap效率高于TreeMap;TreeMap是可以对键进行排序的一种容器,在需要对键排序时可选用TreeMap。TreeMap底层是基于红黑树实现的。

在使用TreeMap时需要给定排序规则:元素自身实现比较规则、通过比较器实现比较规则。

操作步骤同TreeSet集合。

public class User implements Comparable<User> {
	@Override
    public int compareTo(User o) {
        if (age > o.getAge()) {
            return 1;
        }
        return -1;
    }
}

//外部比较器
class UserComparator implements Comparator<User> {

    @Override
    public int compare(User o1, User o2) {
        if (o1.getAge() > o2.getAge()) {
            return 1;
        }
        return -1;
    }
}

LinkedHashSet与Hashtable集合

/*HashMap与LinkedHashMap
    HashMap不能保证key的存的顺序和取的顺序一致,
    但是LinkedHashMap可以保证key的存取顺序一致
 HashMap与Hashtable
    HashMap既可以存储null值的 key 也可以存储 null值的 value
    Hashtable不允许使用null值的key和null值的value
*/

集合嵌套

嵌套概述

集合嵌套并不是一个新的知识点,仅仅是集合内容又是集合,如Collection集合嵌套、Collection集合与Map集合相互嵌套、Map集合嵌套。

/*
 1、ArrayList嵌套 ArrayList
     ArrayList< ArrayList<String> >
     Collection< ArrayList<Integer> >
 2、Map嵌套 ArrayList
     HashMap<String, ArrayList<Person>>
     ArrayList< HashMap<String, String>>
 3、Map集合嵌套
     HashMap<String, HashMap<String,String>>
     HashMap<String, HashMap<Person,String>>
*/

Map嵌套Map

举例:Map集合嵌套

让班级名称对应一个班级,而在每个班级中都让学生的学号对应学生的姓名。

import java.util.HashMap;
public class Demo {
    public static void main(String[] args) {
        //1.先构造Java班的HashMap
        HashMap<String,String> javaHM=new HashMap<>();
        javaHM.put("1001","张三");
        javaHM.put("1002","李四");
        javaHM.put("1003","王五");
        //2.在构造C++班的HashMap
        HashMap<String,String> cPlusHM=new HashMap<>();
        cPlusHM.put("1001","Tom");
        cPlusHM.put("1002","Jack");
        cPlusHM.put("1003","Mark");
        //3.在构造班级名称和班的对应关系
        HashMap<String, HashMap<String,String>> hm=new HashMap<>();
        hm.put("java班", javaHM);
        hm.put("C++班",cPlusHM);
        //遍历这个嵌套集合使用keySet或EntrySet
        //从外向内遍历
        for(String className :hm.keySet()){//外层循环遍历班级名称
            HashMap<String,String> classRoom =hm.get(className);//根据班级名称获取对应的班(教师)
            for(String sno : classRoom.keySet()){//内层循环遍历班中的学生的学号和姓名
                String sname =classRoom.get(sno);//根据学生的学号获取姓名
                System.out.println(className+" "+sno+" "+sname);
            }
        }
        //C++班 1003 Mark
        //C++班 1002 Jack
        //C++班 1001 Tom
        //java班 1003 王五
        //java班 1002 李四
        //java班 1001 张三
    }
}

Collections与Arrays

可变参数

在JDK1.5之后,如果我们定义一个方法需要接受多个参数,并且多个参数类型一致,我们可以对其简化成如下格式:

修饰符 返回值类型 方法名(参数类型... 形参名){ }其实这个书写完全等价与修饰符 返回值类型 方法名(参数类型[] 形参名){ }

只是后面这种定义,在调用时必须传递数组,而前者可以直接传递数据即可。

JDK1.5以后。出现了简化操作。 用在参数上,称之为可变参数。

同样是代表数组,但是在调用这个带有可变参数的方法时,不用创建数组(这就是简单之处),直接将数组中的元素作为实际参数进行传递,其实编译成的class文件,将这些元素先封装到一个数组中,在进行传递。这些动作都在编译.class文件时,自动完成了。

/*
 * JDK1.5新特性:
 *   可变参数底层就是数组,可变参数不但能接收数组,而且能接收任意多个参数
 *   可变参数如果定义必须放在形参列表末尾
 */
public class Demo {
    public static void main(String[] args) {
        //int[] arr={1,2,3,4};
        //method(arr);//传数组给可变参数是可以的
        method(4,7,8,9);//当传入4,7,8,9会自动把4,7,8,9封装到arr中
    }
    public static void method(int... arr){
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }   
}
public class Demo {
    public static void main(String[] args) {
        method(4,10,12);
    }
    /*
       当调用method(4,3,2)的时候,4,3,2都会被封装到arr中
	     m接收不到任何值
       public static void method(int... arr,int m){
             for(int i=0;i<arr.length;i++){
                 System.out.println(arr[i]);
             }
        }*/
    public static void method(int m,int... arr){
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }
}

Arrays/Collections工具类

Arrays中定义了大量的操作数组的方法例如对数组排序,对数组使用二分查找,将数组转换为字符串等,而且都是静态方法,可以通过类名直接调用。

Collections中定义了大量的操作集合的方法,例如对集合排序,对集合使用二分查找,方法也都是静态的,都可以通过类名直接调用。

常见方法:

  • void sort(List):对List容器内的元素排序,排序的规则是按照升序进行排序。

  • void shuffle(List):对List容器内的元素进行随机排列。

  • void reverse(List):对List容器内的元素进行逆续排列。

  • void fill(List, Object):用一个特定的对象重写整个List容器。

  • int binarySearch(List, Object):对于顺序的List容器,采用折半查找的方法查找特定对象。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/*
 *  Arrays:是一个工具类,专门操作数组的工具类
 *    public static <T> List<T> asList(T... a)//可以将数组转换成集合
 *    static int binarySearch(int[] a, int key)
       static void sort(int[] a)
 *
 * Collections:是一个类,专门对集合操作的工具类,可以对集合中的元素排序,对集合中的元素反转..
 *    <T> int binarySearch(List list,T key)
 *    void sort(List<T> list)
 * Collection:是一个接口,单列集合的顶级父接口
 */
public class Demo {
    public static void main(String[] args) {
        //method01();
        //method02();
        //method03();
        //method04();
        ArrayList<Integer> al=new ArrayList<>();
        al.add(4);
        al.add(1);
        al.add(10);
        al.add(6);
        Collections.sort(al);//对集合进行排序
        System.out.println(al);//[1, 4, 6, 10]
    }

    private static void method04() {
        ArrayList<Integer> al=new ArrayList<>();
        al.add(1);
        al.add(4);
        al.add(6);
        al.add(10);
        int index = Collections.binarySearch(al,4);
        System.out.println(index);//1
    }

    private static void method03() {
        int[] arr={7,9,11,13,16};
        Arrays.sort(arr);//数组排序
        for (int ele : arr) {
            System.out.println(ele);
        }
    }

    private static void method02() {
        int[] arr={1,3,5,7,9};
        int index= Arrays.binarySearch(arr,7);//利用二分查找查找7
        System.out.println(index);//3
    }

    private static void method01() {
        int[] arr={12,23,46};
        List<int[]> asList = Arrays.asList(arr);
        System.out.println(asList);//[[I@1540e19d]
        //集合中存储的元素是一个数组的地址值
        //因为我们使用是基本类型数组,而集合只能存储引用类型
        //所以当我们将基本类型的数组转换集合的时候它会把数组对象存入集合

        Integer[] arr2={12,23,46};//12,23,46都会自动装箱
        List<Integer> asList2 = Arrays.asList(arr2);
        System.out.println(asList2);//[12, 23, 46]
    }
}
0

评论区