1JAVA集合

1.   Collection

技术分享

 

Collection接口是List、Set和Queue接口的父接口,该接口定义的方法即存在于Set集合也存在于List集合和Queue集合;

1.1Set接口

技术分享

HashSet:

         HashSet是基于HashMap实现的,

    /**

     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has

     * default initial capacity (16) and load factor (0.75).

     */

    public HashSet() {

        map = new HashMap<>();

    }

所有放入HashSet的元素都是由HashMap的key保存的,而HashMap的value则存储了一个PRESENT静态Object对象

    // Dummy value to associate with an Object in the backing Map

private static final Object PRESENT = new Object();

 

    /**

     * Adds the specified element to this set if it is not already present.

     * More formally, adds the specified element <tt>e</tt> to this set if

     * this set contains no element <tt>e2</tt> such that

     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.

     * If this set already contains the element, the call leaves the set

     * unchanged and returns <tt>false</tt>.

     *

     * @param e element to be added to this set

     * @return <tt>true</tt> if this set did not already contain the specified

     * element

     */

    public boolean add(E e) {

        return map.put(e, PRESENT)==null;

    }

HashSet允许添加null元素;HashSet判断两个元素是否相等的彼岸准除了要求equals方法比较返回true的同时还要求两个对象的hashCode()返回值相同;

    HashSet<String> hs = new HashSet<String>();

    String s = null;

  

    public void Test(){

    hs.add(s);

    hs.add(null);

    hs.add(null);

    }

TreeSet:

EnumSet:

1.2List接口

技术分享

1.3Queue接口

LinkedList实现了Queue接口,同时也实现了List接口,队列先进先出机制

2.   Map接口

技术分享

技术分享

 

 

HashMap:底层由数组和链表组成,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。它的内部其实是用一个Entity数组来实现的,属性有key、value、next。

3.   操作集合的工具类

4.   集合并发操作时使用锁机制

4.1Demo1

运行如下程序,在一个线程中读取集合数据,在另外一个线程中修改集合数据

       

public static ArrayList<String> datas = new ArrayList<String>();

//初始化数据

    public static void initData(){

        for(int i=0;i<20;i++){

            datas.add(""+i);

        }

    }

   

//线程1,读取集合的数据 

    public static  Thread thread1=new Thread(){

        public void run() {

            for(String data:datas){

                System.out.println(data);

            }

        };

    };

//线程2,删除集合的数据

    private static Thread thread2=new Thread(){

        public void run() {

            int size=datas.size();

            for(int i=0;i<size;i++){

                datas.remove(0);

                System.out.println("remove:"+datas.get(i));

            }

        };

    };

//启动程序

        public static void main(String[] args) {

        initData();

        thread1.start();

        thread2.start();

    }

 

输出结果为:

remove:1

remove:3

remove:5

remove:7

remove:9

remove:11

remove:13

remove:15

remove:17

remove:19

11

12

13

14

15

16

17

18

19

Exception in thread "Thread-1" java.lang.IndexOutOfBoundsException: Index: 10, Size: 9

    at java.util.ArrayList.rangeCheck(ArrayList.java:604)

    at java.util.ArrayList.get(ArrayList.java:382)

    at CollectionReadWriteLock.CollectionReadWriteLockTest$2.run(CollectionReadWriteLockTest.java:29)

我们经常会遇到在一个线程遍历集合在另一个线程中修改该集合的情况,此时我们就可以使用java.util.concurrent.locks包里面的ReentrantReadWriteLock;

    public static final ReadWriteLock lock = new ReentrantReadWriteLock(false);

  

    public static ArrayList<String>datas=new ArrayList<String>();

    public static void initData(){

        for(int i=0;i<20;i++){

            datas.add(""+i);

        }

    }

   

     public static Thread thread1 = new Thread(){

    public void run(){

        lock.readLock().lock();

        for(String str : datas){

            System.out.println("t1:"+str);

        }

        lock.readLock().unlock();

    };

     };

 

   

     public static Thread thread2 = new Thread(){

        public void run(){

            lock.writeLock().lock();

            int s = datas.size();

            for(int i=0;i<s;i++){

                datas.remove(0);

                System.out.println("remove");

            }

          

            lock.writeLock().unlock();

        };

      };

   

     public static Thread thread3 = new Thread(){

        public void run(){

            lock.readLock().lock();

            for(String str : datas){

                System.out.println("t3:"+str);

            }

            lock.readLock().unlock();

        };

      };

   

    public static void main(String[] args) {

        initData();

        thread1.start();

        thread2.start();

        thread3.start();

    }

大家可能疑惑为啥没有t3的打印呢?因为读锁在释放之后,立马就被写锁占用了,写锁的线程把集合清空了,所以当轮到线程3的时候就没有数据了,多试几次,会发现还有一种执行结果就是全部都是remove。没有任何打印,这是因为先执行了线程2的缘故。如果我们按照这样的顺序执行,又会不同

也可以使用Collections提供的同步方法

Collections.synchronizedSet(new HashSet<String>());创建一个线程同步的集合

5.   面试汇总

1、 什么是Java集合API

Java集合框架API是用来表示和操作集合的统一框架,它包含接口、实现类、以及帮助程序员完成一些编程的算法。简言之,API在上层完成以下几件事:

 

● 编程更加省力,提高城程序速度和代码质量

● 非关联的API提高互操作性

● 节省学习使用新API成本

● 节省设计新API的时间

● 鼓励、促进软件重用

 

具体来说,有6个集合接口,最基本的是Collection接口,由三个接口Set、List、SortedSet继承,另外两个接口是Map、SortedMap,这两个接口不继承Collection,表示映射而不是真正的集合。

2、 什么是Iterator

一些集合类提供了内容遍历的功能,通过java.util.Iterator接口。这些接口允许遍历对象的集合。依次操作每个元素对象。当使用Iterators时,在获得Iterator的时候包含一个集合快照。通常在遍历一个Iterator的时候不建议修改集合本省。

 

3、 Iterator与ListIterator有什么区别?

Iterator:只能正向遍历集合,适用于获取移除元素。ListIerator:继承Iterator,可以双向列表的遍历,同样支持元素的修改。

 

4、 什么是HashMap和Map?

Map是接口,Java 集合框架中一部分,用于存储键值对,HashMap是用哈希算法实现Map的类。

 

5、 HashMap与HashTable有什么区别?对比Hashtable VS HashMap

两者都是用key-value方式获取数据。Hashtable是原始集合类之一(也称作遗留类)。HashMap作为新集合框架的一部分在Java2的1.2版本中加入。它们之间有一下区别:

● HashMap和Hashtable大致是等同的,除了非同步和空值(HashMap允许null值作为key和value,而Hashtable不可以)。

● HashMap没法保证映射的顺序一直不变,但是作为HashMap的子类LinkedHashMap,如果想要预知的顺序迭代(默认按照插入顺序),你可以很轻易的置换为HashMap,如果使用Hashtable就没那么容易了。

● HashMap不是同步的,而Hashtable是同步的。

● 迭代HashMap采用快速失败机制,而Hashtable不是,所以这是设计的考虑点。

 

6、 在Hashtable上下文中同步是什么意思?

同步意味着在一个时间点只能有一个线程可以修改哈希表,任何线程在执行hashtable的更新操作前需要获取对象锁,其他线程等待锁的释放。

 

7、 什么叫做快速失败特性

从高级别层次来说快速失败是一个系统或软件对于其故障做出的响应。一个快速失败系统设计用来即时报告可能会导致失败的任何故障情况,它通常用来停止正常的操作而不是尝试继续做可能有缺陷的工作。当有问题发生时,快速失败系统即时可见地发错错误告警。在Java中,快速失败与iterators有关。如果一个iterator在集合对象上创建了,其它线程欲“结构化”的修改该集合对象,并发修改异常 (ConcurrentModificationException) 抛出。

 

8、 怎样使Hashmap同步?

HashMap可以通过Map m = Collections.synchronizedMap(hashMap)来达到同步的效果。

 

9、 什么时候使用Hashtable,什么时候使用HashMap

基本的不同点是Hashtable同步HashMap不是的,所以无论什么时候有多个线程访问相同实例的可能时,就应该使用Hashtable,反之使用HashMap。非线程安全的数据结构能带来更好的性能。

如果在将来有一种可能—你需要按顺序获得键值对的方案时,HashMap是一个很好的选择,因为有HashMap的一个子类LinkedHashMap。所以如果你想可预测的按顺序迭代(默认按插入的顺序),你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。同时如果有多个线程访问HashMap,Collections.synchronizedMap()可以代替,总的来说HashMap更灵活。

 

10、为什么Vector类认为是废弃的或者是非官方地不推荐使用?或者说为什么我们应该一直使用ArrayList而不是Vector

你应该使用ArrayList而不是Vector是因为默认情况下你是非同步访问的,Vector同步了每个方法,你几乎从不要那样做,通常有想要同步的是整个操作序列。同步单个的操作也不安全(如果你迭代一个Vector,你还是要加锁,以避免其它线程在同一时刻改变集合).而且效率更慢。当然同样有锁的开销即使你不需要,这是个很糟糕的方法在默认情况下同步访问。你可以一直使用Collections.sychronizedList来装饰一个集合。

事实上Vector结合了“可变数组”的集合和同步每个操作的实现。这是另外一个设计上的缺陷。Vector还有些遗留的方法在枚举和元素获取的方法,这些方法不同于List接口,如果这些方法在代码中程序员更趋向于想用它。尽管枚举速度更快,但是他们不能检查如果集合在迭代的时候修改了,这样将导致问题。尽管以上诸多原因,oracle也从没宣称过要废弃Vector.

1、HashMap和HashTable

      相同点:二者都实现了Map接口,因此具有一系列Map接口提供的方法。

      不同点:

            1、HashMap继承了AbstractMap,而HashTable继承了Dictionary。

            2、HashMap非线程安全,HashTable线程安全,到处都是synchronized关键字。

            3、因为HashMap没有同步,所以处理起来效率较高。

            4、HashMap键、值都允许为null,HashTable键、值都不允许有null。

            5、HashTable使用Enumeration,HashMap使用Iterator。

      这些就是一些比较突出的不同点,实际上他们在实现的过程中会有很多的不同,如初始化的大小、计算hash值的方式等等。毕竟这两个类包含了很多方法,有很重要的功能,所以其他不同点,请感兴趣的读者自己去看源码,去研究。笔者推荐使用HashMap,因为她提供了比HashTable更多的方法,以及较高的效率,如果大家需要在多线程环境中使用,那么用Collections类来做一下同步即可。

2、Set接口和List接口

  相同点:都实现了Collection接口

    不同点:

          1、Set接口不保证维护元素的顺序,而且元素不能重复。List接口维护元素的顺序,而且元素可以重复。

       2、关于Set元素如何保证元素不重复,我将在下面的博文中给出。

3、ArrayList和LinkList

     相同点:都实现了Collection接口

      不同点:ArrayList基于数组,具有较高的查询速度,而LinkedList基于双向循环列表,具有较快的添加或者删除的速度,二者的区别,其实就是数组和列表的区别。上文有详细的分析。

4、SortedSet和SortedMap

      二者都提供了排序的功能。 来看一个小例子:

[java] view plaincopy

public static void main(String[] args) {

        

        SortedMap<String, Integer> map = new TreeMap<String, Integer>();

        map.put("zgg", 1);

        map.put("erqing", 3);

        map.put("niu", 0);

        map.put("abc", 2);

        map.put("aaa", 5);

        

        Set<String> keySet = map.keySet();

        for (String string : keySet) {

            System.out.print(map.get(string)+" ");

        }

    }

输出:5 2 3 0 1

从结果看得出:SortedMap具有自动排序功能

5、TreeMap和HashMap

     HashMap具有较高的速度(查询),TreeMap则提供了按照键进行排序的功能。

6、HashSet和LinkedHashSet

     HashSet,为快速查找而设计的Set。存入HashSet的对象必须实现hashCode()和equals()。

     LinkedHashSet,具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序),于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

7、TreeSet和HashSet

     TreeSet: 提供排序功能的Set,底层为树结构 。相比较HashSet其查询速度低,如果只是进行元素的查询,我们一般使用HashSet。

8、ArrayList和Vector

      同步性:Vector是线程安全的,也就是说是同步的,而ArrayList是线程序不安全的,不是同步的。

      数据增长:当需要增长时,Vector默认增长为原来一培,而ArrayList却是原来的一半

9、Collection和Collections

      Collection是一系列单值集合类的父接口,提供了基本的一些方法,而Collections则是一系列算法的集合。里面的属性和方法基本都是static的,也就是说我们不需要实例化,直接可以使用类名来调用。下面是Collections类的一些功能列表:

6.   集合妙用

import java.util.HashMap;

import java.util.Map;

/**

* 求出给定数组中重复的元素个数并打印

* @author Pursuit.

* @version 2013-11-16  下午2:54:16

*/

public class TetsMap {

         public static void main(String[] args) {

                  String[] str = {"aaa","bbb","aaa","ccc","ddd","aaa","bbb",

                                   "eee","fff","eee"};

                  method(str);

                  Integer[] il = {1,1,1,2,3,4,4,4,5,6,7,8,9,5,67,8,32,6,8,6};

                  method(il);

                  }

         //定义一个泛型方法

         public static <T> void method(T[] s){

                  final  Integer one = new Integer(1);

                  Map<T,Integer> m = new HashMap<T,Integer>();

                  for(int i=0;i<s.length;i++){

                          Integer temp = m.get(s[i]);

                          //如果当前key已经存在则将value+1后更新value值

                          m.put(s[i], temp==null? one : new Integer(temp+1));

                  }

                  System.out.println(m.size()+"个元素被留下");

                  System.out.println(m);

         }

}

参考链接:

http://blog.csdn.net/zhangerqing/article/details/8122075

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。