java容器类型使用总结-mile米乐体育

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

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

queue

1. add和offer的区别在于达到上限时add抛出异常，offer返回false；
2. remove和poll的区别在于，队列为空时前者抛出异常，后者返回空；
3. element和peek都返回队列头部元素，但是前者失败不抛出异常，后者返回空。

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：数组实现，扩容策略是容量翻倍。

list

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()

map

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这个队列的状态来确定是否真的没有对象引用了。

set

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来实现相同功能。

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