W.T.的博客

Every day to be a little better

Java基础知识-集合

发表于 更新于 分类于
本文字数： 20k 阅读时长 ≈ 18 分钟
Collection List Set Map

1. Collection接口

集合接口，List，Set，Queue都实现了这个接口

常用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Collection;

Iterator<E> iterator();
int size();
boolean isEmpty();
boolean contains(Object obj);
//转换为数组
Object[] toArray();
//添加元素
boolean add(E e);
//删除单个元素
boolean remove(Object o);
//并 other元素添加到集合中
boolean addAll(Collection<E> other);
//交 删除与other中匹配的所有元素
boolean removeAll(Collection other);
//差 删除与other不同的元素
boolean retainAll(Collection other);

//批量删除符合filter条件的所有元素 Predicate对象
default boolean removeIf(Predicate<? super E> filter);
Collection.removeIf(ele->(String)ele.length()<10);

void clear();

2. 迭代器-ArrayList

删除第一个元素：

1
2
3
4
5
6
7
ArrayList<String> c = new ArrayList<>();
c.add("a");
c.add("b");
//调用remove之前必须调用next
Iterator< String> it = c.iterator();
it.next();
it.remove();

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private class Itr implements Iterator<E> {
  // index of next element to return
  int cursor;  
  // index of last element returned; -1 if no such
  int lastRet = -1; 
  
  public boolean hasNext() {
     return cursor != size;
  }
  //返回要访问的下一个对象
  public E next() {
      int i = cursor;
      cursor = i + 1;
      return (E) elementData[lastRet = i];
  }
  //删除上次调用next方法返回的元素
  public void remove() { 
    cursor = lastRet;
    lastRet = -1;
  }
}

3. 固定长度的List

Arrays的内部类ArrayList的实例，不可增加，删除元素，没有重写add，remove方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
List list = Arrays.asList(Object... obj);

 public static <T> List<T> asList(T... a) {
      return new ArrayList<>(a);
 }

 private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable{
       
        private final E[] a;

        @Override
        public E get(int index) {}

        @Override
        public E set(int index, E element) { }

        @Override
        public boolean contains(Object o) {}

        @Override
        public void sort(Comparator<? super E> c) { }
    }

List list = Arrays.asList();
//Exception in thread "main" java.lang.UnsupportedOperationException
list.add(2);
System.out.println(list.size());

基本数据类型和包装类的不同

1
2
3
4
5
6
7
8
9
10
11
12
13
List<int[]> list = Arrays.asList(new int[]{1,2,3,4});
//[[I@6166e06f]
System.out.println(list);
//1
System.out.println(list.get(0)[0]);
//1
System.out.println(list.size());

List<Integer> list2 = Arrays.asList(new Integer[]{1,2,3});
//[1,2,3]
System.out.println(list2);
//3
System.out.println(list2.size());

4. LinkedList

双向链表实现，只能顺序访问，故get方法效率低，可以快速插入和删除元素。

结点 prev|element|next，双向链表

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

类继承AbstractSequentialList，实现List接口

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

4.1. add() 采用尾插法

1
2
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;

4.2. 查找结点

前一半从前往后，后一半从后往前

1
2
3
4
5
6
7
8
9
10
11
if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
        x = x.next;
    return x;
} else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
        x = x.prev;
    return x;
}

4.3. 非List标准的方法

方法 说明
void addFirst(E e) 将指定元素插入到开头
void addLast(E e) 将指定元素插入到结尾
getFirst() 返回此列表的第一个 元素
getLast() 返回此列表的最后一个元素
removeFirst() 移除此列表的第一个元素，并返回这个元素
removeLast() 移除此列表中的最后一个元素，并返回这个元素
E pop() 从此列表所表示的堆栈处弹出一个元素，等效于removeFirst
void push(E e) 将元素推入此列表所表示的堆栈，等效于addFirst
boolean isEmpty() 判断列表是否包含元素，如果不包含元素返回true

5. ArrayList

动态数组，支持随机访问

1
2
3
4
5
6
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable,java.io.Serializable{}

transient Object[] elementData;
//数组默认大小10
private static final int DEFAULT_CAPACITY = 10;

jdk1.7:

1
2
3
public ArrayList() {
    this(10);
}

jdk1.8:

只创建空的数组

等到插入数据时才扩容为10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
grow(minCapacity){
				int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
				elementData = Arrays.copyOf(elementData, newCapacity);
}

5.1. add()

1
elementData[size++] = e;

5.2. remove()

调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)

1
2
3
int numMoved = size - index - 1;
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null;

5.3. 序列化

Serializable表示可以被序列化，保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。实现 writeObject() 和 readObject() 来控制序列化数组中有元素填充那部分内容。

5.4. 转换为数组

Object[] toArray()

<T> T[] toArray(T[] a)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//ArrayList
transient Object[] elementData;
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}


//Arrays
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Test
void testSystem(){
     ArrayList<String> list = new ArrayList<>();
     list.add("a");
     list.add("b");
     list.add("c");

    /*
     Object并不能转为String
     java.lang.ClassCastException: [Ljava.lang.Object; 
     cannot be cast to [Ljava.lang.String;
     String[] array = (String[])list.toArray(); 
    */ 
    Object[] array = list.toArray();
    for (Object obj: array) {
        System.out.println(obj);
    }

    String[] array1 = list.toArray(new String[list.size()]);
    for (String obj: array1) {
        System.out.println(obj);
    }
}

6. Vector

1
2
3
4
5
6
public class Vector<E>  extends AbstractList<E> implements List<E>{
  protected Object[] elementData;
  public Vector() {
        this(10);
  }
}

扩容

1
int newCapacity = oldCapacity + oldCapacity;

内部采用synchronized同步块，线程安全

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public synchronized E get(int index) {}

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

public synchronized E get(int index) {
   return (E) elementData[index];
}

7. Stack

1
2
3
4
5
public class Stack<E> extends Vector<E> {
  protected Object[] elementData;
  
  elementData[elementCount++] = obj;
}

8. HashSet

内部采用HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class HashSet<E>extends AbstractSet<E> implements Set<E>

private transient HashMap<E,Object> map;
public HashSet() {
     map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

private static final Object PRESENT = new Object();
public boolean add(E e) {
     return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
     return map.remove(o)==PRESENT;
}

可以将数组转为集合

1
2
String[] str = {"A","B"};
HashSet<String> hashSet = new HashSet<>(Arrays.asList(str));

集合转为数组

1
2
3
String[] reverse = hashSet.toArray(new String[2]);

hashSet.toArray(); //返回的是Object[]

9. TreeSet

基于红黑树实现，有序

1
2
3
4
5
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> 

public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
}

类排列实现：

  • 类实现Comparable接口，实现compareTo方法

    1
    2
    3
    4
    5
    class Item implements Comparable<Item>{
      public int compareTo(Item other){
        return ...;
      }
    }

  • TreeSet实例化Comparator匿名内部类

    1
    2
    3
    4
    5
    6
    TreeSet<test> set = new TreeSet<>(new Comparator<test>() {
        @Override
        public int compare(test o1, test o2) {
            return 0;
        }
    });

10. HashMap

10.1. 常用方法

1
2
3
4
5
6
7
8
9
public V put(K key, V value) {}
public V get(Object key) {}
 public V remove(Object key) {}
public void clear() {}
public boolean containsKey(Object key){}
//得到key集合
public Set<K> keySet() {}
//key-value集合
public Set<Map.Entry<K,V>> entrySet() {}
  • HashMap 可以插入键为 null 的 Entry。
  • HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>

//table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//装载因子，用来确认table 数组是否需要动态扩展，threshold = (int)(newCapacity * loadFactor)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作，当链表长度超过 8 时，链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
//当红黑树结点个数大于6时，把红黑树重新转为链表
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
//当数组长度达到64时，红黑树结点达到6时才会进行链表转换
static final int MIN_TREEIFY_CAPACITY = 64;

transient Node<K,V>[] table;

映射

hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

结点

1
2
3
4
5
6
Node(int hash, K key, V value, Node<K,V> next) {
      this.hash = hash;
      this.key = key;
      this.value = value;
      this.next = next;
}

插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { 
      next = e.next;
      if ((e.hash & oldCap) == 0) {
          if (loTail == null)
                 loHead = e;
          else
                loTail.next = e;
       loTail = e;
      }else {
             if (hiTail == null)
                   hiHead = e;
              else
                   hiTail.next = e;
              hiTail = e; }
} while ((e = next) != null);

//扩容为2倍
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

10.2. 工作原理

1
2
3
HashMap<String, String> map = new HashMap<>();
map.put("K1", "V1");
map.put("K2", "V2");
  • 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 1，使用除留余数法得到所在的下标 1%16=1。
  • 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 1，使用除留余数法得到所在的桶下标 1%16=1,插在 <K1,V1> 后面。

HashMap采用的是尾插法。

HashMap底层采用hash数组和单向链表实现。初始数组长度为16，每个数组元素为一个Node。

存储：put中传入K，V值。

1）调用hash(k)计算K的hash值，结合数组长度得到数组下标。

  1. 调整数组大小当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n；

  2. 如果K的hash值在HashMap中不存在，则插入；已存在，比较两者equals，false则采用拉链法尾插到数组中，equals为true，更新V值。

获取：

  1. 调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；

2）顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。

10.3. 遍历方式

  • for-each map.keySet() 

    1
    2
    3
    for (String key : map.keySet()) {
        map.get(key);
    }

  • for-each map.entrySet() 

    1
    2
    3
    4
    for (Map.Entry<String, String> entry : map.entrySet()) {
        entry.getKey();
        entry.getValue();
    }

  • for-each map.entrySet()

    1
    2
    3
    4
    5
    Set<Map.Entry<String, String>> entrySet = map.entrySet();
        for (Map.Entry<String, String> entry : entrySet) {
            entry.getKey();
            entry.getValue();
    }

  • for-each map.entrySet().iterator()

    1
    2
    3
    4
    5
    6
    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> entry = iterator.next();
            entry.getKey();
            entry.getValue();
    }

11. Hashtable

线程安全的集合类，Hashtable的properties子类仍应用于IO流中

1
2
3
4
5
6
7
public class Hashtable<K,V>extends Dictionary<K,V>
    implements Map<K,V>
   
public Hashtable(int initialCapacity, float loadFactor) 
public Hashtable() {
        this(11, 0.75f);
}

键值对都不允许为null,线程安全

1
2
3
4
5
public synchronized V put(K key, V value)
public synchronized V remove(Object key)

int hash = key.hashCode();
int newCapacity = (oldCapacity << 1) + 1;

12. HashMap vs. Hashtable

HashMap Hashtable
父类 AbstractMap Dictionary
安全性 线程不安全 线程安全
键值 允许一条记录键值为null，允许多条记录的值为null 键值都不允许为null
初始化数组 16 11
扩容 扩大2倍 扩大2倍+1
hash值 采用高低16位异或计算 直接使用hashCode

13. CurrentHashMap - 同步

ConcurrentHashMap是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现。

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；

ConcurrentHashMap
JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>    
  
private static final int DEFAULT_CAPACITY = 16;  

transient volatile Node<K,V>[] table;

/**
 * Returns the stamp bits for resizing a table of size n.
 * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
 */
private static int RESIZE_STAMP_BITS = 16;

static final int resizeStamp(int n) {
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
  
				Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
}

使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。

并且也在链表过长时会转换为红黑树。

插入结点 

1
synchronized (f) { }

jdk1.7

采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment 和 HashEntry。
①、Segment 继承 ReentrantLock（重入锁） 用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶；
②、HashEntry 用来封装映射表的键-值对；
③、每个桶是由若干个 HashEntry 对象链接起来的链表。

jdk 1.8

采用Node + CAS + Synchronized来保证并发安全。取消类 Segment，直接用 table 数组存储键值对；当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。

Java Collection Framework

Iterator 模式

Java 8 系列之重新认识 HashMap

What is difference between HashMap and Hashtable in Java?

Java 集合之 HashMap

The principle of ConcurrentHashMap analysis

探索 ConcurrentHashMap 高并发性的实现机制

HashMap 相关面试题及其解答

Java 集合细节（二）：asList 的缺陷

Java Collection Framework – The LinkedList Class

14. ConcurrentSkipListMap- 同步,有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
  
    /**
     * The topmost head index of the skiplist.
     */
    private transient volatile HeadIndex<K,V> head;
  
    static final class Node<K,V> {
        final K key;
        volatile Object value;
        volatile Node<K,V> next;
    }
}

15. ConcurrentSkipListSet- 同步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ConcurrentSkipListSet<E>
    extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
  
    private final ConcurrentNavigableMap<E,Object> m;

    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E,Object>();
    }
  
    public ConcurrentSkipListSet(Comparator<? super E> comparator) {
        m = new ConcurrentSkipListMap<E,Object>(comparator);
    }
  
    public boolean add(E e) {
        return m.putIfAbsent(e, Boolean.TRUE) == null;
    }
  
   public boolean remove(Object o) {
        return m.remove(o, Boolean.TRUE);
    }
}

16. ConcurrentLinkedQueue- 同步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable {
  
  private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
  }
  
  private transient volatile Node<E> head;
  private transient volatile Node<E> tail;
  
  public ConcurrentLinkedQueue() {
        head = tail = new Node<E>(null);
  }
}

17. CopyOnWriteArrayList - 同步

初始化数组长度为0

添加时，将数组长度+1，再复制原数组元素，整个过程添加锁机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
  
  /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();
  
   private transient volatile Object[] array;
  
   /**
     * Sets the array.
     */
    final void setArray(Object[] a) {
        array = a;
    }

    /**
     * Creates an empty list.
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
  
		public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
  
   //删除
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
}

18. CopyOnWriteArraySet - 同步

内部采用CopyOnWriteArrayList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    private final CopyOnWriteArrayList<E> al;

    /**
     * Creates an empty set.
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
  
    public boolean add(E e) {
        return al.addIfAbsent(e);
    }
  
    public boolean remove(Object o) {
        return al.remove(o);
    }
}

19. TreeMap

用于比较

1
2
3
4
5
6
public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>
    
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
}

20. LinkedHashMap

1
2
3
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

结点

内部维护了一个双向链表，用来维护插入顺序。

元素有序但不重复

1
2
3
4
5
6
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

Entry(int hash, K key, V value, Node<K,V> next) {
   super(hash, key, value, next);
}

21. EnumMap

1
public class EnumMap <K extends Enum<K>, V> extends AbstractMap<K, V>

key根据enum枚举类中的顺序排序，不允许使用key为null，允许value的null。

1
2
3
EnumMap e = new EnumMap(Season.class);
e.put(Season.SUMMER,"夏天");
e.put(Season.WINTER,"冬天");

22. WeakHashMap

1
2
public class WeakHashMap<K,V>extends AbstractMap<K,V>
    implements Map<K,V>

WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。

WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能。

ConcurrentCache 采取的是分代缓存：

  • 经常使用的对象放入 eden 中，eden 使用 ConcurrentHashMap 实现，不用担心会被回收；
  • 不常用的对象放入 longterm，longterm 使用 WeakHashMap 实现，这些老对象会被垃圾收集器回收。
  • 当调用 get() 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收。
  • 当调用 put() 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。

23. IdentityHashMap

1
public class IdentityHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>

允许使用null作为key和value，IdentityHashMap并不保证键值对的顺序。IdentityHashMap要求两个key严格相等才替换

1
2
3
4
5
IdentityHashMap<Object,int> id = new IdentityHashMap<>();
id.put(new String(a),1);
id.put(new String(a),2); //通过==判断不相等，则为2个key
id.put(1,1);
id.put(1,2); //直接量相等则为同一个key

24. 工具类Collections

1
2
3
4
5
6
7
8
9
//反转
 public static void reverse(List<?> list) {}
//随机洗牌
public static void shuffle(List<?> list) {}

//一次性添加元素
public static <T> boolean addAll(Collection<? super T> c, T... elements) {}
//同步
void synchronizedCollection(List list);

24.1. 排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//排序-默认升序
 public static <T extends Comparable<? super T>> void sort(List<T> list) {
   	// Arrays.sort(a, (Comparator) c);
    list.sort(null); 
 }
//采用比较接口进行排序
public static <T> void sort(List<T> list, Comparator<? super T> c) {}
public interface Comparator<T> {
  int compare(T o1, T o2);
}

List<MyClass> list = new ArrayList<>();
Collections.sort(list,new Comparator<MyClass>{
  public int compare(MyClass o1, MyClass o2){
    return 0;
  }
});

//或者类实现Comparable接口
public interface Comparable<T> {
  public int compareTo(T o);
}

public class MyClass implements Comparable<MyClass>{
  public int compareTo(MyClass o){
    return 0;
  }
}

List<MyClass> list = new ArrayList<>();
list.add(new MyClass());
Collections.sort(list);

25. Enumeration

Iterator的old版本,存在于vector，Hashtable中

1
2
3
4
5
Vector v = new Vector();
Enumeration em = v.elements();
while(em.hasMoreElements()){
  em.nextElement();
}
本文结束  感谢您的阅读
  • 本文作者： Wang Ting
  • 本文链接： /zh-CN/2019/09/13/Java基础知识-集合/
  • 发布时间： 2019-09-13 22:12
  • 更新时间： 2021-10-29 14:21
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

Gitalking ...