集合的由来 

• 数组长度是固定,如果要改变数组的长度需要创建新的数组将旧数组里面的元素拷贝过去，使用起来不方便。
• java给开发者提供了一些集合类，能够存储任意长度的对象，长度可以随着元素的增加而增加,随着元素的减少而减少，使用起来方便一些。

数组和集合的区别

区别1:

• • 数组既可以存储基本数据类型,又可以存储引用数据类型,基本数据类型存储的是值,引用数据类型存储的是地址值
  • 集合只能存储引用数据类型(对象)，如果存储基本数据类型时，会自动装箱变成相应的包装类

区别2:

• • 数组长度是固定的,不能自动增长
  • 集合的长度的是可变的,可以根据元素的增加而自动增长

 

集合继承体系图

 

java提供了一些集合类，这些集合类分别适用于不同的场景，下面是常用的一些集合基础体系图。

Collection接口

 

里面的Collection是接口，下面的List、Set、Queue也都是接口，并且继承了这个Collection。最下面的ArrayList、LinkedList、Vector、HashSet、TreeSet、PriorityQueue都是他们的实现类。

Collections是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全化等操作。 

当于对Array进行类似操作的类——Arrays。 

如，Collections.max(Collection coll); 取coll中最大的元素。 

       Collections.sort(List list); 对list中元素排序

Map接口

里面的Map是接口，下面的HashMap、HashTable、AbstractMap也都是接口，并且继承了这个Map。最下面的LinkedHashMap、TreeMap是他们的实现类。

 

 

集合类的一些特点

List：里面存放的数据是有顺序的，可以存放重复的数据。

Set：里面存放的数据是没有顺序的，不能存放重复的数据。

Queue：是一个队列，里面的数据是先进先出，可以存放重复的数据。

HashMap:里面存放的数据是没有顺序的，可以存null键和null值，并且不存在相同元素，线程不安全。

HashTable:里面存放的元素不保证有序，并且不存在相同元素。

  

关于HashMap的一些说法：

a)  HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。HashMap的底层结构是一个数组，数组中的每一项是一条链表。

b)  HashMap的实例有俩个参数影响其性能： “初始容量” 和 装填因子。

c)  HashMap实现不同步，线程不安全。  HashTable线程安全

d)  HashMap中的key-value都是存储在Entry中的。

e)  HashMap可以存null键和null值，不保证元素的顺序恒久不变，它的底层使用的是数组和链表，通过hashCode()方法和equals方法保证键的唯一性

f)  解决冲突主要有三种方法：定址法，拉链法，再散列法。

 

HashMap是采用拉链法解决哈希冲突的。

注： 链表法是将相同hash值的对象组成一个链表放在hash值对应的槽位；    

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。 沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。   

拉链法解决冲突的做法是： 将所有关键字为同义词的结点链接在同一个单链表中 。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。拉链法适合未规定元素的大小。    

 

*Hashtable、HashMap、ConcurrentHashMap的区别：

HashMap和HashTable都实现了Map接口，里面存放的元素不保证有序，并且不存在相同元素；

 

区别（线程安全和保存值是否为null方面）：

 

   （1） HashMap和HashTable在功能上基本相同，但HashMap是线程不安全的，HashTable是线程安全的；

   （2）HashMap的key和value都是可以为null的，当get()方法返回null值时，HashMap中可能存在某个key，只不过该key值对应的value为null，也有可能是HashM中不存在该key，所以不能使用get()==null来判断是否存在某个key值，对于HashMap和HashTable，提供了containsKey()方法来判断是否存在某个key。

   （3）HashTable是不允许key和value为null的。HashTable中的方法大部分是同步的，因此HashTable是线程安全的。

拓展：

   （1） 影响HashMap（或HashTable）性能的两个因素：初始容量和load factor；

        HashMap中有如下描述：        When the number of entries in the hash table exceeds the product of the load factor and the current capacity, 

the hash table is <i>rehashed</i> (that is, internal data structures are rebuilt) 

        当我们Hash表中数据记录的大小超过当前容量，Hash表会进行rehash操作，其实就是自动扩容，这种操作一般会比较耗时。所以当我们能够预估Hash表大小时，在初始化的时候就尽量指定初始容量，避免中途Hash表重新扩容操作，如：      

HashMap<String, Integer> map = new HashMap<String, Integer>(20);

        

（类似可以指定容量的还有ArrayList、Vector）

   （2）使用选择上，当我们需要保证线程安全，HashTable优先选择。当我们程序本身就是线程安全的，HashMap是优先选择。

        其实HashTable也只是保证在数据结构层面上的同步，对于整个程序还是需要进行多线程并发控制；在JDK后期版本中，对于HashMap，可以通过Collections获得同步的HashMap；如下：

        Map m = Collections.synchronizedMap(new HashMap(...));

        这种方式获得了具有同步能力的HashMap。        

    （3）在JDK1.5以后，出现了ConcurrentHashMap，它可以很好地解决在并发程序中使用HashMap的问题，ConcurrentHashMap和HashTable功能很像，不允许为null的key或value，但它不是通过给方法加synchronized方法进行并发控制的。

     在ConcurrentHashMap中使用分段锁技术Segment，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。效率也比HashTable好的多。

 

*TreeMap、HashMap、LinkedHashMap的区别：

 

（1）LinkedHashMap保存了数据的插入顺序，底层是通过一个双链表的数据结构来维持这个插入顺序的。key和value都可以为null；

（2）TreeMap实现了SortMap接口，它保存的记录是根据键值key排序，默认是按key升序排列。也可以指定排序的Comparator。

 

HashMap、LinkedHashMap和TreeMap都是线程不安全的，HashTable是线程安全的。提供两种遍历Map的方法如下：

（1）推荐方式：

Map
      
        map = new HashMap
       
        (20);        for(Map.Entry
        
          entry : map.entrySet()){    //直接遍历出Entry            System.out.println("key-->"+entry.getKey()+",value-->"+m.get(entry.getValue()));        }
        
       
      

 

这种方式相当于首先通过Set<Map.Entry<String,Integer>> set =  map.entrySet();方式拿到Set集合，而Set集合是可以通过foreach的方式遍历的。

（2）普通方式：

Map
      
        map = new HashMap
       
        (20);        Iterator
        
          keySet = map.keySet().iterator();    //遍历Hash表中的key值集合，通过key获取value        while(keySet .hasNext()){            Object key = keySet .next();            System.out.println("key-->"+key+",value-->"+m.get(key));        }
        
       
      

 

 

HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值的,会去判断当前Map中是否含有该Key对象，内部是先通过key的hashCode,确定有相同的hashCode之后，再通过equals方法判断是否相同。