集合类小结

一、数组与集合

  数组(可以存储对象包括基本类型)是一种常见的数据结构,对元素访问快速,但长度固定,存储数据类型需一致。

  集合只能存储对象,长度可变,可以存储不同类型的对象。

  数组与集合之间可以通过toArray()和Arrays.asList()相互转换。注:(asList返回的对象是一个Arrays内部类,并没有实现集合的add/remove/clear方法。)

二、集合框架图

  集合类存放在java.util包中,主要两种类型:Collection和Map,继承关系如下图:

 

List、Set和Map是集合中的三个主要接口。其中,List和Set继承自Collection(没有直接实现类)根接口,Map和Collection相互独立,但也属于集合类。

  List:有序且允许元素重复;基于数组的Vector和ArrayList适合查询,而基于链表的LinkedList适合添加,删除操作。

  Set:无序且不允许元素重复;不能重复的原因是:Set实现的基础是Map(HashMap),HashMap的key不能重复。

  Map:键值对集合,键不能重复,值可重复。

三、集合类遍历

1、Collection

Collection没有get()方法来获取某个元素,只能通过iterator()遍历元素;foreach内部也是采用了Iterator的方式实现(循环体remove/add会导致expectedModCount和modCount不相等报异常);List可以通过get()方法获取元素,ListIterator是Iterator的子接口,专门用于List。

//iterator
Iterator iterator = list.iterator(); 
while(iterator.hasNext()){ 
  int i = (Integer) iterator.next();                   
  System.out.println(i);   
}

//foreach
for (Object object : list) {  
  System.out.println(object);      
}

//for
for (int i = 0 ;i<list.size();i++) {      
  int v= (Integer) list.get(i);                     
  System.out.println(v);         
} 
    

2、Map

1)通过Map.keySet()将Map中的所有key存入到Set集合中,然后通过iterator()获取迭代器或者foreach遍历key,最后通过Map.get(key)方法取得对应的值。

//iterator
Iterator it=map.keySet().iterator(); 
while(it.hasNext()){ 
    String key; 
    String value; 
    key=it.next().toString(); 
    value=map.get(key); 
    System.out.println(key+"--"+value); 
} 

//foreach
for (String key : map.keySet()) {
  System.out.println("key= " + key + " and value= " + map.get(key));
}

2)通过Map.entrySet()将键值对作为一个整体一对一对地存放到Set集合中,Map.Entry表示映射关系,然后通过iterator()获取迭代器或者foreach遍历获取键(e.getKey())和值(e.getValue());

//iterator
Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
     Map.Entry<Integer, String> entry = it.next();
     System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

//foreach
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

3)通过Map.values()遍历所有的value,但不能遍历key。

for (String v : map.values()) {
    System.out.println("value= " + v);
}

四、接口实现类的区别比较

1、ArrayList和Vector

1)同步性:Vector使用了synchronized方法,是同步和线程安全的,ArrayList是异步和线程非安全的(并发写易出现ConcurrentModificationException),可以通过List Collections.synchronizedList(List list)实现同步。

2)数据增长:当元素个数超过容量时,Vector默认增长为原来的2倍,ArrayList为1.5倍;ArrayList与Vector都可以设置初始的空间大小,Vector还可以设置增长的空间大小,而ArrayList没有提供设置增长空间的方法。

 2、ArrayList和LinkedList

1)实现基础:ArrayList基于数组,LinkedList基于双向链表。

2)效率:get和set操作,ArrayList占优;add和remove操作LinkedList占优。

3、HashMap和Hashtable

1)继承:HashMap继承于AbstractMap,Hashtable继承于Dictionary。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

2)同步性:Hashtable是同步的;HashMap是非同步的,可以通过Map Collections.synchronizedMap(Map m)实现;如需线程安全,推荐使用ConcurrentHashMap。

3)键值要求:HashMap允许存在一个为null的key,多个为null的value ;Hashtable的key和value都不允许为null。

4)遍历方式内部实现:Hashtable、HashMap都使用了 Iterator;由于历史原因,Hashtable还使用了Enumeration的方式 。

5)默认大小和扩容方式:Hashtable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。

jdk1.7
java.util.HashTable
// 哈希表默认初始大小为11
public Hashtable() {
    this(11, 0.75f);
}

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;

    // 每次扩容为原来的2n+1
    int newCapacity = (oldCapacity << 1) + 1;
    // ...
}


java.util.HashMap
// 哈希表默认初始大小为2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 每次扩充为原来的2n 
    if ((size >= threshold) && (null != table[bucketIndex])) {
       resize(2 * table.length);
}

6)Hashtable直接使用对象的hashCode,而HashMap重新计算hash值

jdk1.7
java.util.HashTable
// hash 不能超过Integer.MAX_VALUE 所以要取其最小的31个bit int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length; // 直接计算key.hashCode() private int hash(Object k) { // hashSeed will be zero if alternative hashing is disabled. return hashSeed ^ k.hashCode(); } java.util.HashMap int hash = hash(key); int i = indexFor(hash, table.length); // 在计算了key.hashCode()之后,做了一些位运算来减少哈希冲突 final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // 取模不再需要做除法 static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }

JDK7中HashMap采用的是位桶+链表的方式,即我们常说的散列链表的方式,而JDK8中采用的是位桶+链表/红黑树(有关红黑树请查看红黑树)的方式。当某个位桶的链表的长度达到某个阀值(8)的时候,这个链表就将转换成红黑树,改进链表过长查询慢的问题。另外,JDK8将链表头插改为尾插,避免并发死循环问题,当然仍然是非线程安全,比如数据丢失。

7)Hashtable有一个contains(Object value),功能和containsValue(Object value)功能一样。

原文地址:https://www.cnblogs.com/aaron-shu/p/6720238.html