1. Java中最原始的数据结构

Java底层最原始的数据结构就两种：

1. 数组：数组是底层汇编语言实现的一种数据结构，几乎任何语言都支持。其物理内存地址连续，俗称有序数组（无序数组实际上也是有序数组，只不过数组元素下标由程序自己控制）。
2. 链表：链表是jdk底层自己实现的，其物理内存地址不连续，是散列存储的（参考LinkedList链表的底层实现）；链表分为单向链表、双向链表、单向循环链表、双向循环链表。
   tips：像基本类型这种点性结构就不用说了，任何语言默认就是点性结构，即一个萝卜一个坑。

2. 各个集合框架的次鞥数据结构、默认大小和负载因子

2.1 Vector类

1. 底层数据结构是有序数组，存储时物理内存地址连续。
2. 默认大小是10，在实例化数组对象时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。
3. 负载因子是1，即当元素个数（指的是容器中的元素个数，即bucket数组的元素个数）超过数组指定大小（默认为10）时，进行数组扩容，扩容增量为原数组的一倍。
4. 数组扩容的方式是重新开辟连续内存空间的数组，然后将之前的数组内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. 举例：比如Vector类的初始化大小设置为20，当实际存储的元素个数超过20个时，进行数组扩容，扩容后的新数组大小为40。

2.2 ArrayList类

1. 底层数据结构是有序数组，存储时物理内存地址连续。
2. 默认大小是10，在实例化数组对象时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。
3. 负载因子是1，即当元素个数（指的是容器中的元素个数，即bucket数组的元素个数）超过数组指定大小（默认为10）时，进行数组扩容，扩容增量为原数组的0.5倍+1。
4. 数组扩容的方式是重新开辟连续内存空间的数组，然后将之前的数组内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. 举例：比如ArrayList的初始容量设置为20，当实际存储的元素个数超过20个时，进行数组扩容，扩容后是31。

2.3 LinkedList类

1. 底层数据结构是双向循环链表，物理内存地址不连续，物理位置散列存储。链表不需要初始化大小，也不牵扯数组复制和扩容。只要内存足够，可以基于链表结构无限存储数据。
2. 因为LinkedList要实现一种队列的结构，能够先进先出，而且要操作队列头和队列尾，所以必须采用双向循环链表，单向循环链表不能实现。
3. 链表是类似数组的数据结构，只不过数组是内存地址连续的一块空间，而且大小是预定初始化好的，即大小固定，在使用过程中可能需要动态扩容；而链表结构是散列的存储结构，内存空间不连续，可以无限插入数据。
4. 链表结构只要内存允许，可以无限存储数据，充当容器使用，而且链表这种数据结构很强大，消息队列等大型中间件都是使用链表为基础数据结构的。因为链表结果适合频繁插入和频繁删除的集合操作。

2.4 HashSet类

1. 底层数据结构是无序数组+单向链表，无序数组的下标依赖元素对象的“hashCode%数组初始化大小”获得（实际上hashSet计算数组下标的方式更复杂）。
2. 默认大小是16，在初始化时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。
3. 负载因子是0.75，即当元素个数（指的是容器中的元素个数，即size；对于set而言这不是bucket数组的元素个数，而是set本身存储的元素个数，因为set元素个数有可能大于bucket数组的元素个数，因为bucket数组的每一个元素是一个链表，而链表可能存储多个元素）超过数组大小的0.75倍时，进行数组扩容，扩容增量为原数组的1倍。
4. 数组扩容方式是重新开辟连续内存空间的数组，然后将之前数组的内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. 举例：比如hashSet的容量为16，当实际存储的元素个数超出16的0.75倍即12个时，进行数组扩容，扩容后数组大小为32。

2.5 TreeSet类

1. 底层数据结构是无序数组+单向链表，无序数组的下标依赖元素对象的“hashCode%数组初始化大小”获得（实际上treeSet计算数组下标的方式更复杂）。
2. 默认大小是16，在初始化时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。
3. 负载因子是0.75，即当元素个数（指的是容器中的元素个数，即size；对于set而言这不是bucket数组的元素个数，而是set本身存储的元素个数，因为set元素个数有可能大于bucket数组的元素个数，因为bucket数组的每一个元素是一个链表，而链表可能存储多个元素）超过数组大小的0.75倍时，进行数组扩容，扩容增量为原数组的1倍。
4. 数组扩容方式是重新开辟连续内存空间的数组，然后将之前数组的内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. 举例：比如treeSet的容量为16，当实际存储的元素个数超出16的0.75倍即12个时，进行数组扩容，扩容后数组大小为32。

2.6 HashMap类

1. 底层数据结构是无序数组+单向链表，无序数组的下标依赖元素对象的“hashCode%数组初始化大小”获得（实际上hashMap计算数组下标的方式更复杂）。
2. 默认大小是16，在初始化时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。tips：为啥是16？因为16是2的4次方，可以增加查询效率。
3. 负载因子是0.75，即当元素个数（指的是容器中的元素个数，即size；对于set而言这不是bucket数组的元素个数，而是set本身存储的元素个数，因为set元素个数有可能大于bucket数组的元素个数，因为bucket数组的每一个元素是一个链表，而链表可能存储多个元素）超过数组大小的0.75倍时，进行数组扩容，扩容增量为原数组的1倍。
4. 数组扩容方式是重新开辟连续内存空间的数组，然后将之前数组的内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. HashMap 的 value 可以为 null，并且可以有多个键的值都为 null。也就是说，HashMap 支持重复的 null 值。
6. 举例：比如hashMap的容量为16，当实际存储的元素个数超出16的0.75倍即12个时，进行数组扩容，扩容后数组大小为32。
   tips:集合初始化时推荐明确指定集合初始化大小值。尤其是针对HashMap，这样能有效避免hashMap频繁进行扩容操作，提升性能。
   建议初始化值大小计算方式如下：
   initialCapacity = (需要存储的元素个数/负载因子) + 1；
   注意负载因子默认为0.75。如果暂时无法确认需要存储的元素个数，请明确设置为默认值16。
   备注：jdk底层并不是直接采用我们设置的初始化容量大小来实例化hashMap的，而是经过计算，最终得到的总是一个比设置值大的2的幂。

2.7 HashTable类

1. 底层数据结构是无序数组+单向链表，无序数组的下标依赖元素对象的“hashCode%数组初始化大小”获得（实际上hashTable计算数组下标的方式更复杂）。
2. 默认大小是16，在初始化时可以指定数组初始化大小，人为指定后，数组大小就是指定的大小值。
3. 负载因子是0.75，即当元素个数（指的是容器中的元素个数，即size；对于set而言这不是bucket数组的元素个数，而是set本身存储的元素个数，因为set元素个数有可能大于bucket数组的元素个数，因为bucket数组的每一个元素是一个链表，而链表可能存储多个元素）超过数组大小的0.75倍时，进行数组扩容，扩容增量为原数组的1倍。
4. 数组扩容方式是重新开辟连续内存空间的数组，然后将之前数组的内容复制到容量比较大的新数组中，最后删除原来的数组（让其指向null值等待被gc回收）。
5. 举例：比如hashTable的容量为16，当实际存储的元素个数超出16的0.75倍即12个时，进行数组扩容，扩容后数组大小为32。