Java数组和集合

Java数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型），而Java集合可以存储和操作数目不固定的一组数据。 所有的Java集合都位于 java.util包中， Java集合只能存放引用类型的的数据，不能存放基本数据类型。

下图是一个简略的继承关系图，中间部分层级的继承省略了。

20180725145224835.png

Collection接口

Collection是最基本的集合接口，声明了适用于JAVA集合（只包括Set和List）的通用方法。 Set 和List 都继承了Conllection。

（1）Collection接口的部分常用方法：

public interface Collection<E> extends Iterable<E>{

  boolean add(Object o) ：向集合中加入一个对象的引用   
  
  void clear()：删除集合中所有的对象，即不再持有这些对象的引用   
  
  boolean isEmpty() ：判断集合是否为空   
  
  boolean contains(Object o)：判断集合中是否持有特定对象的引用   
  
  Iterartor iterator() ：返回一个Iterator对象，可以用来遍历集合中的元素   
  
  boolean remove(Object o) ：从集合中删除一个对象的引用   
  
  int size() ：返回集合中元素的数目   
  
  Object[] toArray() ：返回一个数组，该数组中包括集合中的所有元素 </span>  

}

Iterator() 和toArray() 方法都用于集合的所有的元素，前者返回一个Iterator对象，后者返回一个包含集合中所有元素的数组。
关于iterator简单介绍可以看这里。

Set(集合)

1.不允许重复对象
2.Set无序容器，你无法保证每个元素的存储顺序，但是有些子类分别实现了各自规则的排序。
3.只允许一个 null 元素
4.Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。基于 HashMap 实现的 HashSet；LinkedHashset : 保证元素添加的自然顺序；TreeSet 间接实现了 SortedSet 接口，TreeSet通过 Comparator维护了一个排序顺序，保证元素的自然顺序。

注意：List是有序且可重复的，Set是无序且不重复的。这是一个误区，这里所说的顺序有两个概念，一是按照添加的顺序排列，二是按，照自然顺序a-z排列。Set并不是无序的传统所说的Set无序指的是HashSet，它不能保证元素的添加顺序，更不能保证自然顺序，而Set的其他实现类是可以实现这两种顺序的，也就是上面提到的LinkedHashset 、TreeSet 。栗子请看这里

代码示例

Set set=new HashSet();  
String s1=new String("hello");   
String s2=s1;   
String s3=new String("world");   
set.add(s1);   
set.add(s2);   
set.add(s3);  
System.out.println(set.size());

输出结果：

2

可以看到Set是不允许重复对象的。

• （1）实现类HashSet

1.HashSet不是线程安全的；
2.HashSet允许有空值；
3.HashSet中不允许有相同值得存在；

底层是由 Hash Map 实现，不允许集合中有重复的值，使用该方式时需要重写 equals()和 hash Code()方法；

• （2）实现类TreeSet

1.TreeSet是线程不安全的
2.该类实现了SortedSet接口，通过Comparator维护了一个排序顺序（二叉树）。

List

1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

代码示例：

public static void main(String[] args) {
        List<String> list = new ArrayList();
        list.add("aaa");
        list.add("bbb");
        list.add(null);
        list.add("aaa");
        list.add("ccc");
        list.add(null);
        System.out.println("***************以下是foreach的输出*******************");
        for(String s: list){
            System.out.println(s);
        }
        System.out.println("***************以下是普通for循环的输出*******************");
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
        System.out.println("***************以下是迭代器的输出*******************");
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
}

输出结果：

***************以下是foreach的输出*******************
aaa
bbb
null
aaa
ccc
null
***************以下是普通for循环的输出*******************
aaa
bbb
null
aaa
ccc
null
***************以下是迭代器的输出*******************
aaa
bbb
null
aaa
ccc
null

• （1）实现类ArrayList

1.ArrayList底层是用数组实现的，通过索引下标可以快速的查到数据，所以它对数据的查询操作效率高的多，增加和删除等修改操作效率较低；
2.数据可重复性
3.ArrayList不是线程安全的；

• （2）实现类LinkedList

1.LinkedList底层使用双向链表实现的，因此它对于数据的增加删除操作效率较ArrayList要高；
2.对数据的查询需要操作指针，所以查询操作效率较低；
3.数据可重复；
4.LinkedList不是线程安全的；

• （3）实现类Vector

1.通过数组来实现的，但是效率一般比ArrayList低，如果不考虑线程安全问题，一般使用ArrayList
2.数据可重复;
3.vector是线程安全的；

Map(映射)

Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口 从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用方法：

public interface Map<K, V> {
  
    int size();//数量

    boolean isEmpty();//是否为空

    boolean containsKey(Object key);//是否包含目标key

    boolean containsValue(Object value);//是否包含目标value

    V get(Object key);//根据key获取value

    V put(K key, V value);//放入一个键值对

    V remove(Object key);//根据一个key移出一个对象

    void putAll(Map<? extends K, ? extends V> m);//将一个map的拷贝添加到里面去

    void clear();//清空map

    Set<K> keySet();//获取key的集合，因为key不能重复，所以用Set保存

    Collection<V> values();//获取value的集合，因为value可以重复，所以用collection保存

    Set<Map.Entry<K, V>> entrySet();//获取map内部类对象Entry，其中有方法getKey和getValue来获取相应值

}

1.Map不是collection的子接口或者实现类。Map是一个接口；
2.Map 的 每个 Entry 都持有两个对象，也就是一个键一个值，Map 可能会持有相同的值对象但键对象必须是唯一的；
3.TreeMap 也通过 Comparator 维护了一个排序顺序。
4.Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
5.Map 接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 、TreeMap、ConcurrentHashMap。（HashMap最常用）

看代码示例：

public static void main(String[] args) {
        HashMap<String, String> map = new HashMap();
        map.put("aaa", "Hello");
        map.put("bbb", "World");
        map.put("aaa", "Game");
        System.out.println(map.size());
        System.out.println("**************通过循环map的key来获取key和value****************");
        for (String key : map.keySet()) {
            System.out.println("key= "+ key + " and value= " + map.get(key));
        }
        System.out.println("**************通过Map.entrySet使用iterator遍历key和value****************");
        Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, String> entry = it.next();
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
         }
        System.out.println("**************通过Map.entrySet遍历key和value。容量大时(相对来说 比2好一点 效率高)****************");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }
        System.out.println("**************通过Map.values()遍历所有的value，但不能遍历key****************");
        for (String v : map.values()) {
            System.out.println("value= " + v);
        }
}

输出结果：

2
**************通过循环map的key来获取key和value****************
key= aaa and value= Game
key= bbb and value= World
**************通过Map.entrySet使用iterator遍历key和value****************
key= aaa and value= Game
key= bbb and value= World
**************通过Map.entrySet遍历key和value。容量大时(相对来说 比2好一点 效率高)****************
key= aaa and value= Game
key= bbb and value= World
**************通过Map.values()遍历所有的value，但不能遍历key****************
value= Game
value= World

• （1）实现类HashMap

1.HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。
2.底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。
3.HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。
4.HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能
5.采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常

• （2）实现类HashTable

1.Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键
2.底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体
3.Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4.synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

• （3）实现类TreeMap

1.底层是二叉树的结构
2.线程不同步

问题

通过上述一些介绍，我们基本了解了List、Set、Map的一些知识，那么我们根据这些知识可以来解答一下下面这些问题。

（1）什么场景下使用list，set，map呢？

如果你经常会使用索引来对容器中的元素进行访问，那么 List 是你的正确的选择。如果你已经知道索引了的话，那么 List 的实现类比如 ArrayList 可以提供更快速的访问,如果经常添加删除元素的，那么肯定要选择LinkedList。
如果你想容器中的元素能够按照它们插入的次序进行有序存储，那么还是 List，因为 List 是一个有序容器，它按照插入顺序进行存储。
如果你想保证插入元素的唯一性，也就是你不想有重复值的出现，那么可以选择一个 Set 的实现类，比如 HashSet、LinkedHashSet 或者 TreeSet。所有 Set 的实现类都遵循了统一约束比如唯一性，而且还提供了额外的特性比如 TreeSet 还是一个 SortedSet，所有存储于 TreeSet 中的元素可以使用 Java 里的 Comparator 或者 Comparable 进行排序。LinkedHashSet 也按照元素的插入顺序对它们进行存储。
如果你以键和值的形式进行数据存储那么 Map 是你正确的选择。你可以根据你的后续需要从 Hashtable、HashMap、TreeMap 中进行选择。

相关文章：
https://www.cnblogs.com/EasonJim/p/7967138.html
https://blog.csdn.net/yangxingpa/article/details/81023138
HashMap、Hashtable、ConcurrentHashMap的原理与区别
HashMap、Hashtable和ConcurrentHashMap底层实现原理和线程安全问题