# 数据结构

# Java集合继承关系图

Java集合继承关系图

# 预备知识

# 时空复杂度

# 红黑树

//todo

左边节点比父节点小，右边节点比父节点大的数据结构。时间复杂度为logn。

# 哈希算法

# 二分查找算法

# 与运算

两个二进制数的每一位进行计算，得出一个新的二进制数。相同的位之间，如果都是1则得出1，其余情况得0，如1001与1011得出1001。

# 取反运算

# 运算求余原理

与运算对n求余（输入数 & n-1）必须是2的次幂。这样得出来的二进制就是10，100，1000这样第一位为1，其余为0的二进制数。n-1得出来的就是第一位为0，其他位都是1的01，011，0111这样二进制数。输入任意数与n-1进行与运算，如n为4，那二进制就是100，n-1的二进制就是11，得出来来的结果就在11-00之间，也就是十进制的3-0之间。

# 为什么用「与运算」代替「求模运算」

因为位运算比求模运算效率高，求模运算要转换成位运算。字节码是操作符和操作值进行计算。

# 一个Java对象占用多大内存

一个引用对象的内存大小由三部分组成。

对象头数据

包括三部分
- 运行时数据：存储运行时数据， HashCode、锁状态标志、GC分代年龄等。在64位操作系统下，占8字节。32位系统下占4字节。
- 指针：对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪一个类的实例。在开启指针压缩的状况下占 4 字节，未开启状况下占 8 字节。
- 数组长度：部分只有是数组对象才有，若是是非数组对象就没这部分。这部分占 4 字节。
对象实际数据

是基础类型就是基础类型所占大小，是引用类型就按本方法计算。
对齐填充数据

如果得出的结果不是8的倍数，填充到8的倍数。因为cpu CPU 进行内存访问时，一次寻址的指针大小是 8 字节。如果不出现对齐，会出现缓存行污染。影响程序执行效率。

举例：

在64位操作系统未开启指针压缩的情况下，这个数组User[] users = new User[3];所占的内存大小是多少

public class User{
    private int age;
    private int classNum;
}

一个User的大小是：

运行时数据) + 指针数据） +数组长度 + age和className内存大小 + 对齐填充数据

8 + 8+ 4 + 8 + 4= 32；

数组占用内存大小是： 32*3 = 96;

# 相关伪代码(便于直观理解)

# SpareArray删除元素

public void delete(int key) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            mGarbage = true;
        }
    }
}

# List

# ArrayList结构和原理

**结构：**ArrayList是一个基于数组结构的容器。它的内部维护了一个Object类型的数组，这个数组的初始化大小是0，添加数据时，默认大小是10，这个大小可以通过初始化的时候指定。
**扩容：**当当前数组已经被存满时，会触发自动扩容机制。扩容大小为当前大小的1.5倍。1.5倍是一个合理的扩容大小，既不会太大也不会太小。具体的扩容逻辑在grow函数中，在这个函数中，会新建一个当前数组1.5倍大小的新数组，然后调用Arrays.copyOf函数把旧数据拷贝到新数组中。
**读写原理：**数组的大小是固定的，数据存储在一块连续的内存空间上。数组的变量记录的是数组中第一个元素的内存地址，起始元素的内存地址 + 下标位置 * 单元素内存大小，就是每一个元素的内存地址。所以通过下标就能直接获取到每个元素的内存地址，对这块内存地址读写来修改每个元素的值。
**增删原理：**数组结构要进行增删时比较耗时的，因为增加一个元素，就需要调用System.arraycopy函数，通过遍历的方式把当前新增位置后的元素都后移一位，生成一个新数组。删除也是同理，把删除位置后面的值都前移一位。
**反复增删怎么优化：**参考Sparry实现。
**和Vector的区别：**Vector线程安全，可以设置增长因子。

# LinkedList结构和原理

**结构：**LinkedList是一个链表结构的容器。链表结构就是每一个节点中都有上一个节点或者下一个节点这样的一个属性。只有上个节点或者下个节点叫单链表，有上下节点叫双链表，LinkedList是双链表。链表结构是不需要指定大小的，所以也并不需要扩容。
读写原理：在LinkedList中无法通过下标就获取到元素，必须通过遍历的方式才能找到元素。在具体实现中，会先通过下标来判断从头遍历还是从尾遍历，提升查找效率。
**增删原理：**通过以上方式找到元素之后，新建一个节点把前后的两个节点赋值为这个节点前后几点就完成了新增。删除也是一样，找到元素之后，修改前一个元素的下一个节点为下下个元素，这样就把自身这个节点从链中删除了。

# ArrayList对比LinkedList

ArrayList基于数组结构，LinkedList基于链表结构。
查改ArrayList快，增删LinkedList快。
ArrayList需要扩容，LinkedList不需要。

# HashMap

# HashMap结构和原理

**结构：**数组➕单链表结构（可以很形象的理解成烤新疆羊肉串）
**原理：**key的hashCode通过求模运算得出数组的下标
**put原理：**找出下标的链表数据，遍历，如果hashCode相同，值相同，则替换，否则新增。
**怎么解决哈希冲突：**不同的key计算得出的hashCode一致就是哈希冲突。在HashMap中，是通过链表结构来处理哈希冲突的，在哈希冲突的情况下，会通过尾插的方式把当前的元素插入到当前下标的链表结构中。
**二次幂：**为什么HashMap的大小是2次幂，因为上面的求模运算是通过位运算符来计算，总大小必须要是2次幂计算结果才能全匹配到每一个下标值
- **扩容：**当当前HashMap的数组大小已经被用了75%的时候，会扩容一个二次幂的大小，也就是翻一倍。扩容的同时，要把原来已经存储的数据进行移位，也是重新计算存储位置后改变存储位置。因为原来的数组下标是通过key的hashCode对原来数组大小求模得出的，现在数组大小变了，在通过key获取时，计算得出数组下标就与之前不一致了。
**是否可序列化：**不可以。因为hashCode在不同的系统中得出的结果不一样，因此经过系列化之后的数据，并不能通过key获取到正确的值。
**优化：**因每次扩容都需要对已存储数据进行移位，这个步骤非常耗时。从这个点优化，可以在初始化HashMap的时候给定一个大小值，这个大小值接近你要存储数据的大小（存储数据大小/0.75 + 1）。这样就能避免扩容带来的耗时操作。
**缺点：**在java1.7的HashMap设计中是非线程安全的，并且链表结构的查询，修改数据效率慢（因为要遍历链表才能获取数据）。
**1.7和1.8的不同：**1.8加入红黑树和线程安全，链表元素超过8个时将链表转换为红黑树。
**对比HashTable的区别：**HashTable在HashMap的基础上增加了线程安全，每一个函数都加了锁。
**对比ConcurrentMap区别：**ConcurrentMap和HashTable一样也是在HashMap的基础上增加了线程安全。不过currenthashmap只对链表操作加了锁，保证多个线程同时操作一个链表数据一致性。
**对比LinkedHashMap区别：**LinkedHashMap继承自HashMap，在HashMap基础上加了一层链表，实现数据的有序。主要是重写了createEntry方法，在这个方法中，实现了链表结构。
**对比TreeMap：**继承SortedMap，红黑树实现，时间复杂度是O(logn)
**对比WeakHashMap：**结构和HashMap一样数组＋链表。继承WeakHashMap，持有key的弱引用，key不再被外部强引用持有时，会被自动清理。

# SpareArray

**结构：**SpareArray是一个双数组结构的容器。一个int类型的数组存储key，一个object类型的数组存储value。通过二分查找来获取元素。
**删除原理：**SpareArry在删除时，并不删除这个key和value，而是把这个key对应的value赋值为一个object类型的Delete变量用来标识这个元素已经被删除。
**新增原理：**在新增元素时，通过二分查找法查找找到则返回下标，用这个下标插入值。找不到则返回最佳的插入位置，插入之后和ArrayList一样调用System.arraycopy后移这个位置后面的元素。
**对比HashMap:**占用内存小。用int类型的数组来存储key比HashMap的Object类型占用内存小。value为object类型的数组比HashMap的链表占用内存小。

# Set

**HashSet：**内部是一个HashMap，通过HashMap的key唯一的特点来实现。
LinkedHashSet：继承自HashSet，内部是LinkedHash，通过LinkedHash的特点实现了有序。
**TreeSet：**基于TSortedMap实现，

# List、Set、Map的区别

List：有序、可重复；索引查询速度快；插入、删除伴随数据移动，速度慢，非线程安全；
Set：无序，不可重复，非线程安全；
Map：键值对，键唯一，值多个，HashTable和ConcurrentMap线程安全；

参考资料

问题

List、Set、Map的区别
ArrayList和LinkedList区别
ArrayList的扩容
HashMap实现原理
如何解决HashMap碰撞
HashMap和HashTable的区别
LinkedHashMap实现原理
SparseArray原理
HashMap与SparseArray区别
时空复杂度