Java 集合

Qzai 收录于 Java

2022-03-17 约 6243 字预计阅读 13 分钟

Collection

https://img.zhaojq.top/20260728132438965.png — collection

常用方法

add()
addAll()
int size()
void clear()
boolean isEmpty()
boolean contains(Object obj) –通过equals方法判断
boolean containsAll(Collection c) –通过equals方法判断
boolean remove(Object obj) –通过equals方法判断并删除找到的第一个
boolean removeAll(Collection c) –取差集
boolean retainAll(Collection c) –取交集
boolean equals(Object obj) –集合是否相等
Object[] toAarray() –转成对象数据
hashCode() –获取hash值
iterator() –遍历

Iterator遍历

Iterator 对象称为迭代器设计模式的一种 ))，主要用于遍历 Collection 集合中的元素
GOF 给迭代器模式的定义为：提供一种方法访问一个容器 ( 对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、 “空姐
Collection 接口继承了 java.lang.Iterable 接口，该接口有一个 iterator() 方法，那么所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个实现了Iterator 接口的对象
Iterator 仅用于遍历集合 Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合
集合对象每次调用 iterator() 方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前

遍历

        
        
        
    
public class CollectionTest {
    @Test
    public void t2(){
        //错误写法
        Collection collection = new ArrayList();
        collection.add(123);
        collection.add("abc");
        collection.add(false);
        collection.add(456);

        //错误1
        Iterator iterator = collection.iterator();
        while (iterator.next() != null){
            System.out.println(iterator.next());
        }

        //错误2: 每次iterator都是一个新的Iterator迭代器
        while (collection.iterator().hasNext()){
            System.out.println(collection.iterator().next());
        }
    }

    @Test
    public void t1(){
        Collection collection = new ArrayList();
        collection.add(123);
        collection.add("abc");
        collection.add(false);
        collection.add(456);

        Iterator iterator = collection.iterator();
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());

        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

移除 remove()

Iterator 可以删除集合的元素但是是遍历过程中通过迭代器对象的 remove 方法不是集合对象的 remove 方法。
如果还未调用 next() 或在上一次调用 next 方法之后已经调用了 remove 方法再调用 remove 都会报 IllegalStateException

        
        
        
    
public class CollectionTest2 {
    @Test
    public void t1(){
        Collection collection = new ArrayList();
        collection.add(123);
        collection.add("abc");
        collection.add(false);
        collection.add(456);

        Iterator iterator = collection.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next();
            if(next.equals(123)){
                iterator.remove();
            }
        }

        Iterator iterator2 = collection.iterator();
        while (iterator2.hasNext()){
            System.out.println(iterator2.next());
        }
    }
}

foreach() 增强for循环

5.0新增, 底层调用iterator()

Collections

操作Collection、Map的工具类
1.操作排序

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

2.查找,替换

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值

3.同步控制
Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题

List list = Collections.synchronizedList(list);
Map map = Collections.synchronizedMap(list);
…

        
        
        
    
public class CollectionsTest {
    @Test
    public void test2(){
        List list = new ArrayList();
        list.add(123);
        list.add(43);
        list.add(765);
        list.add(-97);
        list.add(0);

        //报异常：IndexOutOfBoundsException("Source does not fit in dest")
//        List dest = new ArrayList();
//        Collections.copy(dest,list);
        //正确的：
        List dest = Arrays.asList(new Object[list.size()]);
        System.out.println(dest.size());//list.size();
        Collections.copy(dest,list);
        System.out.println(dest);

        /*
        Collections 类中提供了多个 synchronizedXxx() 方法，
        该方法可使将指定集合包装成线程同步的集合，从而可以解决
        多线程并发访问集合时的线程安全问题
         */
        //返回的list1即为线程安全的List
        List list1 = Collections.synchronizedList(list);


    }

    @Test
    public void test1(){
        List list = new ArrayList();
        list.add(123);
        list.add(43);
        list.add(765);
        list.add(765);
        list.add(765);
        list.add(-97);
        list.add(0);
        System.out.println(list);

//        Collections.reverse(list);
//        Collections.shuffle(list);
//        Collections.sort(list);
//        Collections.swap(list,1,2);
        int frequency = Collections.frequency(list, 123);

        System.out.println(list);
        System.out.println(frequency);

    }
}

List

鉴于 Java 中数组用来存储数据的局限性，我们通常使用 List 替代数组
List 集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
JDK API 中 List 接口的实现类常用的有： ArrayList 、 LinkedList 和 Vector
常用方法

void add(int index, Object ele) 在 index 位置插入 ele 元素
boolean addAll (int index, Collection) eles 从 index 位置开始将 eles 中的所有元素添加进来
Object get( int index): 获取指定 index 位置的元素
int indexOf (Object obj) 返回 obj 在集合中首次出现的位置
int lastIndexOf (Object obj 返回 obj 在当前集合中末次出现的位置
Object remove( int index): 移除指定 index 位置的元素，并返回此元素
Object set( int index, Object ele) 设置指定 index 位置的元素为 ele
List subList int fromIndex , int toIndex) 返回从 fromIndex 到 toIndex 位置的子集合

ArrayList

ArrayList的源码分析：

jdk 7情况下
ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData
list.add(123);//elementData[0] = new Integer(123);
…
list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。
默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。
结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
jdk 8中ArrayList的变化： ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没有创建长度为10的数组
list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData[0]
… 后续的添加和扩容操作与jdk 7 无异。
小结：jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存

LinkedList

LinkedList的源码分析： LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null
list.add(123);//将123封装到Node中，创建了Node对象。

其中，Node定义为：体现了LinkedList的双向链表的说法

        
        
        
    
   private static class Node<E> {  
       E item;  
       Node<E> next;  
       Node<E> prev;  

       Node(Node<E> prev, E element, Node<E> next) {  
           this.item = element;  
           this.next = next;  
           this.prev = prev;  
       }  
   } 

Vector

jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。在扩容方面，默认扩容为原来的数组长度的2倍

ArrayList 、 LinkedList 和 Vector之间的异同

ArrayList 和 LinkedList 的异同
二者都线程不安全，相对线程安全的Vector ，执行效率高。此外，ArrayList 是实现了基于动态数组的数据结构， LinkedList 基于链表的数据结构。对于随机访问 get 和 set ArrayList 觉得优于 LinkedList ，因为 LinkedList 要移动指针。对于新增和删除操作 add( 特指插入和 remove LinkedList 比较占优势，因为 ArrayList 要移动数据。
ArrayList 和 Vector 的区别
Vector和 ArrayList 几乎是完全相同的唯一的区别在于 Vector 是同步类 ( synchronized)，属于强同步类。因此开销就比 ArrayList 要大，访问要慢。正常情况下大多数的 Java 程序员使用ArrayList 而不是 Vector, 因为同步完全可以由程序员自己来控制。 Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。 Vector 还有一个子类 Stack

Set

Set 接口是Collection 的子接口， set 接口没有提供额外的方法
Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法

特性解读:

无序性:不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
不可重复性:保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个

添加数据:向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()

HashSet

数组+链表的结构,Set接口的主要实现类,线程不安全,可以存储null值
添加过程,以HashSet为例,添加元素a:
1. 首先调用hashCode(),计算hash值,以此hash值通过底层算法计算出在HashSet底层数组中的存放位置(索引位置)
2. 如果此位置没有元素,a添加成功; 如果此位置有其他元素b, 则比较a和b的hash值
3. 如果hash值不相同, a添加成功; 如果hash值相同,则调用equals方法
4. equals为true, 则a添加失败; 反之

https://img.zhaojq.top/20260728133912690.png — hashSet

LinkedHashSet extends HashSet

HashSet的子类,遍历内部数据时,可以按照添加的顺序遍历

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序这使得元素看起来是以插入顺序保存的。
LinkedHashSet 插入性能略低于 HashSet 但在迭代访问 Set 里的全

TreeSet

可以按照添加对象的指定属性，进行排序
向TreeSet中添加的数据，要求是相同类的对象

自然排序

比较两个对象是否相同的标准为：compareTo()返回0.不再是equals()

BigDecimal 、 BigInteger 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较
Character ：按字符的 unicode 值来进行比较
Boolean true 对应的包装类实例大于 false 对应的包装类实例
String ：按字符串中字符的 unicode 值进行比较
Date 、 Time ：后边的时间、日期比前面的时间、日期大

        
        
        
    
//自然排序
@Test
public void t2(){
    TreeSet set = new TreeSet();
    set.add(new User("Tom",12));
    set.add(new User("Jerry",32));
    set.add(new User("Jim",2));
    set.add(new User("Mike",65));
    set.add(new User("Jack",33));
    set.add(new User("Jack",56));


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

//user
package collection.collection;

public class User implements Comparable{
    private String name;
    private int age;

    public User() {
    }

    public User(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;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("User equals()....");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        User user = (User) o;

        if (age != user.age) return false;
        return name != null ? name.equals(user.name) : user.name == null;
    }

    @Override
    public int hashCode() { //return name.hashCode() + age;
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }


    //按照姓名从大到小排列,年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        System.out.println("User compareTo");
        if(o instanceof User){
            User user = (User)o;
//            return -this.name.compareTo(user.name);
            int compare = -this.name.compareTo(user.name);
            if(compare != 0){
                return compare;
            }else{
                return Integer.compare(this.age,user.age);
            }
        }else{
            throw new RuntimeException("输入的类型不匹配");
        }

    }
}

定制排序

比较两个对象是否相同的标准为：compare()返回0.不再是equals()

        
        
        
    
//定制排序
@Test
public void t3(){
    Comparator com = new Comparator() {
        //按照年龄从小到大排列
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof User && o2 instanceof User){
                User u1 = (User)o1;
                User u2 = (User)o2;
                return Integer.compare(u1.getAge(),u2.getAge());
            }else{
                throw new RuntimeException("输入的数据类型不匹配");
            }
        }
    };

    TreeSet set = new TreeSet(com);
    set.add(new User("Tom",12));
    set.add(new User("Jerry",32));
    set.add(new User("Jim",2));
    set.add(new User("Mike",65));
    set.add(new User("Mary",33));
    set.add(new User("Jack",33));
    set.add(new User("Jack",56));


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

常见题

        
        
        
    
//去重
@Test
public void t4(){
    List list = new ArrayList();
    list.add(new Integer(1));
    list.add(new Integer(2));
    list.add(new Integer(2));
    list.add(new Integer(4));
    list.add(new Integer(4));
    List list2 = duplicateList(list);
    for (Object integer : list2) {
        System.out.println(integer);
    }
}
public static List duplicateList(List list) {
    HashSet set = new HashSet();
    set.addAll(list);
    return new ArrayList(set);
}

@Test
public void test5(){
    HashSet set = new HashSet();
    User u1 = new User("Tom",12);
    User u2 = new User("Jack",15);

    set.add(u1);
    set.add(u2);
    System.out.println(set);

    u1.setName("cc");
    set.remove(u1);//会失败,add时是以Tom为hash值对应的位置,以cc得到的hash值不在以Tom为hash值的位置
    System.out.println(set);
    set.add(new User("cc",12));//新位置
    System.out.println(set);
    set.add(new User("Tom",12));//也能加成功,hashCode值一样,但equals的时候不一样,因为u1变为cc了
    System.out.println(set);

}

Map

https://img.zhaojq.top/20260728132459851.png — map

Map 与 Collection 并列存在。用于保存具有映射关系的数据 :key value
Map 中的 key 和 value 都可以是任何引用类型的数据
Map 中的 key 用 Set 来存放，不允许重复，即同一个 Map 对象所对应的类，须重写 hashCode 和 equals 方法
常用 String 类作为 Map 的“键”
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value
Map 接口的常用实现类： HashMap 、 TreeMap 、 LinkedHashMap 和Properties 。其中， HashMap 是 Map 接口使用频率最高的实现类

常用方法

添加,删除,修改

Object put(Object key, Object value)
void putAll(Map m)
Object remove(Object key)
Object clear()
查询

Object get(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()
boolean equals(Object obj)
无视图操作

Set keySet() –返回所有key构成的Set集合
Collection values() –返回所有value构成的Collection集合
Set entrySet() –返回所有key-value构成的Set集合

HashMap

存储结构

1.7 数组+链表
1.8 数组+链表+红黑树
实例化

1.7 底层创建了长度是16的一维数组 Entry[] table
1.8 底层没有创建一个长度为16的数组(jdk8底层数组是Node[] ,而不是Entry[]),首次put时创建
put(k,v)

首先,调用k所在类hashCode()计算k的 hash值,此hash值经过某种算法计算以后,得到Entry数组中的存放位置
如果此位置数据为空,则k-v添加成功
如果此位置数据不为空(存在1个或多个数据以链表形式存在),则比较k的hash值

如果hash值不相同,则k-v添加成功

如果hash值不相同,则通过k的equals方法比较

如果equals() 返回false, 则k-v添加成功
如果equals() 返回true, 则使用v替换相同k的value值

1.7: 在不断扩容过程中,当超过临界值且该位置不为Null,默认的扩容方式:扩容为原来容量的2位,并把旧的数据copy过来
1.8: 当数组的某一个索引位置上的元素以链表形式存在的数据个数>8 && 当前数组长度>64时,此时索引位置上的所有数据改为使用红黑树存储
源码关键参数

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，=容量填充因子：16 0.75 => 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64
加载因子的大小影响

负载因子的大小决定了 HashMap 的数据密度。
负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长造成查询或插入时的比较次数增多，性能会下降。
负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
按照其他语言的参考及研究经验，会考虑将负载因子设置为 0.7~0.75 ，此时平均检索长度接近于常数

LinkedHashMap extends HashMap

LinkedHashMap 是 HashMap 的子类

在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序

        
        
        
    
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

与 LinkedHashSet 类似 LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key V alue 对的插入顺序一致

        
        
        
    
public class MapTest2 {
    @Test
    public void t2(){
        LinkedHashMap map = new LinkedHashMap();
        map.put(111, 1);
        map.put(222, 2);
        map.put(333, 3);

        System.out.println(map);//{111=1, 222=2, 333=3}
    }

    @Test
    public void t1(){
        HashMap map = new HashMap();
        map.put(111, 1);
        map.put(222, 2);
        map.put(333, 3);

        System.out.println(map);//{333=3, 222=2, 111=1}
    }
}

TreeMap

TreeMap 存储 Key Value 对时，需要根据 key value 对进行排序。TreeMap 可以保证所有的 Key Value 对处于有序状态。
TreeSet 底层使用红黑树结构存储数据
TreeMap 的 Key 的排序：

自然排序 TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口

TreeMap 判断两个 key 相等的标准：两个 key 通过 compareTo() 方法或者 compare() 方法返回 0

        
        
        
    
/**
 * 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
 * 因为要按照key进行排序：自然排序 、定制排序
 */
public class TreeMapTest {
    //定制排序
    @Test
    public void test2(){
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User && o2 instanceof User){
                    User u1 = (User)o1;
                    User u2 = (User)o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }
                throw new RuntimeException("输入的类型不匹配！");
            }
        });
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);

        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);

        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());

        }
    }

    //自然排序
    @Test
    public void test1(){
        TreeMap map = new TreeMap();
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);

        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);

        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());

        }
    }
}

HashTable

Hashtable 是个旧的 Map 实现类，JDK1.0 就提供了。不同于 HashMap,Hashtable 是线程安全的。
Hashtable 实现原理和 HashMap 相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
与 HashMap 不同， Hashtable 不允许使用 null 作为 key 和 value
与 HashMap 一样， Hashtable 也不能保证其中 Key Value 对的顺序
Hashtable 判断两个 key 相等、两个 value 相等的标准与 HashMap一致

Properties extends HashTable

Properties 类是 Hashtable 的子类，该对象用于处理属性文件
由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key和 value 都是字符串类型
存取数据时，建议使用 setProperty (String key,String value) 方法和getProperty (String) 方法

        
        
        
    
/**
 * 处理配置文件
 * 
 * map包下放test.properties文件
 * name=zhjq
 * sex=female
 * age=18
 */
public class PropertiesTest {
    public static void main(String[] args) throws IOException {
        Properties properties = new Properties();
        properties.load(new FileInputStream("src/collection/map/test.properties"));
        String name = properties.getProperty("name");
        System.out.println(name);

        Set<Map.Entry<Object, Object>> entries = properties.entrySet();
        for (Map.Entry<Object, Object> entry : entries) {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }
    }
}

目录

Java 集合

Collection

常用方法

Iterator遍历

遍历

移除 remove()

foreach() 增强for循环

Collections

List

ArrayList

LinkedList

Vector

ArrayList 、 LinkedList 和 Vector之间的异同

Set

HashSet

LinkedHashSet extends HashSet

TreeSet

自然排序

定制排序

常见题

Map

常用方法

HashMap

LinkedHashMap extends HashMap

TreeMap

HashTable

Properties extends HashTable