Java中的集合框架定义了一套规范,用来表示、操作集合,使具体操作与实现细节解耦。可以将集合看成一个微型非持久性数据库,操作不外乎“增删改查”四种操作。为了保证核心接口小,最顶端设计的接口(CollectionMap接口)并不会区分该集合是否可变(mutability),是否可更改(modifiability),是否可改变大小(resizability)这些细微的差别。相反,一些操作是可选的,在实现时抛出UnsupportedOperationException即可表示集合不支持该操作。集合的实现者必须在文档中声明那些操作是不支持的。


首先查看jdk1.7中Collection类的源码,具体代码如下:

... 
public interface Collection<E> extends Iterable<E> {
    // Query Operations
...

通过查看可以发现Collection是一个接口类,其继承了java迭代接口IterableCollection接口有两个主要的子接口ListSet,注意的是Map不是Collection的子接口。Collection中可以存储的元素间无序,可以重复组各自独立的元素, 即其内的每个位置仅持有一个元素,同时允许有多个null元素对象。


Collection接口中的方法如下:

 


1. List接口

 List接口对Collection进行了简单的扩充,查看List接口的部分源码如下:

...
public interface List<E> extends Collection<E> {
    // Query Operations

    /**
     * Returns the number of elements in this list.  If this list contains
     * more than <tt>Integer.MAX_VALUE</tt> elements, returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * @return the number of elements in this list
     */
    int size();

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    boolean isEmpty();
  ...


List接口中的元素的特点:

List中存储的元素实现类排序,而且可以重复的存储相关元素。同时List接口又有两个常用的实现类ArrayListLinkedList

1)ArrayList

ArrayList数组线性表的特点为:类似数组的形式进行存储,因此它的随机访问速度极快。

ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

ArrayList可以理解成基于数组的一个线性表,只不过数组的长度可以动态改变而已。


注意:

a. ArrayList初始化的时候没有指定初始化长度的话,默认的长度为10.    

/**
   * Constructs an empty list with an initial capacity of ten.
   */
  public ArrayList() {
  this(10);
  }


b. ArrayList在增加新元素的时候如果超过了原始的容量的话,ArrayList扩容ensureCapacity的方案为“原始容量*3/2+1"

/**
* Increases the capacity of this ArrayList instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param   minCapacity   the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
      Object oldData[] = elementData;
      int newCapacity = (oldCapacity * 3)/2 + 1;
      if (newCapacity < minCapacity)
      newCapacity = minCapacity;
      // minCapacity is usually close to size, so this is a win:
      elementData = Arrays.copyOf(elementData, newCapacity);
    }
}


c. ArrayList是线程不安全的,在多线程的情况下不要使用。

如果一定在多线程使用List的,您可以使用Vector,因为Vector和ArrayList基本一致,区别在于Vector中的绝大部分方法都使用了同步关键字修饰,这样在多线程的情况下不会出现并发错误,还有就是它们的扩容方案不同,ArrayList是通过原始容量*3/2+1,而Vector是允许设置默认的增长长度,Vector的默认扩容方式为原来的2倍。


d. ArrayList实现遍历的几种方法如下:

package com.yoodb.blog;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test{
public static void main(String[] args) {
     List<String> list=new ArrayList<String>();
     list.add("Hello");
     list.add("World");
     list.add("HAHAHAHA");
     //第一种遍历方法使用foreach遍历List
     for (String str : list) {            //也可以改写for(int i=0;i<list.size();i++)这种形式
        System.out.println(str);
    }
 
     //第二种遍历,把链表变为数组相关的内容进行遍历
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(int i=0;i<strArray.length;i++) //这里也可以改写为foreach(String str:strArray)这种形式
    {
        System.out.println(strArray[i]);
    }
     
    //第三种遍历 使用迭代器进行相关遍历
     
     Iterator<String> ite=list.iterator();
     while(ite.hasNext())
     {
         System.out.println(ite.next());
     }
 }
}

 

2)LinkedList

LinkedList的链式线性表的特点是适合于在链表中间需要频繁进行插入和删除操作;缺点是随机访问速度较慢。查找一个元素需要从头开始一个一个的找。可以这样理解LinkedList就是一种双向循环链表的链式线性表,只不过存储的结构使用的是链式表而已。对于LinkedList的详细使用信息以及创建的过程可以查看jdk中LinkedList的源码。


a. LinkedList和ArrayList的区别和联系

ArrayList数组线性表的优点是类似数组的形式进行存储,因此它的随机访问速度极快;缺点是不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

LinkedList的链式线性表的特点是适合于在链表中间需要频繁进行插入和删除操作;缺点是随机访问速度较慢。查找一个元素需要从头开始一个一个的找。


b. LinkedList的内部实现

LinkedList的内部是基于双向循环链表的结构来实现的。在LinkedList中有一个类似于c语言中结构体的Entry内部类。在Entry的内部类中包含了前一个元素的地址引用和后一个元素的地址引用类似于c语言中指针。


c. LinkedList不是线程安全的

LinkedList和ArrayList一样也不是线程安全的,如果在对线程下面访问可以自己重写LinkedList,然后在需要同步的方法上面加上同步关键字synchronized


d. LinkedList的遍历方法

package com.yoodb.blog;
 
import java.util.LinkedList;
import java.util.List;
 

public class Test{
public static void main(String[] args) {
     
    List<String> list=new LinkedList<String>();
    list.add("Hello");
    list.add("World");
    list.add("龙不吟,虎不啸");
    //LinkedList遍历的第一种方式使用数组的方式
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(String str:strArray)
    {
        System.out.println(str);
    }
    //LinkedList遍历的第二种方式
    for(String str:list)
    {
        System.out.println(str);   
    }
  }
}


e. LinkedList可以被当做堆栈来使用

由于LinkedList实现了接口Dueue,所以LinkedList可以被当做堆栈来使用,省略。


2. Set接口

Set接口是Collection接口的一个常用子接口查看Set接口的源码如下:

public interface Set<E> extends Collection<E> {
    // Query Operations

    /**
     * Returns the number of elements in this set (its cardinality).  If this
     * set contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * @return the number of elements in this set (its cardinality)
     */
    int size();

 Set接口区别于List接口的特点在于:

 Set中的元素实现了不重复,有点象集合的概念,无序,不允许有重复的元素,最多允许有一个null元素对象。需要注意的是虽然Set中元素没有顺序,但是元素在set中的位置是有由该元素的HashCode决定的,其具体位置其实是固定的。


举一个实例:对象A和对象B,本来是不同的两个对象,正常情况下它们是能够放入到Set里面的,但是如果对象A和B的都重写了hashcode和equals方法,并且重写后的hashcode和equals方法是相同的话。那么A和B是不能同时放入到Set集合中去的,也就是Set集合中的去重和hashcode与equals方法直接相关。

package com.yoodb.blog;
import java.util.HashSet;
import java.util.Set;
public class Test{
public static void main(String[] args) {
     Set<String> set=new HashSet<String>();
     set.add("Hello");
     set.add("world");
     set.add("Hello");
     System.out.println("集合的尺寸为:"+set.size());
     System.out.println("集合中的元素为:"+set.toString());
  }
}

由于String类中重写了hashcode和equals方法,因此第二个Hello值是无法插入的。


Set接口的常见实现类有HashSet,LinedHashSet和TreeSet三个类。下面我们将分别讲解这三个类,参考资料:http://www.cnblogs.com/xiohao/p/4309462.html

1)HashSet

HashSet是Set接口的最常见的实现类了。其底层是基于Hash算法进行存储相关元素的。

HashSet的部分源码如下:

/**
    * 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<E,Object>();
   }

HashSet使用和理解中容易出现的误区:

a. HashSet中允许出入null值,但是在HashSet中仅能够存入一个null值。

b. HashSet中存储的元素的是无序的,但是由于HashSet底层是基于Hash算法实现的,使用了hashcode,所以HashSet中相应的元素的位置是固定的。

c. 遍历HashSet的几种方法

package com.yoodb.blog;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
 
public class Test{
public static void main(String[] args) {
     Set<String> set=new HashSet<String>();
     set.add("Hello");
     set.add("world");
     set.add("Hello");
     //遍历集合的第一种方法,使用数组的方法
     String[] strArray=new String[set.size()];
     strArray=set.toArray(strArray);
     for(String str:strArray)//此处也可以使用for(int i=0;i<strArray.length;i++)
     {
         System.out.println(str);
     }
     //遍历集合的第二中方法,使用set集合直接遍历
     for(String str:set)
     {
         System.out.println(str);
     }
      
     //遍历集合的第三种方法,使用iterator迭代器的方法
     Iterator<String> iterator=set.iterator();
     while(iterator.hasNext())
     {
         System.out.println(iterator.next());
     }
}
}


2)LinkHashSet

LinkHashSet不仅是Set接口的子接口而且还是HashSet接口的子接口查看LinkedHashSet的部分源码如下:

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and load factor.

对于LinkedHashSet而言,它和HashSet主要区别在于LinkedHashSet中存储的元素是在哈希算法的基础上增加了链式表的结构。


3)TreeSet

TreeSet是一种排序二叉树。存入Set集合中的值,会按照值的大小进行相关的排序操作。底层算法是基于红黑树来实现的。而TreeSet和HashSet的主要区别在于TreeSet中的元素会按照相关的值进行排序。


TreeSet和HashSet的区别和联系

a. HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key

b. Map的key和Set都有一个共同的特性就是集合的唯一性,TreeMap更是多了一个排序的功能

c. hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可。hashCode是用来计算hash值的,hash值是用来确定hash表索引的。hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry。put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value。


由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的

a. Comparator可以在创建TreeMap时指定

b. 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口

c. TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了


TreeSet实例:

package com.yoodb.blog;
import java.util.Iterator;
import java.util.TreeSet;
 
/**
 * TreeSet测试类
 * @author 小浩
 * @创建日期 2015-4-3
 */
public class Test{
    public static void main(String[] args) {
        //String实体类中实现Comparable接口,所以在初始化TreeSet的时候,
        //无需传入比较器
        TreeSet<String> treeSet=new TreeSet<String>();
        treeSet.add("d");
        treeSet.add("c");
        treeSet.add("b");
        treeSet.add("a");
        Iterator<String> iterator=treeSet.iterator();
        while(iterator.hasNext())
        {
            System.out.println(iterator.next());
        }
         
     }
}


3. Map接口

Map接口实现的是一组Key-Value的键值对的组合。 Map中的每个成员方法由一个关键字(key)和一个值(value)构成。Map接口不直接继承于Collection接口,因为它包装的是一组成对的“键-值”对象的集合,而且在Map接口的集合中也不能有重复的key出现,因为每个键只能与一个成员元素相对应。


Map有两种比较常用的实现:HashMap和TreeMap等。HashMap也用到了哈希码的算法,以便快速查找一个键,TreeMap则是对键按序存放,因此它便有一些扩展的方法,比如firstKey(),lastKey()等,你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单,用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。


注意:Set接口的底层是基于Map接口实现的。Set中存储的值,其实就是Map中的key,它们都是不允许重复的。


Map接口的部分源码如下:

 * @see Hashtable
 * @see SortedMap
 * @see Collection
 * @see Set
 * @since 1.2
 */
public interface Map<K,V> {
    // Query Operations

    /**
     * Returns the number of key-value mappings in this map.  If the
     * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
     * <tt>Integer.MAX_VALUE</tt>.
     *
     * @return the number of key-value mappings in this map
     */
    int size();

具体的讲解Hash算法的实现过程,参考资料:http://www.cnblogs.com/xiohao/p/4389672.html


Map接口的常见实现类HashMap、TreeMap、LinkedHashMap、Properties(继承HashTable)以及老版本的HashTable等。

1)HashMap

HashMap实现了Map、CloneMap、Serializable三个接口,并且继承自AbstractMap类。HashMap基于hash数组实现,若key的hash值相同则使用链表方式进行保存。

新建一个HashMap时,默认的话会初始化一个大小为16,负载因子为0.75的空的HashMap:

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
	this.loadFactor = DEFAULT_LOAD_FACTOR;
	threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
	table = new Entry[DEFAULT_INITIAL_CAPACITY];
	init();
}

HashMap中还存在一个内部类Entry,用于链表的存储,部分源代码如下:

     * modified after the entry was returned by the iterator, except through
     * the <tt>setValue</tt> operation on the map entry.
     *
     * @see Map#entrySet()
     * @since 1.2
     */
    interface Entry<K,V> {
        /**
         * Returns the key corresponding to this entry.
         *
         * @return the key corresponding to this entry
         * @throws IllegalStateException implementations may, but are not
         *         required to, throw this exception if the entry has been
         *         removed from the backing map.
         */
        K getKey();

        /**

分析:Entry是一个结点,它持有下一个元素的引用,这样就构成了一个链表。整体上来说HashMap底层使用一个数据结构来实现的。


问题1:Hash值如何与元素的存储建立关系呢?(Hash算法)

在数据结构课中我们学习过Hash的简单算法,就是给你一个Hash因子,通过对该元素的hashCode简单的求余,来实现对其快速的定位和索引。在HashMap中有这样的代码:

/**
* Returns index for hash code h.
*/ 
static int indexFor(int h, int length) { 
   return h & (length-1); 
} 
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
   return h & (length-1);
}

这个方法在HashMap中非常重要,凡是与查询、添加、删除有关的方法中都会调用。这个方法是根据hashCode及当前table的长度(数组的长度,不是map的size)得到该元素应该存放的位置,或者在table中的索引。


问题2:当数据量已经超过初始定义的负载因子时,HashMap如何处理?

在HashMap中当数据量很多时,并且已经达到了负载限度时,会重新做一次哈希,也就是说会再散列。调用的方法为resize(),并且java默认传入的参数为2*table.length。先看一下JDK源码:

/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 *
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 *
 * @param newCapacity the new capacity, MUST be a power of two;
 *        must be greater than current capacity unless current
 *        capacity is MAXIMUM_CAPACITY (in which case value
 *        is irrelevant).
 */ 
void resize(int newCapacity) { 
	Entry[] oldTable = table; 
	int oldCapacity = oldTable.length; 
	if (oldCapacity == MAXIMUM_CAPACITY) { 
		threshold = Integer.MAX_VALUE; 
		return; 
	} 

	Entry[] newTable = new Entry[newCapacity]; 
	transfer(newTable); 
	table = newTable; 
	threshold = (int)(newCapacity * loadFactor); 
} 

/**
 * Transfers all entries from current table to newTable.
 */ 
void transfer(Entry[] newTable) { 
	Entry[] src = table; 
	int newCapacity = newTable.length; 
	for (int j = 0; j < src.length; j++) { 
		Entry<K,V> e = src[j]; 
		if (e != null) { 
			src[j] = null; 
			do { 
				Entry<K,V> next = e.next; 
				int i = indexFor(e.hash, newCapacity); 
				e.next = newTable[i]; 
				newTable[i] = e; 
				e = next; 
			} while (e != null); 
		} 
	} 
}

从上述代码中可以看出resize(再哈希)的工作量是很大的。再哈希是重新建一个指定容量的数组,然后将每个元素重新计算它要放的位置。


这里就产生了一个很重要的问题,那就是怎么让哈希表的分布比较均匀,也就是说怎么让它即不会成为一个单链表(极限情况,每个key的hash值都集中到了一起),又不会使hash空间过大(导致内存浪费)?


上面两个问题一个是解决了怎么计算hash值快速存取,一个是怎么实现再哈希,何时需要再哈希。快速存取的前提是元素分布均匀,不至于集中到一点,再哈希是元素过于零散,导致不断的重新构建表。


那么在第一个问题中我们看到了这样一个代码return h & (length-1);在第二个问题中我们说过内部调用传入的值为2*table.length;并且默认情况下HashMap的大小为一个16的数字,除了默认构造提供大小为16的空间外,如果我们使用

// Find a power of 2 >= initialCapacity 
int capacity = 1; 
while (capacity < initialCapacity) 
      capacity <<= 1; 
…… 
table = new Entry[capacity]; 
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
      capacity <<= 1;
……
table = new Entry[capacity];

也就是说当我们传入1000时,它并没有给我们构造一个容量为1000的哈希表,而是构建了一个容量为1024大小的哈希表。


无论什么情况HashMap中哈希表的容量总是2的n次方的一个数,公式:当length=2^n时,hashcode & (length-1) == hashcode % length。

也就是这一点验证了第一个问题,hash索引值的计算方法其实就是对哈希因子求余。只有大小为2的n次方时,那样的计算才成立,所以HashMap为我们维护了一个这样大小的一个哈希表。(位运算速度比取模运算快的多)


2)HashMap的使用方法:

在实际开发中我们都会使用HashMap,因为它符合存储关联数据的要求,其次它的存取速度快。

Map的三种遍历方法,分别如下:

a. 使用keySet遍历,while循环;

b. 使用entrySet遍历,while循环;

c. 使用for循环遍历。


3)LinkedHashMap的特点、实现机制及使用方法


LinkedHashMap的特点:

LinkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样,LinkedHashMap允许key和value均为null。于该数据结构和HashMap一样使用到hash算法,因此它不能保证映射的顺序,尤其是不能保证顺序持久不变(再哈希)。如果在多线程中使用,那么需要使用Collections.synchronizedMap方法进行外部同步。

LinkedHashMap与HashMap的不同之处在于,LinkedHashMap维护者运行于所有条目的双重链接列表,此链接列表可以是插入顺序或者访问顺序。


HashMap与Hashtable的区别:

Hashtable实现Map接口,继承自古老的Dictionary类,实现一个key-value的键值映射表。任何非空的(key-value)均可以放入其中,基于陈旧的Dictionary实现的,而HashMap是基于Java1.2引进的Map接口实现的;Hashtable是线程安全的,而HashMap是非线程安全的,我们可以使用外部同步的方法解决这个问题;HashMap可以允许你在列表中放一个key值为null的元素,并且可以有任意多value为null,而Hashtable不允许键或者值为null。


两大基类Collection与Map

在集合框架的类继承体系中,最顶层有两个接口:

Collection表示一组纯数据

Map表示一组key-value对,一般继承自Collection或Map的集合类,会提供两个“标准”的构造函数:

没有参数的构造函数,创建一个空的集合类

有一个类型与基类(Collection或Map)相同的构造函数,创建一个与给定参数具有相同元素的新集合类

因为接口中不能包含构造函数,所以上面这两个构造函数的约定并不是强制性的,但是在目前的集合框架中,所有继承自Collection或Map的子类都遵循这一约定。


Collection类主要有三个接口:

Set表示不允许有重复元素的集合(A collection that contains no duplicate elements)

List表示允许有重复元素的集合(An ordered collection (also known as a sequence))

Queue JDK1.5新增,与上面两个集合类主要是的区分在于Queue主要用于存储数据,而不是处理数据。(A collection designed for holding elements prior to processing.)


Map并不是一个真正意义上的集合(are not true collections),但是这个接口提供了三种“集合视角”(collection views ),使得可以像操作集合一样操作它们,具体如下:

把map的内容看作key的集合(map’s contents to be viewed as a set of keys)

把map的内容看作value的集合(map’s contents to be viewed as a collection of values)

把map的内容看作key-value映射的集合(map’s contents to be viewed as a set of key-value mappings)

评论

分享:

支付宝

微信