java队列 - queue Queue：一个队列就是一个先入先出（FIFO）的数据结构 Queue接口与List、Set同一级别，继承了Collection接口，LinkedList实现了Deque接口
非阻塞队列：ConcurrentLinkedQueue(无界线程安全)，采用CAS机制(compareAndSwapObject原子操作) 阻塞队列：ArrayBlockingQueue(有界)、LinkedBlockingQueue(无界)、DelayQueue、PriorityBlockingQueue，采用锁机制；使用ReentrantLock锁
不存入重复元素的规则，使用hashcode和equals 元素的哈希值通过元素的hashcode方法来获取，hashset首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals方法，如果equals结果为true，hashset就视为同一个元素，如果equals 为false就不是同一个元素 哈希值相同，但equals为false的元素如何存储，方法是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中），总结下就是哈希一样的存一列
1、元素自身具备比较性，元素需要实现Comparable接口，覆盖compareTo方法 2、容器具备比较性，当元素自身不具备比较性，或者元素自身具备的比较性不是所需的，只能让容器自身具备 定义一个类实现 Comparator接口，覆盖compare方法，并将该接口的子类对象作为参数传递给 TreeSet集合的构造函数 当Comparable和Comparator比较方式同时存在，以Comparator比较方式为主。 通过 return 0来判断唯一性
总结： 看到array，就要想到角标 看到link，就要想到first、last 看到hash，就要想到hashCode、equals 看到tree，就要想到两个接口，Comparable、Comparator
List分为3类：ArrayList、LinkedList和Vector 1、是按顺序查找 2、允许存储项为空 3、允许多个存储项的值相等
继承于Collection接口，除了Collection通用的方法以外，扩展了部分只属于List的方法
是一个数组实现的列表，由于数据是存入数组中的，和数组的特点一致，查询很快，查询返回数组下标对应的值即可，适用于多查找的场景，但中间部分的插入和删除很慢，
是ArrayList的线程安全版，方法前都加了synchronized锁，其它实现逻辑都相同，如果对线程安全要求不高的话，可以选择ArrayList，毕竟synchronized很耗性能。
由链表实现，插入和删除方便，适用于多次数据替换的场景，双向链表，LinkedList继承于AbstractSequentialList，和ArrayList一个套路，内部维护了3个成员变量，一个是当前链表的头节点，一个是尾部节点，还有链表长度
最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度，HashMap最多只允许一条记录的键为Null（多条会覆盖），允许多条记录的值为Null，非同步的
能够把它保存的记录根据键（key）排序，默认是按升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的，TreeMap不允许key的值为null，非同步的
保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，在遍历的时候会比HashMap慢，key和value均允许为空，非同步的
1、Stack是线程安全的 2、内部使用数组保存数据，不够时翻倍
栈是一种用于存储数据的简单数据结构，类似链表或者顺序表（俗称线性表），栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，把允许操作的一端称为栈顶（Top）,不可操作的一端称为栈底（Bottom）,同时把插入元素的操作称为入栈（Push），删除元素的操作称为出栈（Pop），若栈中没有任何元素，则称为空栈。
每个节点最多有两个叶子节点
二叉树由节点和边组成，节点分为根节点、父节点和子节点
红色是根节点（root），蓝色是子节点也是父节点，绿色是子节点，其余的线是边，节点和链表中的节点一样都可以存放数据信息，树中的边可以用自引用表示，这种引用就是c/c++里面的指针，通常来说树是顶部小，底部大，且树呈分层结构，root节点是第0层，以此类推，二叉树最多有两个节点。
二叉树搜索：二叉树一个节点左子节点的关键字小于这个节点，右子节点关键字大于或等于这个父节点。
查找关键字：在有序数组中通过二分排序效率非常高。
树的最值查找：从root开始查找，最小值只会出现所有父节点的左节点处，最大值只会出现在所有父节点的沿着右节点搜索的最底层右节点处。
叶节点只能出现在最下层和次下层，并且最小面一层的结点都集中在该层最左边的若干位置的二叉树。
一颗深度为k的有n个结点的二叉树，对树中的结点按从上至下，从左到右的顺序进行编号，如果编号为i（1<=i<=n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这颗二叉树称为完全二叉树。
左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。如果插入或者删除一个节点使的高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态，这个方案解决了二叉查找树退化成链表的问题，把插入、查找、删除的时间复杂度最好情况和最坏情况都维持在O(logN)，但频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree）
红黑树是在普通二叉树上，对每个结点添加一个颜色属性形成的
满足以下五条性质：
1、节点是红色或黑色：在树里面的节点不是红色的就是黑色的
2、根节点是黑色的
3、每个叶节点（NIL或空节点）是黑色
注：NIL节点是个空节点，并且是黑色的
4、每个红色节点的两个子节点都是黑色的（不存在两个连续的红色节点）
连续的两个节点不能是连续的红色，连续的两个节点是父节点与子节点不能是连续的红色
5、从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点
注：从根节点到每一个NIL节点的路径中，都包含了相同数量的黑色节点
总结：这五条性质约束了红黑树，可以通过数学证明来证明，满足这五条性质的二叉树可以将查找删除维持在对数时间内，当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。
MySQL是基于B+树聚集索引组织表 B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中； B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中； B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3;
优势： B-树是一种平衡的多路查找（又称排序）树，在文件系统中有所应用，主要用作文件的索引，B树必须用中序遍历的方法按序扫库； B+树方便扫库，直接从叶子结点挨个扫一遍就完了；支持range-query（区间查询）方便，而B树不方便
B树优势是当查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询 B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大（或最小）关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点，因此在B+树种，无论查找成功与否，都是走了一条从根到叶子节点的路径。 B树：是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，B树定义了非叶子结点关键字个数至少为（2/3）M,即块的最低使用率为2/3（代替B+树的1/2）,所以 B树分配新结点的概率比B+树要低，空间使用率更高。
LSM（Log-Structured Merge-Trees）和B+树相比，是牺牲了部分读的性能来换取写的性能（通过批量写入），实现读写之间的平衡，Hbase、LevelDB、Tair（Long DB）、nessDB采用LSM树的结构，LSM可以快速建立索引；
《LSM树 VS B+树》 B+ 树读性能好，但由于需要有序结构，当Key比较分散时，磁盘寻道频繁，造成写性能较差； LSM是将一个大树拆分成N棵小树，先写到内存（无寻道问题，性能高），在内存中构建一颗有序小树（有序树），随着小树越来越大，内存的小树会flush到磁盘上，当读时，由于不知道数据在哪些小树上，因此必须遍历（二分查找）所有的小树，但在每颗小树内部数据是有序的。
《LSM树存储引擎》 1、基于LSM树实现的HBase的写性能比MySQL高了一个数量级，读性能低了一个数量级； 2、优化方式：Bloom filter替代二分查找；compact小数未大树，提高查询性能； 3、Hbase中，内存中达到一定阈值后，整体flush到磁盘上、形成一个文件（B+树），HDFS不支持update操作，所以Hbase做整体flush而不是merge update，flush到磁盘上的小树，定期会合并成一个大树。
经常用于大规模数据的排重检查
《Java Bitset类》 一个Bitset类创建一种特殊类型的数组来保存位值，BitSet中数组大小会随需要增加，这和位向量（vector of bits）比较类似
《Java BitSet（位集）》 原理简介： Java平台的BitSet用于存放一个位序列，如果要高效的存放一个位序列，就可以使用位集(BitSet)。由于位集将位包装在字节里，所以使用位集比使用Boolean对象的List更加高效和更加节省存储空间。 BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，一次扩充64位，最终内部是由N个long来存储。 默认情况下，BitSet的所有位都是false即0。 在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。 一个1GB的空间，有8102410241024 = 8.5810^9bit，也就是1GB的空间可以表示85亿多个数。
应用场景： 1.统计一组大数据中没有出现过的数； 将这组数据映射到BitSet，然后遍历BitSet，对应位为0的数表示没有出现过的数据。 2.对大数据进行排序； 将数据映射到BitSet，遍历BitSet得到的就是有序数据。 3.在内存对大数据进行压缩存储等等。 一个GB的内存空间可以存储85亿多个数，可以有效实现数据的压缩存储，节省内存空间开销。
为什么BitSet使用long数组做内部存储？ JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。 从数据在栈上的存储来说，使用long和byte基本是没有什么差别的，除了编译器强制地址对齐的时候，使用byte最多会浪费7个字节(强制按照8的倍数做地址对其)，另外从内存读数组元素的时候，也是没有什么区别的，因为汇编指令有对不同长度数据的mov指令。所以说，JDK选择使用long数组作为BitSet的内部存储结构的根本原因就是在and和or的时候减少循环次数，提高性能。 例如我们进行BitSet中的and, or,xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。另外我们在查找bitset中下一个置为1的bit时,word首先会和0进行比较，如果word的值为0，则表示该word中没有为1的bit，可以忽略这个word，如果是long数组存储，可以一次跳过64个bit，如果是int数组存储时，一次只能跳过32个bit。