来自:四火的唠叨
作者:四火,Amazon程序员 全栈工程师 @西雅图
链接:http://www.raychase.net/2834(点击尾部阅读原文前往)
最近抽空把java.lang下面常用的那些容器类型(数据结构)复习了一下,这些东西是基础,平时使用的时候也可以很容易查得到,有些方法大概知道,但是总是弄混,如果可以记住那些重要方法,并且能够熟练使用的话,还是可以让编码过程变得容易很多。另外一个是实现机制,对于常用数据结构的实现机制,应该说是必须要熟知的。
另外,并发容器我之前整理过,放在这篇文章里 http://www.raychase.net/1912
1、add和offer的区别在于达到上限时add抛出异常,offer返回false;
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
PriorityQueue,内部实现是一个Object[] queue承载的堆。
Deque,双端队列(double-ended queue),在Queue基础上,增加了这样几个方法:
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
ArrayDequeue:数组实现,扩容策略是容量翻倍。
boolean add(E e);
boolean remove(Object o);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
ArrayList,扩容策略是(oldCapacity * 3)/2 + 1。
LinkedList,它除了实现自List接口外,还实现了Deque接口。
Vector,实现自List接口,内部实现是个数组,线程安全,扩容策略是(capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2)。
Stack是Vector的子类,增加了一些栈的方法:
E push(E item)
E pop()
E peek()
boolean empty()
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
Set
keySet(); Collection
values(); Set<>
> entrySet();
SotedMap接口,key是有序的map:
SortedMap
subMap(K paramK1, K paramK2); SortedMap
headMap(K paramK); SortedMap
tailMap(K paramK);
K firstKey();
K lastKey();
子接口NavigableMap,提供了一些根据某个key寻找它前面或者后面的key的方法。其中floorKey/celingKey表示的关系是小于等于/大于等于,lower/higher表示的关系是严格的小于/大于:
Map.Entry
floorEntry(K key) K floorKey(K key)
Map.Entry
ceilingEntry(K key) K ceilingKey(K key)
Map.Entry
lowerEntry(K key) K lowerKey(K key)
Map.Entry
higherEntry(K key) 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这个队列的状态来确定是否真的没有对象引用了。
boolean contains(Object o);
boolean add(E e);
boolean remove(Object o);
SortedSet,接口方法和SortedMap类似:
SortedSet
subSet(E fromElement, E toElement); SortedSet
headSet(E toElement); SortedSet
tailSet(E fromElement);
E first();
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[]。
void flip(int bitIndex);
void flip(int fromIndex, int toIndex);
void set(int bitIndex);
void set(int fromIndex, int toIndex, boolean value);
void clear(int bitIndex);
int length();
int size();
其中size方法返回实际使用了的比特位数目;length方法返回逻辑意义上的长度(比如表示的数里面最大是80,那么加上0,它的逻辑意义上的长度就是81)。
扩容策略:Math.max(2 * words.length, wordsRequired)。
Dictionary
Enumeration
keys(); Enumeration
elements();
V get(Object key);
V put(K key, V value);
V remove(Object key);
已经被废弃了,用Map来实现相同功能。
最后这张图来自这个网站,对于从宏观上把握这些容器类型实在是太有帮助了:
●本文编号283,以后想阅读这篇文章直接输入283可。
●输入m可以获取到文章目录
算法与数据结构
推荐《15个技术类公众微信》
涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。
联系客服