2018-12-25 java集合框架总结

1.List,Set,Map之间的区别

List:对付顺序的好帮手

List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象

Set:注重独一无二的性质

不允许重复的集合。不会有多个元素引用相同的对象。

Map:用Key来搜索的专家

使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象,但Key不能重复,典型的Key是String类型,但也可以是任何对象。

2.ArrayList与LinkedList的区别

Arraylist底层使用的是数组(存读数据效率高,插入删除特定位置效率低),LinkedList底层使用的是双向循环链表数据结构(插入,删除效率特别高)。学过数据结构这门课后我们就知道采用链表存储,插入,删除元素时间复杂度不受元素位置的影响,都是近似O(1)而数组为近似O(n),因此当数据特别多,而且经常需要插入删除元素时建议选用LinkedList.一般程序只用Arraylist就够用了,因为一般数据量都不会蛮大,Arraylist是使用最多的集合类。

3.ArrayList 与 Vector 区别

ArrayList是Vector的高级版,它是用来替换Vector的,ArrayList是线程不安全的,Vector的所有方法都是同步的,故当2个线程同时访问的时候要花费大量的时间,故用ArrayList来替换他。

4.HashMap 和 Hashtable 的区别

1.HashMap是线程不安全的,HashTable是线程安全的,HashTable的内部方法基本都使用synchronized修饰。
2.HashMap比HashTable效率高,HashTable基本被淘汰。
3.HashMap允许有键值都为null,HashTable键值都不可以为null,否则会报NullPointerException。
Hashtable和HashMap有几个主要的不同:线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable,而如果你使用Java5或以上的话,请使用ConcurrentHashMap吧


图片.png

5.HashMap 和 ConcurrentHashMap 的区别

1.ConcurrentHashMap采用锁分段技术,将整个Hash桶进行了分段segment,也就是将这个大的数组分成了几个小的片段segment,而且每个小的片段segment上面都有锁存在,那么在插入元素的时候就需要先找到应该插入到哪一个片段segment,然后再在这个片段上面进行插入,而且这里还需要获取segment锁。相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。)

2.HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。

6. HashSet如何检查重复

当我们将对象存入到HashSet当中的时候,HashSet会调用当前对象的HashCode()进行比较,如果该HashCode已经存在,HashSet会调用equals()方法进行比较,如果两者相同,HashSet就不会让加入操作成功,如果不同就使用拉链法插入。

(一)hashCode()与equals()的相关规定:

如果两个对象相等,则hashcode一定也是相同的
两个对象相等,对两个equals方法返回true
两个对象有相同的hashcode值,它们也不一定是相等的
综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

(二)==与equals()

  1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
  2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较.
    3.==指引用是否相同 equals()指的是值是否相同

7.comparable与comparator的区别

1.comparable接口是java.lang下的包,他有一个compareTo(Object obj)方法用来排序。
2.Comparator接口是java.util下的包,有一个compare(Object obj1, Object obj2)方法用来排序。

一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序

(一)Comparator定制排序

package com.xd.map;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Test8 {    

   public static void main(String[] args) {
       
       ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.add(-1);
        arrayList.add(3);
        arrayList.add(3);
        arrayList.add(-5);
        arrayList.add(7);
        arrayList.add(4);
        arrayList.add(-9);
        arrayList.add(-7);
        System.out.println("原始数组:");
        System.out.println(arrayList);
        System.out.println("****************************定制化排序**********************************");
        //集合反转
        Collections.reverse(arrayList);
        System.out.println(arrayList);
        //将list集合的后面4个数转换到前面
        Collections.rotate(arrayList, 4);
        System.out.println(arrayList);
        //将list集合的前4个数放到后面
        Collections.rotate(arrayList, -4);
        System.out.println(arrayList);

        //按照自然排序升序排序
        Collections.sort(arrayList);
        System.out.println(arrayList);
   }
}
   

重写compareTo方法实现按年龄来排序

ackage cn.demo;
 
public class Student implements Comparable{
    private int number=0;           //学号
    private String name="";         //学生姓名
    private String gender="";       //性别
    public int getNumber(){
        return number;
    }
    public void setNumber(int number){
        this.number=number;
    }
    public String getName(){
        return name;
    }
    public void setName(String name){
        this.name=name;
    }
    public String getGender(){
        return gender;
    }
    public void setGender(String gender){
        this.gender=gender;
    }
    
    public int compareTo(Object obj){
        Student student=(Student)obj;
        if(this.number==student.number){  
            return 0;           //如果学号相同,那么两者就是相等的
        }else if(this.number>student.getNumber()){ 
            return 1;           //如果这个学生的学号大于传入学生的学号
        }else{ 
            return -1;          //如果这个学生的学号小于传入学生的学号
        }
    }
}

package cn.demo;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
 
public class Test {
    public static void main(String[] args) {
        Student student1=new Student();
        student1.setNumber(5);
        Student student2=new Student();
        student2.setNumber(2);
        Student student3=new Student();
        student3.setNumber(1);
        Student student4=new Student();
        student4.setNumber(4);
        ArrayList<Student> list=new ArrayList<Student>();
        list.add(student1);
        list.add(student2);
        list.add(student3);
        list.add(student4);
        System.out.println("-------排序前-------");
        Iterator<Student> iterator=list.iterator();
        while(iterator.hasNext()){
            Student stu=iterator.next();
            System.out.println(stu.getNumber());
        }
        //使用Collections的sort方法对list进行排序
        System.out.println("-------排序后-------");
        Collections.sort(list); 
        iterator=list.iterator();
        while(iterator.hasNext()){
            Student stu=iterator.next();
            System.out.println(stu.getNumber());
        } 
 
    }
}

如何对Object的list排序

对objects数组进行排序,我们可以用Arrays.sort()方法
对objects的集合进行排序,需要使用Collections.sort()方法

8.如何实现数组与List的相互转换

List转数组:toArray(arraylist.size()方法;数组转List:Arrays的asList(a)方法

    List<String> arrayList = new ArrayList<String>();
        arrayList.add("s");
        arrayList.add("e");
        arrayList.add("n");
        /**
         * ArrayList转数组
         */
        int size=arrayList.size();
        String[] a = arrayList.toArray(new String[size]);
        //输出第二个元素
        System.out.println(a[1]);//结果:e
        //输出整个数组
        System.out.println(Arrays.toString(a));//结果:[s, e, n]
        /**
         * 数组转list
         */
        List<String> list=Arrays.asList(a);
        /**
         * list转Arraylist
         */
        List<String> arrayList2 = new ArrayList<String>();
        arrayList2.addAll(list);
        System.out.println(list);

如何求ArrayList集合的交集 并集 差集 去重复并集

需要用到List接口中定义的几个方法:

addAll(Collection<? extends E> c) :按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾 实例代码:
retainAll(Collection<?> c): 仅保留此列表中包含在指定集合中的元素。
removeAll(Collection<?> c) :从此列表中删除指定集合中包含的所有元素。
package com.xd.map;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test9 {    

   public static void main(String[] args) {
       
       List<Integer> list1 = new ArrayList<Integer>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);

        List<Integer> list2 = new ArrayList<Integer>();
        list2.add(2);
        list2.add(3);
        list2.add(4);
        list2.add(5);
        // 并集
        // list1.addAll(list2);
        // 交集
        //list1.retainAll(list2);
        // 差集
        //list1.removeAll(list2);
        // 无重复并集
        list2.removeAll(list1);
        list1.addAll(list2);
        for (Integer i : list1) {
            System.out.println(i);
        } 
   }
}   

HashMap 的工作原理及代码实现

集合框架源码学习之HashMap(JDK1.8)

ConcurrentHashMap 的工作原理及代码实现

ConcurrentHashMap实现原理及源码分析

9.集合框架底层数据结构总结

Collection

1. List

  • Arraylist:数组(查询快,增删慢 线程不安全,效率高 )
  • Vector:数组(查询快,增删慢 线程安全,效率低 )
  • LinkedList:链表(查询慢,增删快 线程不安全,效率高 )

2. Set

  • HashSet(无序,唯一):哈希表或者叫散列集(hash table)
  • LinkedHashSet:链表和哈希表组成 。 由链表保证元素的排序 , 由哈希表证元素的唯一性
  • TreeSet(有序,唯一):红黑树(自平衡的排序二叉树。)

- Map

  • HashMap:基于哈希表的Map接口实现(哈希表对键进行散列,Map结构即映射表存放键值对)
  • LinkedHashMap:HashMap 的基础上加上了链表数据结构
  • HashTable:哈希表
  • TreeMap:红黑树(自平衡的排序二叉树)

集合的选用

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用Map接口下的集合,需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时,就选择实现Collection接口的集合,需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet,不需要就选择实现List接口的比如ArrayList或LinkedList,然后再根据实现这些接口的集合的特点来选用。

10. Arraylist 与 LinkedList 异同

  • 1. 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
  • 2. 底层数据结构: Arraylist 底层使用的是Object数组;LinkedList 底层使用的是双向链表数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注意双向链表和双向循环链表的区别:); 详细可阅读JDK1.7-LinkedList循环链表优化
  • 3. 插入和删除是否受元素位置的影响:ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e) 方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element) )时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)而数组为近似 O(n)。
  • 4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。
  • 5. 内存空间占用: ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。

补充内容:RandomAccess接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

ArraysList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。

下面再总结一下 list 的遍历方式选择:

实现了RadmoAcces接口的list,优先选择普通for循环 ,其次foreach,
未实现RadmoAcces接口的ist, 优先选择iterator遍历(foreach遍历底层也是通过iterator实现的),大size的数据,千万不要使用普通for循环

ArrayList 与 Vector 区别

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。

HashMap 和 Hashtable 的区别

   1.线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
   2.效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
   3.对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛出 NullPointerException。
   4.初始容量大小和每次扩充容量大小的不同 : ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小(HashMap 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
   5.底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

HashMap,Hashtable,ArrayList初始容量大小

  • Arraylist的初始容量是10,每次扩容之后容量都会变为原来的 1.5 倍!
  • HashMap的初始容量是16,之后每次扩充,容量变为原来的2倍,创建时如果给定了容量初始值,而 HashMap 会将其扩充为2的幂次方大小。
  • Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1,创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小。

HashMap 多线程操作导致死循环问题

在多线程下,进行 put 操作会导致 HashMap 死循环,原因在于 HashMap 的扩容 resize()方法
注意:jdk1.8已经解决了死循环的问题。

11.HashSet 和 HashMap 区别

hashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。)

图片.png

12. ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) ****对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。***(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率(默认分配16个Segment,比Hashtable效率提高16倍。)

图片.png

图片.png

13.ConcurrentHashMap线程安全的具体实现方式/底层具体实现

首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

14.集合框架底层数据结构总结

Collection

1. List

  • Arraylist: Object数组
  • Vector: Object数组
  • LinkedList: 双向链表(JDK1.6之前为循环链表,JDK1.7取消了循环) 详细可阅读JDK1.7-LinkedList循环链表优化

2. Set

  • HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素
  • LinkedHashSet: LinkedHashSet 继承与 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样,不过还是有一点点区别的。
  • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。)

Map

  • HashMap: JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间
  • LinkedHashMap: LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
  • HashTable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
  • TreeMap: 红黑树(自平衡的排序二叉树)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容

  • Java集合类可用于存储数量不等的对象,并可以实现常用的数据结构如栈,队列等,Java集合还可以用于保存具有映射关...
    小徐andorid阅读 1,915评论 0 13
  • 原文地址 Java集合 Java集合框架:是一种工具类,就像是一个容器可以存储任意数量的具有共同属性的对象。 Ja...
    gyl_coder阅读 973评论 0 8
  • 一、集合入门总结 集合框架: Java中的集合框架大类可分为Collection和Map;两者的区别: 1、Col...
    程序员欧阳阅读 11,530评论 2 61
  • 在一个方法内部定义的变量都存储在栈中,当这个函数运行结束后,其对应的栈就会被回收,此时,在其方法体中定义的变量将不...
    Y了个J阅读 4,413评论 1 14
  • 在第二课时教学中,我以学生为本、以读为主线,引导学生采用多种形式的朗读如指名读、小组读、师范读、齐读、男女生合作读...
    莫名_3afe阅读 179评论 0 0