Java数据结构篇
Map体系
1.HashMap
- 哈希冲突：开放定址法、再哈希法、链地址法
- 插入元素先检查是否到达阈值，是则先数组扩容，然后再插入链表，链表长度超过8则转红黑树
- 1.7之前由于扩容导致的头插法尾插法混合导致指针错误，出现死循环问题
2.TreeMap
基于红黑树，增加了排序功能，默认使用Java自带排序规则，没有则需要实现Comparable接口（大于等于小于分别返回1，0，-1）
🌟下面是并发安全容器，HashTable和ConcurrentHashMap基于HashMap，而ConcurrentSkipListMap基于TreeMap
3.HashTable
在数据不断地写入和删除，且不存在数据量累积以及数据排序的场景下，我们可以选用Hashtable或ConcurrentHashMap。Hashtable使用Synchronized同步锁修饰了put、get、remove等方法，因此在高并发场景下，读写操作都会存在大量锁竞争，给系统带来性能开销。
4.ConcurrentHashMap
相比Hashtable，ConcurrentHashMap在保证线程安全的基础上兼具了更好的并发性能。在JDK1.7中，ConcurrentHashMap就使用了分段锁Segment减小了锁粒度，最终优化了锁的并发操作。到了JDK1.8，ConcurrentHashMap做了大量的改动，摒弃了Segment的概念。由于Synchronized锁在Java6之后的性能已经得到了很大的提升，所以在JDK1.8中，Java重新启用了Synchronized同步锁，通过Synchronized实现HashEntry作为锁粒度。这种改动将数据结构变得更加简单了，操作也更加清晰流畅。
与JDK1.7的put方法一样，JDK1.8在添加元素时，在没有哈希冲突的情况下，会使用CAS进行添加元素操作；如果有冲突，则通过Synchronized将链表锁定，再执行接下来的操作。因此按理说在性能上ConcurrentHashMap要好一些，通常为首选。但要注意一点，虽然ConcurrentHashMap的整体性能要优于Hashtable，但在某些场景中，ConcurrentHashMap依然不能代替Hashtable。例如，在强一致的场景中ConcurrentHashMap就不适用，原因是ConcurrentHashMap中的get、size等方法没有用到锁，ConcurrentHashMap是弱一致性的，因此有可能会导致某次读无法马上获取到写入的数据。
5.ConcurrentSkipListMap
ConcurrentHashMap容器，该容器在数据量比较大的时候，链表会转换为红黑树。红黑树在并发情况下，删除和插入过程中有个平衡的过程，会牵涉到大量节点，因此竞争锁资源的代价相对比较高。而跳跃表的操作针对局部，需要锁住的节点少，在并发场景下的性能会更好一些，因此就实现了在非线程安全的Map容器中，用TreeMap容器来存取大数据；在线程安全的Map容器中，用SkipListMap容器来存取大数据。
List体系
1.LinkedList
- 双向链表
- 内部属性
2.ArrayList
- 实现接口List，Clonable，Serializable，RandomAccess（空接口，仅用于标识）
- 从ArrayList属性来看，它没有被任何的多线程关键字修饰，但elementData被关键字transient修饰了。这就是我在上面提到的第一道测试题：transient关键字修饰该字段则表示该属性不会被序列化，但ArrayList其实是实现了序列化接口，这到底是怎么回事呢？
这还得从“ArrayList是基于数组实现“开始说起，由于ArrayList的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。 如果采用外部序列化法实现数组的序列化，会序列化整个数组。ArrayList为了避免这些没有存储数据的内存空间被序列化，内部提供了两个私有方法writeObject以及readObject来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。
因此使用transient修饰数组，是防止对象数组被其他外部方法序列化。
- 扩容策略，1.5倍+1，可以自行预估存储量指定初始容量，减少扩容次数，提高性能；
- 插入和删除中间节点需要重排列位置，直接末尾操作则不需要；
- 遍历过程中可以增加删除元素吗？可以使用iterator迭代器进行安全操作，hashmap同理；
3.vector
Vector也是基于Synchronized同步锁实现的线程安全，Synchronized关键字几乎修饰了所有对外暴露的方法，所以在读远大于写的操作场景中，Vector将会发生大量锁竞争，从而给系统带来性能开销。
4.CopyOnWriteArrayList
相比之下，CopyOnWriteArrayList是java.util.concurrent包提供的方法，它实现了读操作无锁，写操作则通过操作底层数组的新副本来实现，是一种读写分离的并发策略。我们可以通过以下图示来了解下CopyOnWriteArrayList的具体实现原理。
回到案例中，我们知道黑名单是一个读远大于写的操作业务，我们可以固定在某一个业务比较空闲的时间点来更新名单。
这种场景对写入数据的实时获取并没有要求，因此我们只需要保证最终能获取到写入数组中的用户ID就可以了，而CopyOnWriteArrayList这种并发数组容器无疑是最适合这类场景的了。
Set体系
1.HashSet
HashSet的contains方法原理：主要就是一个查找过程，底层基于HashMap实现，就是查找哈希桶位，然后再遍历链表（红黑树）查找是否有目标元素。需要注意两点：
- 重写equals（）方法，判断相等的核心依据；
- 重写hashcode（）方法，确保哈希性能；
2.TreeSet
同TreeMap，可自定义排序，红黑树，插入值非空（1.8之后）
二叉树
BST、AVL、红黑树、B树、B+树