博客

java中的各集合

转自：

来源

• List , Set, Map都是接口，前两个继承至Collection接口，Map为独立接口
• Set下有HashSet，LinkedHashSet，TreeSet
• List下有ArrayList，Vector，LinkedList
• Map下有Hashtable，LinkedHashMap，HashMap，TreeMap
• Collection接口下还有个Queue接口，有PriorityQueue类

• 注意:
  

• Queue接口与List、Set同一级别，都是继承了Collection接口。
  
  看图你会发现,LinkedList既可以实现Queue接口,也可以实现List接口.只不过呢, LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

• SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。

转载声明：原文转自

http://www.cnblogs.com/xiezie/p/5511840.html

这里要讨论这些常用的默认初始容量和扩容的原因是：

当底层实现涉及到扩容时，底层是数组的容器或重新

分配一段更大的连续内存

（如果是离散分配则不需要重新分配，离散分配都是插入新元素时动态分配内存），

要将容器原来的数据全部复制到新的内存上

，这无疑使效率大大降低。

加载因子的系数小于等于1，意指  即当 元素个数 超过 容量长度*加载因子的系数 时，进行扩容。

另外，扩容也是有默认的倍数的，不同的容器扩容情况不同。

List

1、ArrayList

线程不安全、非同步的

数组存储结构，查询快、增删慢

元素存储顺序就是数据插入顺序

常用方法

import java.util.ArrayList;

public class F{
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
//       追加
        list.add("1");
//        指定位置插入
        list.add(1,"2");
        list.add("3");
//        toString方法
        System.out.println(list.toString());
//        contains方法，返回true，false
        System.out.println(list.contains("1"));
//        get方法 ，根据index获取元素
        System.out.println(list.get(1));
//        返回与指定值第一个匹配的index
        System.out.println(list.indexOf("1"));
//        根据value移除第一个值相同的元素
        list.remove("1");
//        格局index移除元素
        list.remove(0);
        System.out.println(list.toString());
//        给指定index位置赋值
        list.set(0,"1");
        System.out.println(list.toString());

    }
}

ArrayList中的元素必须是引用类型的对象，不能使用基本数据类型来代替泛型。

为啥呢？不确定具体答案。

可能和数据在内存中的位置相关，基本类型的数据存在栈中，而引用类型的数据存在对中，栈中的数据很容易被回收。

可能和使用方法相关，一般处理数据放到集合中时，可能会存在空值，引用类型允许null，而基础类型不允许。

经常配合Collections.sort()使用，举个例子，实现数组从大到小输出。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class F{
    public static void main(String[] args) {
        String[] arr = {"a","f","b","d","c"};

        ArrayList<String> list = new ArrayList<>();
        for (String a:arr) {
            list.add(a);
        }
//        自定义compare实现倒叙
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -1*(o1.compareTo(o2));
            }
        });
        System.out.println(list.toString());

    }
}

在ArrayList没有元素时，容量是0，向ArrayList中add第一个元素时，给出默认容量10（不是size），扩容时每次扩大为原来的1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);  >>右移可以理解为十进制数据/2，<<左移理解为乘2。

线程不安全解释：

【引用：

https://www.cnblogs.com/panbingqi/p/11041182.html

】

【引用：

https://blog.csdn.net/weixin_43407007/article/details/87901795

】

为什么ArrayList线程不安全？

举个栗子：

一个 ArrayList ，在添加一个元素的时候，它可能会有两步来完成：

1. 在 Items[Size] 的位置存放此元素；
2. 增大 Size 的值。 增大 Size 的值。

在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1； 而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。现在看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。

既然ArrayList是线程不安全的，但如果需要在多线程中使用，3种方式来实现一个线程安全的ArrayList对象。

#1:自己手动同步
public static List<E> list = ... ;
lock.lock();
list.add();
lock.unlock();
#2:使用同步包装器
List<E> syncList = Collections.synchronizedList(new ArrayList<E>());
//迭代时，需要包含在同步块当中

synchronized(syncList){
   while(Iterator<E> iter = syncList.iterator();iter.hasNext();){}
}

Collections.synchronizedList迭代时，需要包含在同步块当中

为什么遍历时要这样处理，为什么add()不需要synchronized,而遍历的时候需要加synchronized?

synchronizedList（）方法对集合的add等操作都加了synchronized修饰，listIterator（）以及iterator（）方法没有加

List list = Collections.synchronizedList(new ArrayList());
      ...
  synchronized (list) {
      Iterator i = list.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }

SynchronizedList和Vector最主要的区别：

【转自：

https://www.cnblogs.com/hongdada/p/10931891.html

】

1. Vector扩容为原来的2倍长度，ArrayList扩容为原来1.5倍
2. SynchronizedList有很好的扩展和兼容功能。他可以将所有的List的子类转成线程安全的类。
3. 使用SynchronizedList的时候，进行遍历时要手动进行同步处理 。
4. SynchronizedList可以指定锁定的对象。

2、Vector

【引用：

https://blog.csdn.net/weixin_43407007/article/details/87901795

】

线程安全、同步

底层是数组

数组存储结构，查询快、增删慢

效率低

元素存储顺序就是数据插入顺序

Vector扩容为原来的2倍长度

Synchronized是Java中解决并发问题的一种最常用最简单的方法 ，他可以确保线程互斥的访问同步代码

Vector类中的capacity()/size()/isEmpty()/indexOf()/lastIndexOf()/removeElement()/addElement() 等方法均是 sychronized 的，所以，对Vector的操作均是线程安全的。对于Vector的操作均是线程安全这句话还需要注意一点是：如果是单个方法进行调用是线程安全的，但是如果是组合的方式进行调用则需要再次进行同步处理

所以在回答Vector与ArrayList的区别时，应该这样回答：



Vector 和 ArrayList 实现了同一接口 List, 但所有的 Vector 的方法都具有 synchronized 关键字修饰。但对于复合操作，Vector 仍然需要进行同步处理。

3、LinkedList

双向链表存储结构

增删快、查找慢

线程不安全，可以使用ArrayList中的方法来解决线程不安全的问题：1、自定义锁。2、同步包装器

【引用：

https://mp.weixin.qq.com/s?src=11&timestamp=1597150757&ver=2516&signature=ZyhA6VWS4NCUFEqRcaMn8Cx5MKkTAhrb-qPLzwQVHUoH*RqRGTLHnykAN7WihZ1Nbetlsmn2CebgXhWFHuGtLYLtTBzz5TOSLh29cRIM1zTvKxr3DvIk2lkLNY9H7ZKE&new=1

】

LinkedList中有size，first以及last全局变量，其作用分别是：

• size — 存放当前链表有多少个节点。

• first — 指向链表的第一个节点的引用

• last —  指向链表的最后一个节点的引用

• 节点是内部类：包含节点的值，pre指针，next指针

• 

Set

1、


HashSet




（




Hash




表）

实现Set接口，底层是哈希表（实际上是HashMap实例），没有索引 也不能使用fori的方法遍历

哈希值：是一个十进制的整数，由系统随机给出（是一个模拟出来的逻辑地址，不是数据存储的物理地址）

public native int hashCode();没有方法体，native表示调用底层操作系统的方法

HashSet特点：

1、不允许存储重复元素

2、没有索引，没有带索引的方法，不能使用fori的方法遍历

3、是一个无序的集合，存储元素和取出元素可能不一致

4、底层是一个哈希表结构，查询速度非常快

哈希表的组成：数组+链表+红黑树

数组用来存链表或者红黑树的

哈希值相同的元素会存在同一个链表中，（JDK1.8新特性）当链表长度超过8时，会使用红黑树的结构存数据。如果仍然使用链表的话，遍历链表的时间复杂度是O(n)，而使用红黑树后，时间复杂度会变成O(lgn),所以哈希表的特点就是访问快。

HashSet存储不重复的原理：

HashSet 通过 hashCode 值来确定元素在内存中的位置。


一个 hashCode 位置上可以存放多个元 素


。

遍历方法：增强for、迭代器

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Main{
    public static void main(String[] args) {
        Set<Integer> myset = new HashSet<>();
        myset.add(1);
        myset.add(2);
        myset.add(3);
        //迭代器遍历
        Iterator<Integer> it = myset.iterator();
        while (it.hasNext()){
            Integer item = it.next();
            System.out.println(item);
        }
        //增强for循环
        for (Integer item:myset) {
            System.out.println(item);
        }
    }
}

2、


LinkHashSet




（




HashSet+LinkedHashMap




）

LinkHashSet实现了Set接口，继承了HashSet类，是有序的，与HashSet相比，他多了一个链表，用来记录元素的存储顺序，保证元素有序。

LinkHashSet是由HashSet和一个链表组成，HashSet本身就是由数组+链表可能还会有红黑树组成的，

对于 LinkedHashSet 而言，它继承与于HashSet、又基于 LinkedHashMap 来实现的。

LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与于HashSet，其所有的方法

操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并

通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操

作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

3、


TreeSet




（二叉树）

引自：

https://blog.csdn.net/Regino/article/details/104549601

• TreeSet 类继承了 Set 接口和 SortedSet 接口，元素不能重复；
• 由于 SortedSet 接口能对元素升序排序，Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，
  
  自
  
  己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
  
  （也叫自然排序），TreeSet 类也会对实现了
  
  Comparable 接口
  
  的类的对象自动排序，或者根据创建 TreeSet 时提供的 Comparator 进行排序（比较器排序）；
• 底层依赖于
  
  TreeMap
  
  ，元素没有索引；
• 通过
  
  红黑树
  
  实现，
  
  不允许放入null值
  
  ；
• 存储大量的需要进行快速检索的排序信息时，TreeSet 是一个很好的选择；

Map

Map特点：

1、map集合是一个双集合列，一个元素包含两个值（键，值）

2、map集合中的元素，可以和value的数据类型可以相同，可以不同

3、map集合中的元素，key不能重复，value可以重复

4、map集合中的元素，key和value一一对应

1、


HashMap




（数组




+




链表+




红黑树）

HashMap

实现了Map接口

2、


ConcurrentHashMap

3、HashTable




（线程安全）

实现了Map接口

HashTable




与HashMap区别

1、

HashMap底层是一个哈希表，是一个多线程的不安全的集合，速度快

HashTable底层是一个哈希表，是一个线程安全的集合，是单线程的集合，速度慢

2、HashMap集合可以存储null值，null键，可以存一个null键，多个null值

HashTable不可以存储NULL值，null键

3、HashTable和Vector一样在jdk1.2版本之后被更先进的集合给取代了

HashTable被HashMap取代，Vector被ArrayList取代

HashTable的子类Properties依然活跃

Properties集合是唯一一个和IO流相结合的集合

线程安全，单线程，慢

4、TreeMap




（可排序 ）

TreeMap

继承了AbstractMap，并且使用一颗树。

5、LinkHashMap




（记录插入顺序）

遍历方式：

键找值 的方法：

1、通过Map集合的getKeys（）方法，返回集合的所有键的集合keys

2、遍历集合keys中的所有key，使用迭代器或者增强for循环遍历

2、通过Map集合的get（key）方法，根据键返回对应的值

使用entrySet（）方法遍历：

1、使用Map集合的entrySet（）方法，将Map集合的Entry对象取出来，存在Set集合中。

2、遍历Set集合，获取每个Entry对象

3、使用Entry对象的getkey（），getValue（）方法，获取键与值

Map集合存储自定义数据：

Map集合保证key是唯一的：

作为key的元素必须重写hashCode和equals方法。

小例子：Map中key是城市，value存person

package testmap;

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

    public Person(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 boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;

        Person person = (Person) o;

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

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

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

package testmap;


import java.util.HashMap;

public class MyTest {
    public static void main(String[] args) {
        show();
    }

    /**
     * HashMap存储自定义的Person对象
     * 地点String类型已经重写了hashCode和equals方法
     * vallue可以重复
     */
    public static void show(){
        HashMap<String ,Person> hashMap = new HashMap<>();
        hashMap.put("北京",new Person("张三",20));
        hashMap.put("广州",new Person("张四",21));
        hashMap.put("天津",new Person("张五",22));
        hashMap.put("天津",new Person("张五",24));

        for(String key :hashMap.keySet()){
            Person person = hashMap.get(key);
            System.out.println(key+" "+person);
        }


    }
}

小例子：统计字符串中每个字符出现的次数

package testmap;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class CountTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if(hashMap.containsKey(str.charAt(i))){
                hashMap.put(str.charAt(i),hashMap.get(str.charAt(i))+1);
            }
            else{
                hashMap.put(str.charAt(i),1);
            }
        }
        for (Character c :hashMap.keySet() ) {
            System.out.println(c+"  "+hashMap.get(c));
        }
    }
}

斗地主小案例；

package testmap;

import java.util.*;

public class Doudizhu {

    public static void main(String[] args) {
        //1、准备牌
        //创建Map集合，存储牌的索引和组装好的牌
        HashMap<Integer,String> poker = new HashMap<>();
        ArrayList<Integer> pokerIndex = new ArrayList<>();
        List<String> pokercolor = new ArrayList<>();
        pokercolor.add("♥");
        pokercolor.add("♠");
        pokercolor.add("♦");
        pokercolor.add("♣");

        String[] num = new String[] {"2","A","K","Q","J","10","9","8","7","6","5","4","3"};
        ArrayList<String> nums = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }
        //手动存储大王小王
        int index = 0;
        poker.put(index,"大王");
        pokerIndex.add(index);
        index++;
        poker.put(index,"小王");
        pokerIndex.add(index);
        index++;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < pokercolor.size(); j++) {
                poker.put(index,pokercolor.get(j)+nums.get(i));
                pokerIndex.add(index);
                index++;
            }
        }

        //洗牌 使用Collections.shuffle方法
        Collections.shuffle(pokerIndex);

        //发牌
        ArrayList<Integer> player1 = new ArrayList<>();
        ArrayList<Integer> player2 = new ArrayList<>();
        ArrayList<Integer> player3 = new ArrayList<>();
        ArrayList<Integer> dipai = new ArrayList<>();

        //遍历牌索引集合
        for (int i = 0; i < pokerIndex.size(); i++) {
            Integer in = pokerIndex.get(i);
            if(i>=51){
                dipai.add(in);
            }else if(i%3==0){
                player1.add(in);
            }else if(i%3==1){
                player2.add(in);
            }else if(i%3==2){
                player3.add(in);
            }
        }


        //给牌排序
        Collections.sort(player1);
        Collections.sort(player2);
        Collections.sort(player3);
        Collections.sort(dipai);

        //看牌
        kanpai("玩家1",poker,player1);
        kanpai("玩家2",poker,player2);
        kanpai("玩家3",poker,player3);
        kanpai("底牌",poker,dipai);
    }

    public static void kanpai(String name,HashMap<Integer,String> poker,ArrayList<Integer> list){
        String res = "";
        for (int i = 0; i < list.size(); i++) {
            res+=poker.get(list.get(i))+" ";
        }
        System.out.println(name+": "+res.trim());
    }
 }