设为首页收藏本站
开启辅助访问

在路上

 找回密码
 立即注册
在路上 › 站点首页 ›学习 › 查看内容

Java容器类型使用总结

2016-12-22 13:25| 发布者: zhangjf| 查看: 475| 评论: 0

摘要: 最近抽空把java.lang下面常用的那些容器类型（数据结构）复习了一下，这些东西是基础，平时使用的时候也可以很容易查得到，有些方法大概知 道，但是总是弄混，如果可以记住那些重要方法，并且能够熟练使用的话，还是 ...

最近抽空把java.lang下面常用的那些容器类型（数据结构）复习了一下，这些东西是基础，平时使用的时候也可以很容易查得到，有些方法大概知 道，但是总是弄混，如果可以记住那些重要方法，并且能够熟练使用的话，还是可以让编码过程变得容易很多。另外一个是实现机制，对于常用数据结构的实现机 制，应该说是必须要熟知的。

另外，并发容器我之前整理过，放在这篇文章里。

Queue

add和offer的区别在于达到上限时add抛出异常，offer返回false； remove和poll的区别在于，队列为空时前者抛出异常，后者返回空； element和peek都返回队列头部元素，但是前者失败不抛出异常，后者返回空。
  1. boolean add(E e);
  2. boolean offer(E e);
  4. E remove();
  5. E poll();
  7. E element();
  8. E peek();
复制代码

PriorityQueue，内部实现是一个Object[] queue承载的堆。

Deque，双端队列（double-ended queue），在Queue基础上，增加了这样几个方法：

  1. void addFirst(E e);
  2. void addLast(E e);
  4. boolean offerFirst(E e);
  5. boolean offerLast(E e);
  7. E removeFirst();
  8. E removeLast();
  10. E pollFirst();
  11. E pollLast();
  13. E getFirst();
  14. E getLast();
  16. E peekFirst();
  17. E peekLast();
  19. boolean removeFirstOccurrence(Object o);
  20. boolean removeLastOccurrence(Object o);
复制代码

ArrayDequeue：数组实现，扩容策略是容量翻倍。

List

  1. boolean add(E e);
  2. boolean remove(Object o);
  3. E get(int index);
  4. E set(int index, E element);
  5. void add(int index, E element);
  6. E remove(int index);
复制代码

ArrayList，扩容策略是(oldCapacity * 3)/2 + 1。

LinkedList，它除了实现自List接口外，还实现了Deque接口。

Vector，实现自List接口，内部实现是个数组，线程安全，扩容策略是(capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2)。

Stack是Vector的子类，增加了一些栈的方法：

  1. E push(E item)
  2. E pop()
  3. E peek()
  4. boolean empty()
复制代码

Map

  1. boolean containsKey(Object key);
  2. boolean containsValue(Object value);
  4. V get(Object key);
  5. V put(K key, V value);
  6. V remove(Object key);
  8. Set<K> keySet();
  9. Collection<V> values();
  10. Set<Map.Entry<K, V>> entrySet();
复制代码

SotedMap接口，key是有序的map：

  1. SortedMap<K, V> subMap(K paramK1, K paramK2);
  2. SortedMap<K, V> headMap(K paramK);
  3. SortedMap<K, V> tailMap(K paramK);
  5. K firstKey();
  6. K lastKey();
复制代码

子接口NavigableMap，提供了一些根据某个key寻找它前面或者后面的key的方法。其中floorKey/celingKey表示的关系是小于等于/大于等于，lower/higher表示的关系是严格的小于/大于：

  1. Map.Entry<K,V> floorEntry(K key)
  2. K floorKey(K key)
  3. Map.Entry<K,V> ceilingEntry(K key)
  4. K ceilingKey(K key)
  6. Map.Entry<K,V> lowerEntry(K key)
  7. K lowerKey(K key)
  8. Map.Entry<K,V> higherEntry(K key)
  9. K higherKey(K key)
复制代码

TreeMap是NavigableMap的直接实现子类，内部实现是一个红黑树。

EnumMap，结构是, V>，内部是通过一个K[] keyUniverse和一个Object[] vals来实现的。

HashMap，内部是数组+链表实现的，达到threshold = capacity * loadFactor时，扩容策略为：numKeysToBeAdded / loadFactor + 1。

HashTable，实现自Dictionary和Map，方法都是 线程安全的。HashTable的put方法，value不可以为空，这是它和HashMap的一个不同；再有二者找桶的hash方法不同；最后则是 threshold计算逻辑相同，但它的扩容策略不同：oldCapacity * 2 + 1。HashTable、HashMap和HashSet经常被放到一起比较。

Properties，是HashTable的子类，方法线程安全。

IdentityHashMap，比较key不是使用equals来比较，而是使用“==”来比较，只要地址不等（即不是同一个对象）即可共存，也就是说，key是可以重复的。

LinkedHashMap，在HashMap的基础上，又单独维护 了一个双向循环链表。有一个重要参数是accessOrder，accessOrder为true时，每次调用get方法访问行为发生后，会把最近访问的 对象移动到头部，而超出容量移除对象时，是从尾部开始的，利用它并且覆写boolean removeEldestEntry方法可以实现一个LRU的队列。

WeakHashMap，但是key是weak引用，在不被使用时自 动清除，扩容策略：tab.length * 2。原理上看：Entry extends WeakReference implements Map.Entry，因此entry是弱引用的实现类，关键方法是expungeStaleEntries，它在对这个map各种 操作的时候都会被调用到，而这个方法里面也是靠监听key的ReferenceQueue这个队列的状态来确定是否真的没有对象引用了。

Set

  1. boolean contains(Object o);
  2. boolean add(E e);
  3. boolean remove(Object o);
复制代码

SortedSet，接口方法和SortedMap类似：

  1. SortedSet<E> subSet(E fromElement, E toElement);
  2. SortedSet<E> headSet(E toElement);
  3. SortedSet<E> tailSet(E fromElement);
  5. E first();
  6. E last();
复制代码

相应地，NavigableSet和NavigableMap类似，方法就不列出了。

TreeSet则和TreeMap类似，其实内部实现就是一个TreeMap。

HashSet，尤其注意的是，有两种实现，当构造方法参数小于3个时，内部使用HashMap，否则，使用LinkedHashMap。

RegularEnumSet和JumboEnumSet，前者是普通的枚举set（用位移来表示各种组合的可能，达到空间占用最小，最大不能超过64个枚举值），后者适合数量较大的枚举set（老老实实地使用对象数组）。

LinkedHashSet，其实和LinkedHashMap是一个东西。

BitSet，叫set但是没有实现set的接口。用比特位来存放某个数是否存在，比如仅仅一个long，64位，就可以存放0~63的数，内部实际的数据类型是long[]。

  1. void flip(int bitIndex);
  2. void flip(int fromIndex, int toIndex);
  4. void set(int bitIndex);
  5. void set(int fromIndex, int toIndex, boolean value);
  7. void clear(int bitIndex);
  9. int length();
  10. int size();
复制代码

其中size方法返回实际使用了的比特位数目；length方法返回逻辑意义上的长度（比如表示的数里面最大是80，那么加上0，它的逻辑意义上的长度就是81）。

扩容策略：Math.max(2 * words.length, wordsRequired)。

Dictionary

  1. Enumeration<K> keys();
  2. Enumeration<V> elements();
  4. V get(Object key);
  5. V put(K key, V value);
  6. V remove(Object key);
复制代码

已经被废弃了，用Map来实现相同功能。

最后这张图来自这个网站，对于从宏观上把握这些容器类型实在是太有帮助了：

Java容器类型使用总结

来源：四火的唠叨
收藏 邀请
上一篇：在Java中如何避免“!=null”式的判空语句?下一篇：一个Java 8中简单Lambda表达式程序

最新评论

相关分类

小黑屋|在路上 ( 蜀ICP备15035742号-1 )  

;

GMT+8, 2025-7-9 20:22

Copyright 2015-2025 djqfx

返回顶部