HashMap

根据key获取哈希桶数组索引位置

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

扩容过程

1.初始化一个新的Entry数组，2.将数据转移到新的Entry数组里，3.HashMap的table属性引用新的Entry数组，4.修改阈值

JDK1.7扩容需要重新计算hash，jdk1.8做了优化，不需要重新计算（因为扩容都是＊2，n－1就是在最高位变为1，只需要判断最高位是否为1就行）。

put方法的详细执行

HashMap JDK1.7和1.8区别

jdk1.8在扩容的新数组位置计算上做了优化，扩容都是＊2，在二进制最高位变为1，所以只需要判断原来数组的最高位是否为1，为0九继续保持原坐标，避免了像1.7那样重新计算所有key的hash值的新数组坐标。

jdk1.8引入了红黑树，在key分布极不均匀情况下查询性能极大的提升，从o(n)提升到了o(lg(n)).

jdk1.8优化了hash算法提高性能减少hash冲突，计算hash值的时候，1.7用了9次扰动处理=4次位运算+5次异或，1.8只用了2次扰动处理=1次位运算+1次异或。

JDK1.7先进行扩容后进行插入，而在JDK1.8的时候则是先插入后进行扩容，提升了性能，减少不必要的开销。

发生冲突时，jdk1.7使用链地址法＋头插法，jdk1.8使用链地址法＋尾插法（>8使用红黑树）

Jdk1.8为何引入了红黑树

元素较少时使用链表性能更好，因为红黑树需要进行左旋，右旋操作， 而单链表不需要。

HashMap使用优化

(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

ConcurrentHashMap的底层原理

HashMap在高并发下会出现链表环，从而导致程序出现死循环。高并发下避免 HashMap 出问题的方法有两种，一是使用 HashTable，二是使用 Collections.syncronizedMap。但是这两种方法的性能都能差。因为这两个在执行读写操作时都是将整个集合加锁，导致多个线程无法同时读写集合。高并发下的 HashMap 出现的问题就需要 ConcurrentHashMap 来解决了。

jdk1.7，ConcurrentHashMap使用Segment分段锁技术，每一个 Segment 就好比一个自治区，读写操作高度自治，Segment 之间互不影响。

任何读操作都可以不用锁判断，不同Segment间的写操作也可以并发，只有同一Segment下的写操作才需要锁判断。

调用 Size() 是统计 ConcurrentHashMap 的总元素数量，需要把各个 Segment 内部的元素数量汇总起来。但是，如果在统计 Segment 元素数量的过程中，已统计过的 Segment 瞬间插入新的元素则会把各Segment加锁进行重新统计。这种思想和乐观锁悲观锁思想如出一辙，先假设 Size 过程中不会有修改，如果有修改进行悲观锁操作。

参考文章：https://www.jianshu.com/p/78989cd553b4

ConcurrentHashMap 1.7和1.8的区别

1.整体结构

1.7：Segment + HashEntry + CAS

1.8: 移除 Segment，使锁的粒度更小，Synchronized + CAS + Node

2.put操作

1.7：先定位 Segment，再定位桶，put 全程加锁，没有获取锁的线程提前找桶的位置，并最多自旋 64 次获取锁，超过则挂起。

1.8：由于移除了 Segment，类似HashMap，可以直接定位到桶，拿到 first 节点后进行判断：①为空则CAS插入；②为 -1 则说明在扩容，则跟着一起扩容；③ else 则加锁 put(类似1.7)

3.get操作

基本类似，由于 value 声明为volatile，保证了修改的可见性，因此不需要加锁。

4.resize操作

1.7：跟HashMap步骤一样，只不过是搬到单线程中执行，避免了HashMap在 1.7 中扩容时死循环的问题，保证线程安全。

1.8：支持并发扩容，HashMap扩容在1.8中由头插改为尾插(为了避免死循环问题)，ConcurrentHashmap 也是，迁移也是从尾部开始，扩容前在桶的头部放置一个 hash 值为 -1 的节点，这样别的线程访问时就能判断是否该桶已经被其他线程处理过了。

5.size操作

1.7：很经典的思路：计算两次，如果不变则返回计算结果，若不一致，则锁住所有的 Segment 求和。

1.8：用 baseCount 来存储当前的节点个数，这就设计到 baseCount 并发环境下修改的问题。

linkedHashmap

LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。

HashMap无序；LinkedHashMap有序，可分为插入顺序和访问顺序两种。

LinkedHashMap存取数据，还是跟HashMap一样使用的Entry[]的方式，双向链表只是为了保证顺序。

LinkedHashMap是线程不安全的。

linkedHashmap在Android中的应用

在Android中使用图片时，一般会用LruCacha做图片的内存缓存，它里面就是使用LinkedHashMap来实现存储的。

树

在非线性结构里面，树是非常非常重要的一种数据结构。基于其本身的结构优势，尤其在查找领域，应用广泛，其中又以二叉树最为重要。树的话我们这里只重点说一下二叉树。

二叉搜索树

二叉搜索树又叫二叉查找树，又叫二叉排序树。性质如下：(1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3) 左、右子树也分别为二叉排序树；(4) 没有键值相等的结点。

平衡二叉树

平衡二叉树又叫AVL树。性质如下：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

红黑树

类似与平衡二叉树的一种实现，通过改变元素节点时通过左旋和右旋操作达到平衡二叉树。

红黑树是有序的。红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)。Java集合中的TreeSet和TreeMap，Linux虚拟内存的管理，都是通过红黑树去实现的。

红黑树和平衡二叉树（AVL树）比较

红黑树的查询性能略微逊色于AVL树，因为其比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

hash表和红黑树比较

红黑树是有序的，Hash是无序的，根据需求来选择。

红黑树占用的内存更小（仅需要为其存在的节点分配内存），而Hash事先就应该分配足够的内存存储散列表（即使有些槽可能遭弃用）。

红黑树查找和删除的时间复杂度都是O(logn)，Hash查找和删除的时间复杂度都是O(1)。

B树