乐趣区

关于java:Java-集合

Java 汇合是一个罕用的技术,无论是在: 开发应用,还是面试总是高频的提及到~

  • 正因如此: 本篇是对集体应用汇合的, 总结 办法 … 不适宜初学者, 适宜面试 | 温习...

Java 汇合

汇合和数组:

  • 数组申明了它包容的元素的类型,而汇合能够不申明 存储 Object 类型 能够通过泛型进行标准!
  • 数组是动态的,一个数组实例具备固定的大小,一旦创立了就无奈扭转容量了。
    汇合是能够动静扩大容量,能够依据须要动静扭转大小,汇合提供更多的成员办法,能满足更多的需要。
  • 汇合: 和数组一样 Java 中用来存储数据的作用,补救了数组长度固定的毛病更灵便

Java 汇合框架概述

Java 汇合可分为 Collection 和 Map 两种体系

Collection 接口: 单列数据,定义了存取一组对象的办法的汇合

  • List:元素有序、可反复的汇合
  • Set:元素无序、不可反复的汇合

Map 接口:双列数据,保留具备映射关系 key-value 的汇合

Collection 接口:

简介

Collection 汇合次要有 List 和 Set 两大接口 不罕用的 Queue 接口

List 接口

  • 一个有序,(元素存入汇合的程序和取出的程序统一) 的汇合容器 元素能够反复,能够插入多个 null 元素,元素都有索引
  • 有三个实现类: ArrayList LinkedList Vector

Set 接口

  • 一个无序,(存入和取出程序有可能不统一) 的汇合容器

    • 不能够存储反复元素,只容许存入一个 null 元素 必须保障元素唯一性
  • 罕用实现类: HashSet LinkedHashSet TreeSet

Collection 接口的罕用办法:

JDK 不提供此接口的任何间接实现,而是提供更具体的子接口:set list 都默认继承了 Collection 的办法();

boolean        .add(object);                // 在列表 开端添元素 和数组一样 起始索引地位从 0 开使, 可储存 null; 数值类型会主动装箱;
void        .add(int,object);            // 指定索引地位增加元素 但 不可指定 在超过目前 汇合长度;
void        .forEach(System.out::print);//jdk8 新个性; 一种循环遍历;    
void        .clear();                    // 清空集合;
int            .size();                    // 返回汇合元素个数; 
boolean        .contains(object);        // 判断汇合在是否存在指定元素; ture/flase; 底层相当于是调 equls(); 比,String 类重写了所以比拟的是值;
                                        // 没重写当然就是比拟地址咯;
boolean        .containAll(Collection);    // 判断参数是个汇合, 判断参数汇合本人有没有, 都有就 true 一个没有就 false
boolean        .equals(Coll...);            // 想要返回 true, 须要以后汇合元素 和 参数汇合元素值都雷同 地址 ; 依据 new ArrayList 或其它汇合 / 其程序也要雷同;
Object        .get(int);                // 返回指定索引的元素;(留神这是 Object 类型须要类型转换);
List        .sublist(int1,int2);        // 返回汇合 1-2 地位的子集合;
Object        .set(int,Object);            // 设置指定 int 地位的元素;


留神不能够在, 汇合进行循环遍历的时候移除元素!   因为汇合长度发送扭转, 循环遍历报错!Object        .remove(int);                // 删除指定下标中的元素; 返回删除的元素;
boolean        .remove(object/int);        // 移除汇合中指定元素; true 移除胜利 false 移除失败: 不存在要移除元素; 
                                        // 尽管数值类型会装箱,int 下标删除了.. 须要确保下标存在
boolean        .removeAll(Collection);    // 从汇合中移除指定: 一个汇合元素; 两个汇合 A B, A.removeAll(B); // 把 A B 汇合中一样的元素移除掉了(交加);

正确的删除须要应用:Iterator 对象~
Iterator    .iterator();                // 返回一个 Iterator 对象; 

数组汇合互相转换
Object[]    .toArray();                    // 能够将汇合返回一个 Object[] 数组;
汇合           Arrays.aslist(数组);         //Arrays 类的静态方法: 将数组转换成汇合;

List 接口

Arraylist

Arraylist: 对数组进行封装, 实现长度可变的数组(依据增删主动扭转元素在汇合中地位)

  • Arraylist 底层其实就是一个,能够动静调节长度的数组

    • JDK1.7:ArrayList 饿汉式,间接创立一个初始容量为 10 的数组
    • JDK1.8:ArrayList 懒汉式,一开始创立一个长度为 0 的数组,当增加第一个元素时再创立一个始容量为 10 的数组
  • 优: 更利于遍历 和随机拜访元素

根本应用:

  • 开发罕用的就是这个,这里就以 Arraylist 举例了
public void jh(){
    /** 创立汇合对象 */
    //      Collection coll = new ArrayList();
    ArrayList arrayList = new ArrayList();      //List 汇合存储 Object 类型元素, 反对反复元素!
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(2);
    arrayList.add(3);
    arrayList.add("2");
    arrayList.add(null);                        // 能够存储 null
    System.out.println("arrayList 汇合遍历:");
    for (Object o : arrayList) {System.out.println(o);
    }

    /** 罕用办法 */
    //contains(Object obj): 判断以后汇合中是否蕴含 obj   : 判断时会调用 obj 对象所在类的 equals(), 自定义对象须要重写 equals
    System.out.println("arrayList 汇合是否存在 1:"+arrayList.contains(1));

    //containsAll(Collection coll1) 判断形参 coll1 中的所有元素是否都存在于以后汇合中
    ArrayList arrayList2 = new ArrayList();
    arrayList2.add(1);
    arrayList2.add(2);
    System.out.println("arrayList 汇合是否存在 arrayList2 的所有元素:"+arrayList.containsAll(arrayList2));

    //retainAll(Collection coll1): 交加:获取以后汇合和 coll1 汇合的交加,并返回给以后汇合
    //        arrayList.retainAll(arrayList2);
    //        System.out.println("retainAll(Collection coll1): 交加:获取以后汇合和 coll1 汇合的交加,并返回给以后汇合");
    //        for (Object o : arrayList) {//            System.out.println(o);
    //        }

    /** 正文下面: retainAll() 让两个汇合元素 A.retainAll(B) A 汇合只保留 B 交加独特的数据了~ */
    //remove(Object obj): 从以后汇合中移除 obj 元素
    //removeAll(Collection coll1): 差集:从以后汇合中移除 coll1 中所有的元素
    arrayList.removeAll(arrayList2);
    System.out.println("removeAll(Collection coll1): 差集:从以后汇合中移除 coll1 中所有的元素");
    for (Object o : arrayList) {System.out.println(o);
    }

    /** 数组 ———》List 汇合 */
    System.out.println("应用: Arrays. asList(array) 进行转换");
    List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
    System.out.println(list);

    /** List 汇合 ———》数组 */
    System.out.println("应用: List 自带的 toArray() 办法");
    Object[] objects = list.toArray();
    for (Object obj : objects) {if(obj instanceof String)           // 对象 instanceof 类型  比拟对象是否属于改类型~
            System.out.print(obj+" ");
    }
}

LinkedList

LinkedList:采纳双向链表存储形式

  • 优:

    在插入删除时效率更高,同 Arraylist 一样都实现 list 接口比 Arraylist 多了一些办法 毛病就是查找遍历没有 Arraylist 快

LinkedList 新增办法

void    .addFist(object);            // 在汇合 首部 增加元素 (索引 0);
void    .addLast(object);            // 在汇合 开端 增加元素;
Object    .getFist( );                // 返回 第一元素;
Object    .getLast( );                // 返回 最初一个元素; 
Object    .removrFist( );            // 删除 并 返回第一个元素;
Object    .removeLast();            // 删除 并 返回最初一个元素;    

Vector

Vector 读:歪课特 远古代码,jdk1.0 就有的

  • 通过 Vector(); 结构器创建对象:

    底层就创立了长度为 10 的数组, 扩容方面就是扩大为原数组长度的二倍;

ArrayList/LinkedList/vector 的异同?

ArrayList 和 LinkedList 的异同

  • 二者都是线程不平安的,绝对于线程平安的 Vector,执行效率高
  • ArrayList 是实现了基于动静数组的数据结构,LinkedList 是基于链表的数据结构
  • 对于随机拜访 get 和 set: ArrayList 优于 LinkedList, LinkedList 要挪动指针
  • 对于新增(特质插入)add 和删除 remove 操作LinkedList 占优,因为 ArrayList 要挪动数据

ArrayList 和 Vector 的异同:

  • Vector 和 ArrayList 简直是完全相同的
  • Vector 是同步类(Synchronized), 强同步类: 开销就比 ArrayList 大,拜访要慢~
  • Vector 每次扩容申请其大小的 2 倍空间,而 ArrayList 是 1.5 倍

Set 接口

简介:

Set 接口实现 Collection 接口

  • 存储一组 无序的 (不等于随机, 而是依据数据的哈希值决定的), 不可反复 的,汇合数据
  • Set 接口中没有额定定义新的办法, 应用的都是 Collection 中申明过的办法:
  • Set 接口的实现类:HashSet LinkedHashSet TreeSet

HashSet

  • 惟一,无序。基于 HashMap 实现,底层采纳 HashMap 保留数据

  • 它不容许汇合中有反复的值,

    将对象存储在 HashSet 之前,要先确保对象重写 equals()和 hashCode()办法,这样能力比拟对象的值是否相等,以确保 set 中没有贮存相等的对象

LinkedHashSet: 作为 HashSet 子类, 遍历器外部数据时, 能够依照增加的程序遍历

  • 作为 HashSet 类的子类, 在增加数据同时, 每个数据还保护两个援用, 记录了此数据前一个数据和后一个数据
  • 优:频繁的遍历操作, 效率高

ThreeSet

  • 有序,惟一):红黑树(自均衡的排序二叉树

向 TreeSet 增加的数据,要求是雷同的类型的

  • 自定义类须要:指定排序规定

    天然排序: 定义类继承 Comparable 重写 compareTo(obj);

    定制排序: TreeSet 在 new 时就传入一个 Comparator 类对象

List 数据去重

五种无效办法:

  1. [计划一: 借助 HashSet 的个性进行去重]
  2. [计划二 : 利用 set 汇合个性放弃程序统一去重] TreeSet LinkedHashSet
  3. [计划三 : 应用 list 本身办法 remove()–>不举荐 ] 循环遍历判断,remove()
  4. [计划四 : 应用 Java8 个性去重]
/** 计划一 */
@org.junit.Test
    public  void distinct() {List<String> lists = Arrays.asList(new String[]{"AA", "BB", "CC","CC"});
    HashSet<String> sets = new HashSet<>();
    for (String s : lists) {sets.add(s);
    }
    System.out.println("去重后的 Set 汇合:"+sets);
}

@org.junit.Test
    /** 计划二 */
    public  void distinct2() {List<String> lists = Arrays.asList(new String[]{"AA", "BB", "CC","CC"});
    // 形式一
    List<String> listNew = new ArrayList<String>(new TreeSet<String>(lists));
    System.out.println("TreeSet"+listNew);
    // 形式二
    List<String> listNew2 = new ArrayList<String>(new LinkedHashSet<String>(lists));
    System.out.println("LinkedHashSet"+listNew);
}

@org.junit.Test
    /** 计划四 */
    public  void distinct4() {List<String> lists = Arrays.asList(new String[]{"AA", "BB", "CC","CC"});
    List<String> myList = lists.stream().distinct().collect(Collectors.toList());
    System.out.println("JDK8.0 新个性:"+myList);
}

Iterator 迭代器接口

Iterator 中:迭代器 读:艾特瑞特~

能够通过,Collection 类的 .iterator() 办法返回一个 Iterator 迭代器对象

  • Map 中存在 keySet()办法返回 Set 类型对象,Set 接口实现 Collection 因而间接存在 iterator(); 办法 ….

Iterator 接口的办法

boolean    hasNext();  // 判断是否 存在下一个可拜访的元素;
Object    next();        // 返回要拜访的下一个元素;
void    remove();    // 移除以后的汇合元素可保障从源汇合中平安地删除对象;     留神(图:Iterator 移除)
  • 迭代器是通过 汇合.iterator() 办法获取 示意对该汇合的迭代
  • 迭代器存在 游标的概念:
  • 默认游标都在汇合的第一个元素之前 因而:通过 Next(); 获取下一个元素!
  • 留神: 在调用 it.next()办法之前必须要调用 it.hasNext()进行检测

    若不调用,且下一条记录有效间接调用 i.next()会抛出 NoSuchElementException 异样。

Iterator 仅用于遍历汇合

边遍历边批改 汇合 的惟一正确形式是应用 Iterator.remove() 办法,如下:

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();}

一种最常见的错误代码如下:

for(Integer i : list){list.remove(i)
}
  • 运行以上错误代码会报 ConcurrentModificationException 异样
  • 这是因为当应用 foreach(for(Integer i : list)) 语句时,会主动生成一个 iterator 来遍历该 list
  • 但同时该 list 正在被 .remove() 批改。Java 个别不容许一个线程在遍历 Collection 时另一个线程批改它

Map 接口:

简介

双列汇合, 存储一对 key-value 数据 —》

  • K 键:无序 惟一
  • V 值:无序 反复;

HashMap: 作为 Map 的次要实现类;线程不平安的,效率高;容许存储 null 的 key 和 value

  • LinkedHashMap: 保障在遍历 map 元素时,能够依照增加的程序实现遍历

    起因: 在原有的 HashMap 底层构造根底上,增加了一对指针,指向前一个和后一个元素

    对于频繁的遍历操作,此类执行效率高于 HashMap

TreeMap: 保障依照增加的 key-value 对进行排序,实现排序遍历。此时思考 key 的天然排序或定制排序 底层应用红黑树

Hashtable: 作为古老的实现类

  • 线程平安的,效率低;不能存储 null 的 key 和 value
  • Properties: 罕用来解决配置文件。key 和 value 都是 String 类型

实现类有:

  • HashMap LinkedHasMap TreeMap Hashtable(jdk1.0) Properties

Map 罕用办法:

Object    .put(Object key,Object value);    // 以 键值对 形式存储  留神(键 惟一 值 能够反复 // 雷同的键 前面的代替后面的 键值对 元素)Object    .get(key);                        // 依据键 返回对应的值对象不存在对应键 返回 null;
Object    .remove(key);                    // 依据键 删除指定 键值对 对象
int        .size();                        // 返回元素个数
boolean .containsKey(object key);        // 判断 是否存在 指定键值对 对象;
boolean .isEmpty();                        // 判断 是否存在 键值对 对象
void    .clear();                        // 清空该汇合所有 元素;
Set        .keySet();                        // 返回 键的汇合 Set 类型汇合;    set 是 Collection 的实现类, 通过 .iterator(); 办法返回一个 Iterator 对象, 进行遍历!Collection    .values();                    // 返回 值的汇合 collection 类型汇合;

实例:

@Test
public void mapTest(){Map map = new HashMap();       // 只能存储 K 惟一, 值能够反复的元素, 反复的 key 会代替之前的数据!map.put(1, "AA");
    map.put(1, "AA");
    map.put(1, "BB");
    map.put(2, "AA");
    map.put(2, "BB");
    map.put(3, "CC");

    System.out.println("遍历所有的 key-value");
    System.out.println("形式一: entrySet()");
    Set entrySet = map.entrySet();                  // 获取所有的: entrySet()办法返回一个实现 Map.Entry 接口的对象汇合
    Iterator iterator1 = entrySet.iterator();       //set 属于 collection.iterator(); 获取迭代器!while (iterator1.hasNext()){Object obj = iterator1.next();
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "---->" + entry.getValue());
    }
    System.out.println();
    System.out.println("形式二: 迭代器");
    // 形式二:
    Set keySet = map.keySet();
    Iterator iterator2 = keySet.iterator();
    while(iterator2.hasNext()){Object key = iterator2.next();
        Object value = map.get(key);
        System.out.println(key + "=====" + value);

    }
    System.out.println();
    System.out.println("形式三: 通过 ForEach 循环进行遍历: 此数省略~");
    System.out.println();
    System.out.println("形式四: 通过 Java8 Lambda 表达式遍历:");
    map.forEach((k, v) -> System.out.println("key:" + k + "value:" + v));

    System.out.println();
    System.out.println("依据 Key 寻找 value="+map.get(1));

    System.out.println("remove(Object key) 依据 key 移除元素~");

    System.out.println();
    System.out.println("boolean containsKey(Object key): 是否蕴含指定的 key"+map.containsKey(1));

    System.out.println();
    System.out.println("map.clear()   清空 map, 与 map = null 操作不同");
    System.out.println("map.isEmpty() 判断 map 是否为空");
}

Map.Entry 的定义

Map 的 entrySet()办法返回一个实现 Map.Entry 接口的对象汇合

  • 汇合中每个对象都是底层 Map 中一个特定的键 / 值对 通过这个汇合的迭代器 取得每一个条数据的键或值

Map.Entry 中的罕用办法

  • Object getKey(): 返回条目标关键字
  • Object getValue(): 返回条目标值
  • Object setValue(Object value): 将相干映像中的值改为 value,并且返回旧值

常见面试题:

汇合源码解析

HashMap 的底层实现原理?

在 JDK 1.7 中 HashMap 是以数组加链表的模式组成的

JDK 1.8 之后新增了红黑树的组成构造,当链表大于 8 并且容量大于 64 时,链表构造会转换成红黑树结构

HashMap 基于 Hash 算法实现的:

  • 当咱们往 Hashmap 中 put 元素时
  • 首先计算 keyhash 值,这里调用了 hash办法

    hash办法理论是让 key.hashCode()key.hashCode()>>>16进行, 异或操作 目标是缩小碰撞

    >>> 无符号右移    3>>>1: 3 无符号右移一位等于 3/2=1 (三 除 二的一次幂) 二进制码最高位无论是 0 或 1 都 0 示意, 后果为一个负数;
    &   与运算符    二进制码 0: true 1:false 将两个二级制码一一位 码进行比拟, 返回成一个新的二级制码; 就是它的后果;
    ^   异运算符    二进制码 0: true 1:false 将两个二级制码一一位 码进行比拟, 返回成一个新的二级制码; 就是它的后果;
    |   或运算符    二进制码 0: true 1:false 将两个二级制码一一位 码进行比拟, 返回成一个新的二级制码; 就是它的后果;
    
    计算机的每个对象最终都会本义成二进制:
    0101010101001
    而: 与 异 或 就是针对这些二进制操作的运算符
    & 与运算符 
        a &= b; 等同于 a = a & b;        有 0 为 0,否则为 1
        0 & 0 = 0;
        1 & 1 = 1;
        1 & 0 = 0;
        
    | 或运算符    
        有 1 为 1,否则为 0
        0 | 0 = 0;
        1 | 1 = 1;
        1 | 0 = 1;
        
    ^ 异运算符
        雷同为 0,不同为 1
        0 ^ 0 = 0;
        1 ^ 1 = 0;
        1 ^ 0 = 1;
    异 或 与 就是将两边的对象的 二进制每一个值进行比拟, 返回一个新的对象~      

咱们都晓得 HashMap 底层实现是: 数组 + 链表 JDK8: 数组 + 链表 + 红黑树

  • 依据 K 的 hashCode() 计算出 哈希值 进行取模算法, 失去在一个在数组上的坐标.
  • 判断数组的坐标上是否存在元素, 没有就 间接新增, 如果存在则: ③
  • 与该坐标的元素 hash 值一样, 则比拟两个元素的 equals(); 如果 equals() 不同则新增, 如果雷同则不新增 笼罩该元素!
  • JDK8.0
  • 遍历 table[i],判断链表长度是否大于 8 , 大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;
  • 插入胜利后,判断理论存在的键值对数量 size 是否超多了最大容量 threshold,如果超过,进行扩容

HashMap 和 Hashtable 的异同?

雷同:

  • 都是 K-V 存储构造
  • HashMap 和 HashTable 都实现了 Serializable 接口,因而它反对序列化,实现了 Cloneable 接口,能被克隆

不同:

  • HashMap 的初始容量为 16,Hashtable 初始容量为 11,两者的填充因子默认都是 0.75
  • HashMap 是非线程平安的,只是用于单线程环境下 多线程环境下能够采纳 concurrent 并发包下的 concurrentHashMap HashTable 是线程平安的
  • HashMap 中 key 和 value 都容许为 null key 为 null 的键值对永远都放在以 table[0]为头结点的链表中
  • HashTable 在遇到 null 时,会抛出 NullPointerException 异样

HashMap 中 String、Integer 这样的包装类适宜作为 K?

String、Integer 等包装类的个性可能保障 Hash 值的不可更改性和计算准确性,可能无效的缩小 Hash 碰撞的几率

  • 都是 final 类型,即不可变性,保障 key 的不可更改性,不会存在获取 hash 值不同的状况
  • 外部已重写了 equals()hashCode() 等办法,恪守了 HashMap 外部的标准

泛型

JDK5.0 新增

  • 是程序设计语言的一种格调或范式 , 泛型容许程序员在强类型程序,编写代码时应用一些特定的[类型]
  • 这种参数类型能够用在: 接口 办法中,== 别离被称为泛型类、泛型接口、泛型办法 ==
  • 汇合中存储的对象 什么都是 Object 类型因而 每次获取 都须要 进行 类型判断转换 instanceof

    泛型汇合 在汇合的根底上 指定存储类型

    List<String>

退出移动版