Java笔记之 3. 数据结构

通常学习的数据结构分为：表、栈、队列、集合、哈希、树、图。

Java对其中一部分有自己的实现。

表：线性表ArrayList，链表LinkedList，线程安全Vector。

集合：Set、SortedSet、HashSet、TreeSet。

哈希：Map、HashMap、TreeMap、Hashtable、SortedMap、LinkedHashMap。

栈：线性栈Stack

队列：Queue、Deque

主要的顶层接口：

• List：是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引来访问List中的元素，第一个元素的索引为 0，允许有相同的元素。
• Set：与 Collection 完全一样的接口，只是行为上不同， 不保存重复的元素
• Queue：一个队列就是一个先入先出（FIFO）的数据结构
• Deque：
• Map：将唯一的键映射到值。

一、List：

继承关系：

image

主要实现类功能：

• ArrayList：线性表，非线程安全。采用可增长数组实现，增长当前长度的50%有利于节约内存空间。随机访问快，中间插入和删除慢。迭代器：ListIterator。

add：前端O(N2)，后端：都O(1)
get： O(1)
remove：O(N2)
for循环：O(N)(循环的N次)

• LinkedList：双链表，非线程安全。采用保存前后节点的引用实现。前后端插入速度快，中间查找慢。迭代器：LLSpliterator

add：前端LinkedList - O(1), 后端：O(1)
get： O(N)
remove：LinkedList - O(N),
for循环：O(N2)(循环N次，getN次)

• CopyOnWriteArrayList:线程安全的ArrayList。所有可变操作（add、set等等）都是通过对底层数组进行一次新的复制来实现的，并且使用ReentrantLock保证同时只能有一个线程操作。

使用了一种叫写时复制的方法，当有新元素添加到CopyOnWriteArrayList时，先从原有的数组中拷贝一份出来，然后在新的数组做写操作，写完之后，再将原来的数组引用指向到新数组。整个add操作都是在锁的保护下进行的。
这样做是为了避免在多线程并发add的时候，复制出多个副本出来,把数据搞乱了，导致最终的数组数据不是我们期望的。

• Vector：线程安全。采用可增长数组实现。默认扩容方式为原来的2倍。

ArrayList & LinkedList & Vector

1. ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
2. Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
3. LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用

二、Set

集成关系：

image

• HashSet：
  不允许出现重复元素，不保证集合中元素的顺序，允许包含值为null的元素，但最多只能一个。

• LinkedHashSet：
  不允许出现重复元素，具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现。

• TreeSet
  不允许出现重复元素，可以实现排序等功能。

• ConcurrentSkipListSet：
  提供的功能类似于TreeSet，能够并发的访问有序的set。基于“跳跃列表（skip list）”实现，只要多个线程没有同时修改集合的同一个部分，那么在正常读、写集合的操作中不会出现竞争现象。

• CopyOnWriteArraySet：

HashSet & TreeSet

1. TreeSet 是二差树实现的,Treeset中的数据是自动排好序的，不允许放入null值。
2. HashSet 是哈希表实现的,HashSet中的数据是无序的，只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
3. HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。

二、队列

继承关系：

image

非阻塞队列：

• ConcurrentLinkedQueue：是基于链接节点的、线程安全的无界非阻塞队列。采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。

阻塞队列：BlockingQueue

接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。
五个队列所提供的各有不同：

• ArrayBlockingQueue ：一个由数组支持的有界队列。通过将ReentrantLock设置为true来 达到公平性：即等待时间最长的线程会先操作。

• LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。

• PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。元素按优先级顺序被移除。

• DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。（基于PriorityQueue来实现，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。

• SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

• LinkedTransferQueue：基于链表的FIFO无界阻塞队列。
  采用一种预占模式，有就直接拿走，没有就占着这个位置直到拿到或者超时或者中断。即消费者线程到队列中取元素时，如果发现队列为空，则会生成一个null节点，然后park住等待生产者。后面如果生产者线程入队时发现有一个null元素节点，这时生产者就不会入列了，直接将元素填充到该节点上，唤醒该节点的线程，被唤醒的消费者线程拿东西走人。

双向队列Deque

image

三、哈希Map

继承关系：

image

主要的实现有：HashMap、TreeMap、LinkedHashMap、Hashtable

• HashMap：散列表，非线程安全
  根据键的HashCode值存储数据，具有很快的访问速度，最多允许一条记录的键为null，不支持线程同步。

• Hashtable：线程安全的散列表
  是 Dictionary(字典) 类的子类，synchronized修饰所有的操作，已被ConcurrentHashMap代替。

• ConcurrentHashMap：线程安全
  采用了分段锁的设计，只有在同一个分段内才存在竞态关系，不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计，分段锁大大的提高了高并发环境下的处理能力。但同时，由于不是对整个Map加锁，导致一些需要扫描整个Map的方法（如size(), containsValue()）需要使用特殊的实现

• TreeMap：基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

• LinkedHashMap：所有Entry节点链入一个双向链表的HashMap。继承于HashMap，使用元素的自然顺序对元素进行排序.

• WeakHashMap：弱引用map
  当某个键不再正常使用时，会被从WeakHashMap中被自动移除。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。某个键被终止时，它对应的键值对也就从映射中有效地移除了。

Hashtable & HashMap

Hashtable和HashMap它们的性能方面的比较类似 Vector和ArrayList，比如Hashtable的方法是同步的,而HashMap的不是。

最后：合理配置集合类的初始大小

在Java集合框架中的大部分类的大小是可以随着元素个数的增加而相应的增加的，我们似乎不用关心它的初始大小,但如果我们考虑类的性能问题时,就一定要考虑尽可能地设置好集合对象的初始大小,这将大大提高代码的性能。

比如,Hashtable缺省的初始大小为101,载入因子为0.75,即如果其中的元素个数超过75个,它就必须增加大小并重新组织元素，所以,如果你知道在创建一个新的Hashtable对象时就知道元素的确切数目如为110,那么,就应将其初始大小设为110/0.75=148,这样,就可以避免重新组织内存并增加大小