Guadazi
0%

Java Collection与Map

Posted on Edited on In

<< Java高级软件工程师知识结构

  1. 掌握Collection和Map的继承体系。
  2. 掌握ArrayList、LinkedList、Vector、Stack、PriorityQueue、HashSet、LinkedHashSet、TreeSet、HashMap、
  3. LinkedHashMap、TreeMap、WeakHashMap、EnumMap、HashTable的特点和实现原理。
    4.掌握CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentHashMap的实现原理和适用场景。

Java Collection与Map的继承关系

在程序设计中, 集合可以存储和传递一组数据. 集合虽然比不上数组的查询速度, 但是有更加方便的功能,
如可变长度、键值对、去重复等.
其家族成员有:

Collection是一个接口, 该接口允许添加和查找一个或多个元素、生成迭代器等功能.

List Set和Queue分别是继承了Collocation的子接口.
List用于存放可重复可为null的元素的有序集合. 并且可以对元素进行精确地控制, 可根据整数索引访问元素.
Set用于存放不可重复可为null的元素的集合,
Map并没有继承Collection, 是由一系列键值对组成的集合. 在Map中一个key对应一个value, key不能相同.

List接口

实现了List接口的集合主要有 ArrayList LinkedList Vector Stack

ArrayList

特性

  1. 可重复, 可为null: 添加元素是将元素存放到数组中
  2. 有序
  3. 擅长随机访问： 快速检索 增删慢
  4. 非线程同步
    通过Collections.synchronizedList(new ArrayList());转换为线程安全的List

实现原理
动态数组, 底层也是通过单个Java数组实现的, ArrayList根据元素个数动态调整内部数组的长度以达到实现动态数组的效果.
内部数组的初始长度为10, 当添加的元素的个数超出了内部数组的长度时, 调用JNI函数对内部数组实现扩容（为原长度的150%）和复制.
本质上, ArrayList是采用了线性表的结构, 因此, ArrayList具有快速检索的优点也具有增删慢的缺点.

复杂度
添加n个元素需要O(n)时间

优化建议 :
如果确定了插入元素的多少, 最好可以指定初始容量值,
避免过多的进行扩容和复制而浪费时间.

LinkedList

特性

  1. 不能随机访问
  2. 非线程同步
    通过Collections.synchronizedList(new LinkedList());转换为线程安全的List
  3. 善于插入和删除 不善于随机访问

实现原理
双向链表, 可以通过get remove insert方法操作首部和尾部的元素.

复杂度

与ArrayList对比
由于ArrayList是线性表的形式存储的, 需要连续的存储空间. 而LinkedList不需要连续,
因此在存储数据量较大的情况下, 优先选择LinkedList.

Vector

特性

  1. 线程同步
  2. 与ArrayList一样 ???

实现原理
线程安全的动态数组, 内部也是采用单个数组

复杂度

Stack 栈

特性

  1. 后进先出的栈
  2. 提供了除了ArrayList和Vector以外的栈操作方法:
    • push 压入栈
    • pop 出栈
    • peek 得到栈顶
    • empty 测试栈是否为空
    • search 检测一个元素在栈中的位置

实现原理
用Vector构建,而非继承自Vector

复杂度

【样例】: 使用栈实现计算器

Set接口

特性

  1. 不可重复
  2. 最多只允许一个null

EnumSet

特性

  1. 枚举专用Set
  2. 不是同步的
    多线程情况下, 最好在创建时完成这一操作, 以防止意外的非同步访问
    Set<MyEnum> s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));
  3. 枚举 set 中所有键都必须来自单个枚举类型, 该枚举类型在创建 set 时显式或隐式地指定.

实现原理

//TODO

复杂度

HashSet

特性

  1. 速度最快的集合
  2. 不能重复，最多一个为null

实现原理
内部存在一个HashMap, 借助于HashCode来实现, 所以不保证元素的顺序

复杂度

LinkedHashSet

特性

  1. 有序

实现原理
内部是LinkedHashMap实现的
LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它 同时使用链表维护元素的次序 。
当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

复杂度

TreeSet

特性

  1. 总是处于排序状态的Set(顺序取决于元素的自然顺序或者创建Set时指定的Comparator)
  2. 非线程同步
    多线程情况下,最好在创建时进行, 以防止对 set 的意外非同步访问：
    SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

实现原理
内部由TreeMap(使用红黑树)来实现

复杂度

Map接口

特性

  1. 键值对
  2. Key不能重复

HashMap

特性

  1. 线程不安全
  2. 初始容量设定

实现原理

参考链接: HashMap的工作原理

以哈希表的数据结构实现. 内部存在一个哈希表数组, 每个数组元素又有一组长度不确定的链表.

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。

HashMap在bucket中存储Map.Entry对象，每个Map.Entry保存有key和value。

get的工作原理

当使用get(key)方法，
首先调用hashing方法，利用key.hashcode计算key所在的bucket，找到相应的bucket后。
然后遍历bucket中的Map.Entry，首先比对key.hashcode值，其次比对(key值或key.equals方法比对两个对象)

1
2
if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))
return e;

在这里，使用了 && 的短路特性: 只要第一个条件不满足，不再比较后面的条件；只有前面的条件满足了，才比较后面的条件。
等价于

1
2
3
4
5
if(e.hash==hash){
  if((k = e.key) == key || (key != null && key.equals(k)){
return e;
  }
}

key的hashcode相同的情况

因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。当hashcode相同时，还会调用key.equals比对两个key对象是否相同。

负载因子 0.75

“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”
默认的负载因子大小为 0.75，也就是说，当一个map填满了 75% 的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。
这个过程叫作 rehashing，因为它调用hash方法找到新的bucket位置。

rehashing 过程

重新调整HashMap大小存在的问题:
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候， HashMap 并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

key类型的选择与提速

  • hashing的概念

  • HashMap 中解决碰撞的方法

  • equals()和hashCode()的应用，以及它们在HashMap中的重要性

  • 不可变对象的好处

    使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用 String，Interger 这样的wrapper类作为键是非常好的选择。而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。

    不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。

    因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

复杂度

LinkedHashMap

特性

  1. 非线程同步
  2. 有序： 可以按照访问顺序或者插入顺序排序

实现原理
底层使用哈希表与双向链表来保存所有元素。其基本操作与父类 HashMap 相似

LinkedHashMap 定义了排序模式 accessOrder，该属性为 boolean 型变量，对于访问顺序，为 true；
对于插入顺序，则为 false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。

//TODO 排序模式

TreeMap

特性

  1. 可排序
  2. 不是同步的
    SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

实现原理
红黑树的数据结构, 实现了SortedMap接口

复杂度

应用
TreeMap 常用于在接口参数拼接中，以自动对key排序

WeakHashMap

特性

  1. 当除了自身有对key的引用外，此key没有其他引用那么此map会自动丢弃此值

实现原理
使用弱引用作为内部数据的存储方案。 WeakHashMap可以作为简单缓存表的解决方案，
当系统内存不够的时候，垃圾收集器会自动的清除没有在其他任何地方被引用的键值对。

EnumMap

特性

  1. Key必须是Enum
  2. EnumMap的key不允许为null，value可以为null，按照key在enum中的顺序进行保存，非线程安全。

实现原理

HashTable

特性

  1. 线程安全
  2. 性能比HashMap差

实现原理
哈希表
使用 synchronized 锁住所有的读写操作

复杂度

Queue接口

// FIXME 实现原理

队列, 它主要分为两大类:

  • 一类是阻塞式队列, 队列满了以后再插入元素则会抛出异常, 主要包括
    • ArrayBlockQueue
    • PriorityBlockingQueue
    • LinkedBlockingQueue
  • 另一类是双端队列, 支持在头、尾两端插入和移除元素, 主要包括：
    • ArrayDeque
    • LinkedBlockingDeque
    • LinkedList

常见的队列有:

  1. ArrayDeque, （数组双端队列）
  2. PriorityQueue, （优先级队列）
  3. ConcurrentLinkedQueue, （基于链表的并发队列）
  4. DelayQueue, （延期阻塞队列）（阻塞队列实现了BlockingQueue接口）
  5. ArrayBlockingQueue, （基于数组的并发阻塞队列）
  6. LinkedBlockingQueue, （基于链表的FIFO阻塞队列）
  7. LinkedBlockingDeque, （基于链表的FIFO双端阻塞队列）
  8. PriorityBlockingQueue, （带优先级的无界阻塞队列）
  9. SynchronousQueue （并发同步阻塞队列）

PriorityQueue

无界优先级队列
特性

  1. 有序:
    • 顺序取决于元素的自然顺序或者创建队列时指定的Comparator
    • 依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。
  2. 不允许元素为null
  3. 优先级队列是无界的
    有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。
    随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。
  4. 非线程安全

PriorityBlockingQueue

无界优先级阻塞队列
特性

  1. 有序: 与PriorityQueue相同
  2. 不允许元素为null
  3. 无界: 资源耗尽时执行add会失败（导致 OutOfMemoryError）
  4. 线程安全

几种特殊的

CopyOnWriteArrayList

ArrayList的一个线程安全的变体, 所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制作为新的内部数组来实现的.

  • 这一般需要很大的开销, 但是当遍历操作的数量大大超过可变操作的数量时, 这种方法可能比其他替代方法更有效.
  • 在不能或不想进行同步遍历, 但又需要从并发线程中排除冲突时, 它也很有用.

“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用. 此数组在迭代器的生存期内不会更改, 因此不可能发生冲突, 并且迭代器保证不会抛出ConcurrentModificationException. 创建迭代器以后, 迭代器就不会反映列表的添加、移除或者更改. 在迭代器上进行的元素更改操作（remove、set 和 add）不受支持. 这些方法将抛出 UnsupportedOperationException.

允许使用所有元素, 包括 null.

内存一致性效果：

当存在其他并发 collection 时, 将对象放入 CopyOnWriteArrayList 之前的线程中的操作 happen-before
随后通过另一线程从 CopyOnWriteArrayList 中访问或移除该元素的操作.

这个类和ArrayList最大的区别就是add(E) 的时候。容器会自动copy一份出来然后再尾部add(E)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
   * Appends the specified element to the end of this list.
   *
   * @param e element to be appended to this list
   * @return <tt>true</tt> (as specified by {@link Collection#add})
   */
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();
  }
}

CopyOnWriteArraySet

对其所有操作使用内部 CopyOnWriteArrayList 的 Set. 因此, 它共享以下相同的基本属性：

它最适合于具有以下特征的应用程序：

  • set 大小通常保持很小, 只读操作远多于可变操作, 需要在遍历期间防止线程间的冲突.
  • 它是线程安全的.
  • 因为通常需要复制整个基础数组, 所以可变操作（add、set 和 remove 等等）的开销很大.
  • 迭代器不支持可变 remove 操作.
  • 使用迭代器进行遍历的速度很快, 并且不会与其他线程发生冲突. 在构造迭代器时, 迭代器依赖于不变的数组快照.

示例用法

以下代码使用一个写时复制（copy-on-write）的 set, 以维护在状态更新时执行某项操作的一组 Handler 对象.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Handler { void handle(); ... }
class X {
   private final CopyOnWriteArraySet<Handler> handlers = new CopyOnWriteArraySet<Handler>();
   public void addHandler(Handler h) {
handlers.add(h);
   }
   private long internalState;
   private synchronized void changeState() {
internalState = ...;
   }
   public void update() {
changeState();
for (Handler handler : handlers)
    handler.handle();
   }
}

ConcurrentHashMap

//FIXME 重写介绍

实现原理

  1. 结构

c

  1. 详情请参考: 探索 ConcurrentHashMap 高并发性的实现机制的本地版

线程安全

Collections类中的静态方法

在 Collections类中有多个静态方法，它们可以获取通过同步方法封装非同步集合而得到的集合：

1
2
3
4
5
6
public static Collection synchronizedCollention(Collection c)
public static List synchronizedList(list l)
public static Map synchronizedMap(Map m)
public static Set synchronizedSet(Set s)
public static SortedMap synchronizedSortedMap(SortedMap sm)
public static SortedSet synchronizedSortedSet(SortedSet ss)

这些方法基本上返回具有同步集合方法版本的新类。比如，为了创建多线程安全且由ArrayList支持的List，可以使用如下代码：

1
List list = Collection.synchronizedList(new ArrayList());

注意，ArrayList实例马上封装起来，不存在对未同步化ArrayList的直接引用（即直接封装匿名实例）。这是一种最安全的途径。如果另一个线程要直接引用ArrayList实例，它可以执行非同步修改。

//FIXME 实现原理

CopyOnWrite机制

synchronized机制

ReteenLock机制

ConcurrentHashMap是个特例

异同点

Vector 和 ArrayList

  1. Vector是线程同步的, 所以它也是线程安全的, 而ArrayList是线程异步的, 是不安全的. 如果不考虑到线程的安全因素, 一般用ArrayList效率比较高.
  2. 如果集合中的元素的数目大于目前集合数组的长度时, Vector增长率为目前数组长度的100%, 而ArrayList增长率为目前数组长度的50%. 如果在集合中使用数据量比较大的数据, 用Vector有一定的优势.
  3. 如果查找一个指定位置的数据, Vector和ArrayList使用的时间是相同的, 都是O(1),这个时候使用Vector和ArrayList都可以; 而如果移动一个指定位置的数据花费的时间为O(n-i) n为总长度, 这个时候就应该考虑到使用LinkedList, 因为它移动一个指定位置的数据所花费的时间为O(1), 而查询一个指定位置的数据时花费的时间为O(i).

Arraylist和LinkedList

  1. ArrayList是实现了基于动态数组的数据结构, LinkedList基于链表的数据结构.
  2. 对于随机访问get和set, ArrayList优于LinkedList, 因为LinkedList要移动指针.
  3. 对于新增和删除操作add和remove, LinkedList比较占优势, 因为ArrayList要移动数据.
    这一点要看实际情况的. 若只对单条数据插入或删除, ArrayList的速度反而优于LinkedList. 但若是批量随机的插入删除数据, LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据, 要移动插入点及之后的所有数据.

HashMap 与 TreeMap

  1. HashMap通过hashcode对其内容进行快速查找, 而TreeMap中所有的元素都保持着某种固定的顺序,
    如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）.
  2. 在Map 中插入、删除和定位元素, HashMap 是最好的选择. 但如果您要按自然顺序或自定义顺序遍历键, 那么TreeMap会更好.
    使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现. 这个TreeMap没有调优选项, 因为该树总处于平衡状态.

HashMap与HashTable的区别

  1. 继承不同
    public class Hashtable extends Dictionary implements Map
    public class HashMap extends AbstractMap implements Map
  2. Hashtable 中的方法是同步的, 而HashMap中的方法在缺省情况下是非同步的. 在多线程并发的环境下, 可以直接使用Hashtable, 但是要使用HashMap的话就要自己增加同步处理了.
  3. Hashtable中, key和value都不允许出现null值, 在HashMap中, null可以作为键, 这样的键只有一个; 可以有一个或多个键所对应的值为null. 当get()方法返回null值时, 即可以表示 HashMap中没有该键,也可以表示该键所对应的值为null. 因此, 在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断.
  4. 两个遍历方式的内部实现上不同.
    Hashtable、HashMap都使用了 Iterator. 而由于历史原因, Hashtable还使用了Enumeration的方式 .
  5. 哈希值的使用不同, HashTable直接使用对象的hashCode. 而HashMap重新计算hash值.
  6. Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式. HashTable中hash数组默认大小是11, 增加的方式是 old*2+1. HashMap中hash数组的默认大小是16, 而且一定是2的指数

对集合的选择

对List的选择

  1. 对于随机查询与迭代遍历操作, 数组比所有的容器都要快. 所以在随机访问中一般使用ArrayList
  2. LinkedList使用双向链表对元素的增加和删除提供了非常好的支持, 而ArrayList执行增加和删除元素需要进行元素位移.
  3. 对于Vector而已, 我们一般都是避免使用.
  4. 将ArrayList当做首选, 毕竟对于集合元素而已我们都是进行遍历, 只有当程序的性能因为List的频繁插入和删除而降低时, 再考虑LinkedList.

对Set的选择

  1. HashSet由于使用HashCode实现, 所以在某种程度上来说它的性能永远比TreeSet要好, 尤其是进行增加和查找操作.
  2. 虽然TreeSet没有HashSet性能好, 但是由于它可以维持元素的排序, 所以它还是存在用武之地的.

对Map的选择

  1. HashMap与HashSet同样, 支持快速查询. 虽然HashTable的速度也不慢, 但是在HashMap面前还是稍微慢了些, 所以HashMap在查询方面可以取代HashTable.
  2. 由于TreeMap需要维持内部元素的顺序, 所以它通常要比HashMap和HashTable慢.

用法

数组

数组复制System.arrayCopy

该方法是个JNI函数, 是在JVM中实现的

1
2
3
4
5
6
7
8
9
/**
*从src的srcPos位置复制数据到dest的destPos位置, 长度为length
*src - 源数组.
*srcPos - 源数组中的起始位置.
*dest - 目标数组.
*destPos - 目标数据中的起始位置.
*length - 要复制的数组元素的数量.
*/
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

Arrays.copyOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 由U类型复制为T类型？
* original - 要复制的数组
* newLength - 要返回的副本的长度
* newType - 要返回的副本的类型
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
  T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
  System.arraycopy(original, 0, copy, 0,
 Math.min(original.length, newLength));
  return copy;
    }
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

Arrays.asList: 将数组转换为ArrayList

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

Arrays.asList返回的ArrayList并不是java.util.ArrayList, 只是Arrays的内部类. 该类只提供了一些基本的操作,

  1. size：元素数量
  2. toArray：转换为数组, 实现了数组的浅拷贝.
  3. get：获得指定元素.
  4. contains：是否包含某元素.
    asList返回的是一个长度不可变的列表. 数组是多长, 转换成的列表是多长, 我们是无法通过add、remove来增加或者减少其长度的
    我们经常需要使用到Arrays这个工具的asList()方法将其转换成列表. 方便是方便, 但是有时候会出现莫名其妙的问题. 如下：
1
2
3
4
5
public static void main(String[] args) {
  int[] datas = new int[]{1,2,3,4,5};
  List list = Arrays.asList(datas);
  System.out.println(list.size());
    }

输出结果:

1
1

结果是1, 为什么会是1而不是5呢？先注意这个参数: T…a, 这个参数是一个泛型的变长参数, 我们知道 基本数据类型是不可能泛型化的 ,也就是说8个基本数据类型是不可作为泛型参数的, 但是为什么编译器没有报错呢？这是因为数组会当做一个对象来处理, 它是可以泛型的, 所以我们的程序是把一个int型的数组作为了T的类型,所以在转换之后List中就只会存在一个类型为int数组的元素了.
所以我们这样的程序System.out.println(datas.equals(list.get(0)));输出结果肯定是true.
当然如果将int改为Integer, 则长度就会变成5了.

Arrays.fill

使用值填充数组

1
2
3
int[] a=new int[10];
Arrays.fill(a,0);
// 使用0填充数组a

遍历

Map的遍历

Map的遍历,都是需要转换为Collection

1
Map<String, String> map = ...;

  1. 由Map生成Collection, 获取所有的值

    1
    2
    3
    4
    5
    Collection<String> values = map.values();
    Iterator<String> iterator = values.iterator();
    while (iterator.hasNext()) {
    	System.out.println(iterator.next());
    }

  2. 由Map.keySet, 遍历key值

    1
    2
    Set<String> keySet = map.keySet();
    Iterator<String> keyIterator = keySet.iterator();

  3. 获取Map.Entry类型的Set

    1
    2
    3
    4
    5
    6
    7
    8
    Set<Map.Entry<String, String>> entrySet = map.entrySet();
    Iterator<Map.Entry<String, String>> entryIterator = entrySet.iterator();
    while (entryIterator.hasNext()) {
    	Map.Entry<String, String> entry = entryIterator.next();
    	String key = entry.getKey();
    	String value = entry.getValue();
    	System.out.println(key + "\t" + value);
    }

Collection的遍历方法

  1. Iterator 迭代子

    1
    2
    3
    4
    5
    Collection<String> values2 = map.values();
    Iterator<String> iterator2 = values2.iterator();
    while (iterator2.hasNext()) {
    	System.out.println(iterator.next());
    }

  2. foreach

    1
    2
    3
    for (String valueItem : values2) {
    	System.out.println(valueItem);
    }

  3. List特有的遍历方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    List<String> list = null;
    assert list != null;
    for (int i = 0; i < list.size(); i++) {
    	System.out.println(list.get(i));
    }
    // 当然也可以写成
    for (String aList : list) {
    	System.out.println(aList);
    }

List遍历方式有三种:

- 下标遍历
- Iterator遍历
- Foreach遍历（最快）

排序

FIXME 排序：集合自带排序 对集合排序

其他

Java中有多少种数据结构, 分别是什么？

- List：是列表, 有下标值, 存储元素可以重复, 遍历元素是有序的.
- Set：是散列集, 无下标值, 存储元素不可重复, 遍历元素时无序的.
- Map：是以键值对存储, 一个key一个value, key不可以重复, value可以重复.
- 数组：指定类型, 固定长度, 元素存储地址是连续的.
- 树：元素以树形结构存储, 只有一个根节点.
- 栈：元素是先进后出, 后进先出.
- 向量：动态数组, 可以存储任何类型元素, 动态长度, 元素存储地址是连续的.
- 队列：元素存储是排列有序的, 一定保证先进的先出, 后进的后出.

修改记录:

  1. HashMap的详细实现原理 重写ConcurrentHashMap介绍 2016-08-20

参考文献:

  1. java提高篇（二十）集合大家族
  2. Java集合类详解
  3. 探索 ConcurrentHashMap 高并发性的实现机制