<commit_before># data_structure
java数据结构基础

# Java中的Collections API主要包含两个独立的树形结构。Collection和Map
## Collection接口
![image](‪C:\Users\Adaministrator\Desktop\CollectionAPI.png)
### Queue

除了基本的Collection接口中定义的操作，还提供其他**插入**、**删除**、和**元素检查**等操作。**限定元素个数的称为<font color="red">有界队列</font>**。

```
public interface Queue<E> extends Collection<E>{
    // 元素检查
    E element();
    
    // 插入
    boolean offer(E e);
    
    // 元素检查
    E peek();
    
    // 移除
    E poll();
    
    // 移除
    E remove();
}
```
队列操作的两种方式：

| 队列操作 | 功能说明 | 异常情况 | 抛出异常的方法 | 返回特定值的方法 |
| --- | :---: | :---: | :---: | :---: |
| 插入 | 向队列中加入元素 | 有界队列已满 | add(e) | offer(e)，返回false |
| 移除 | 从队首移走一个元素 | 队列空 | remove() | poll()，返回null  |
| 元素检查 | 返回队首元素，但不删除该元素 | 队列空 | element() | peek()，返回null |


### Set
Set继承了**Collection**接口，方法全部从Collection继承，自身没有声明其他方法。

```
public interface Set<E> extends Collection<E>{
    // 基本操作
    // 返回集合中元素的数量，如果超过int型最大值Integer.MAX_VALUE，则仅返回最大值
    int size();
    
    // 集合中不包含任何元素就返回true
    boolean isEmpty();
    
    // 集合是否包含指定元素
    boolean contains(Object element);
    
    // 往集合里添加元素，添加成功返回true；集合不允许添加重复元素返回false；其他情况抛异常；能否添加null看具体实现规则
    boolean add(E element);
    
    // 移除一个或多个与指定的元素匹配的实例，成功返回true；其余抛出异常
    boolean remove(Object o);
    
    // 返回当前集合元素的迭代器iterator，无法保证有关的顺序
    Iterator<E> iterator();
    
    // 集合元素批量操作
    // 返回当前集合是否包含指定集合C的所有元素
    boolean containsAll(Collection<?> c);
    
    // 将指定集合C的元素都添加到当前集合，自己无法添加自己，成功true；不知何时返回false;其余抛异常，不支持的操作，空指针，类型转换，非法状态，不允许添加等
    boolean addAll(Collection<? extends E> c);
    
    // 从当前集合中去除指定集合中的所有元素，成功返回true；其余抛出异常，不支持的操作、类型转换、空指针等
    boolean removeAll(Collection<?> c);
    
    // 在当前集合中只保留属于C的元素，如果当前集合发生变化则返回true；其余抛出异常，不支持的操作、类型装还、空指针等
    boolean retainAll(Collection<?> c);
    
    // 清除集合中的所有元素
    void clear();
    
    // 数组操作
    // 返回包含当前集合所有元素的数组，保证元素的顺序（依据迭代器的顺序）
    Object[] toArray();
    
    // 返回包含当前集合所有元素的数组，所返回的数组的运行时类型是数组a的类型。保证元素的顺序（依据迭代器的顺序）；如果数组a能容下集合的所有元素，则将集合元素写入a并返回，否则创建类型与a相同、长度等于集合长度的数组
    <T> T[] toArray(T[] a);
}
```
JDK提供实现Set接口的3个实用类：***HashSet***、***TreeSet***、***LinkedHashSet***;
#### 1. HashSet
采用Hash表实现了Set接口（源码使用的是HashMap），一个HashSet对象中的元素存储在一个Hash表中，元素没有固定顺序；Hash表结构支持大数据量的访问，所以比线性列表快

#### 2. TreeSet
实现了SortedSet接口（源码中未发现，待研究），采用一种有序树的结构存储集合中的元素，TreeSet对象中的元素按照升序排序

#### 3. LinkedHashSet
实现了Set接口，采用Hash表和链表相结合的结构存储集合中的元素，元素具有固定的顺序，集中了HashSet与TreeSet的优点，即能保证顺序又能够具有较高的存取效率（待研究）

### List
List是一种有序集合，继承自Collection接口。除了Collection中的方法，List接口还增加如下操作：
- 按位置存取元素，按照元素在list中的序号对其进行操作
- 查找，在list中搜寻指定的对象并返回该对象的序号
- 遍历，使用ListIterator实现List的遍历
- 截取子List，建立List视图


```
public interface List<E> extends Collection<E>{
    // 按位置存取元素
    E get(int index);
    E set(int index, E element);
    Boolean add(E element);
    void add(int index, E element);
    E remove(int index);
    boolean addAll(int index, Collection<? extends E> c);
    
    // 查找
    int indexOf(Object o);
    int lastIndexOf(Object o);
    
    // 遍历
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    
    // 子List的截取
    List<E> subList(int from, int to);
}
```


### ArrayList & Vector & LinkedList
####  ArrayList
采用**可变大小的数组**实现List接口，默认增长为1.5倍。ArrayList会随着元素的增加其容积自动扩大，非同步。除此之外，几乎与Vectorc操作是同等的。

##### 特性

1. 主要底层实现是<font color="red">**对象数组**</font>；
2. 和LinkedList相比，它的**查找和访问**元素的速度较快，但**新增，删除**的速度较慢（非绝对）。所以主要使用场景是查询，扬长避短；
3. 可在**构造时初始化底层数组大小**，或者通过无参构造初始化成**默认空数组**，添加数据时才分配默认长度为10的初始容量；为什么是10？10是基于调研的一个常用且最有效的；
4. 可通过**数组扩容**的方式去避免数组有限长度的问题，达到无限制长度的效果；
5. ArrayList(int initialCapacity)会初始化数组大小，但是<font color="red">**List大小是返回size的，所以构造时List大小是无变化的**</font>，add操作之后才会增加List的大小；所以不能在构造ArrayList之后直接进行set操作，因为set内部下标是和size比较的；
6. 线程不安全，线程安全可使用**Vector(同步在方法上)**，或者**用Collections.synchronizedList包装**一个线程安全版本的数组容器使用（方法内同步语句块）；
7. **不适合做队列**。队列特性先进先出，能通过尾部新增，头部移除实现，但是涉及到数据移动，速度慢；
8. 数组适合做队列。前提是<font color="red">**定长数组**，通过两个偏移量来标记读和写的位置来满足，如果超过长度就折回到数组开头；例如：*数组阻塞队列ArrayBlockingQueue*</font>
9. **遍历性能优于LinkedList**。因为底层数组实现，分配的内存连续。CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

##### 扩容操作

1. 何时需要扩容？数组空间已填满，无法插入元素
2. 扩容算法？N+N/2 = 1.5N（N为当前数组长度，所以未指定数组长度的情况，正常的扩容长度依次会是10，15，22，33...）
3. 如何扩容？把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数组的地址换到新数组

##### 增删操作

**1. 新增操作**

新增操作分两类：指定index新增和尾部新增

*第一种：尾部新增*

1. 确认数组长度（是否扩容，是则完成扩容）
2. 加入尾部

*第二种：指定index新增*

1. 确认插入index合法
2. 确认数组长度（是否扩容，是则完成扩容）
3. 指定index开始的数据后移（通过native实现的数组拷贝来完成。并没有真正的拷贝方法，实则通过将index及之后元素一个个后移，清理出index位置的空间）
4. 在index处插入数据

综合上面两种新增方式，不难发现新增速度慢的特性描述并非绝对，是在一定的场景下得出。显然在指定index新增比较符合特性描述，因为即便拷贝操作是在native完成，但是数据量大了之后，根据上述介绍拷贝的原理，这并非是一个高性能的操作。而且扩容操作也涉及到拷贝的过程。

**2. 删除操作**

介绍一种：指定index移除

1. 确认删除index合法
2. 指定index之后的数据前移(还是同上通过数组拷贝完成)，实则覆盖非删除

同新增方式大同小异，数组容量大，效率堪忧。

##### 总结

依其名ArrayList，一个动态数组。

#### Vector
采用**可变体积的数组**实现List接口，默认增长为两倍。该类像数组一样，可以通过索引序号对所包含的元素进行访问，同步的。
#### LinkedList
采用**链表结构**实现List接口。除了List中的方法，该类还提供了在List的开头和结尾进行get，remove和insert等操作。这些操作使得LinkedList可以用来实现**堆栈、队列或双端队列**，非同步。



### Stack

```

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.<commit_msg>fixed: update;<commit_after># data_structure
java数据结构基础

# Java中的Collections API主要包含两个独立的树形结构。Collection和Map
## Collection接口
![image](‪C:\Users\Adaministrator\Desktop\CollectionAPI.png)
### [Queue](./src/main/java/com/liminghuang/queue/README.md)

除了基本的Collection接口中定义的操作，还提供其他**插入**、**删除**、和**元素检查**等操作。**限定元素个数的称为<font color="red">有界队列</font>**。

```
public interface Queue<E> extends Collection<E>{
    // 元素检查
    E element();
    
    // 插入
    boolean offer(E e);
    
    // 元素检查
    E peek();
    
    // 移除
    E poll();
    
    // 移除
    E remove();
}
```
队列操作的两种方式：

| 队列操作 | 功能说明 | 异常情况 | 抛出异常的方法 | 返回特定值的方法 |
| --- | :---: | :---: | :---: | :---: |
| 插入 | 向队列中加入元素 | 有界队列已满 | add(e) | offer(e)，返回false |
| 移除 | 从队首移走一个元素 | 队列空 | remove() | poll()，返回null  |
| 元素检查 | 返回队首元素，但不删除该元素 | 队列空 | element() | peek()，返回null |


### Set
Set继承了**Collection**接口，方法全部从Collection继承，自身没有声明其他方法。

```
public interface Set<E> extends Collection<E>{
    // 基本操作
    // 返回集合中元素的数量，如果超过int型最大值Integer.MAX_VALUE，则仅返回最大值
    int size();
    
    // 集合中不包含任何元素就返回true
    boolean isEmpty();
    
    // 集合是否包含指定元素
    boolean contains(Object element);
    
    // 往集合里添加元素，添加成功返回true；集合不允许添加重复元素返回false；其他情况抛异常；能否添加null看具体实现规则
    boolean add(E element);
    
    // 移除一个或多个与指定的元素匹配的实例，成功返回true；其余抛出异常
    boolean remove(Object o);
    
    // 返回当前集合元素的迭代器iterator，无法保证有关的顺序
    Iterator<E> iterator();
    
    // 集合元素批量操作
    // 返回当前集合是否包含指定集合C的所有元素
    boolean containsAll(Collection<?> c);
    
    // 将指定集合C的元素都添加到当前集合，自己无法添加自己，成功true；不知何时返回false;其余抛异常，不支持的操作，空指针，类型转换，非法状态，不允许添加等
    boolean addAll(Collection<? extends E> c);
    
    // 从当前集合中去除指定集合中的所有元素，成功返回true；其余抛出异常，不支持的操作、类型转换、空指针等
    boolean removeAll(Collection<?> c);
    
    // 在当前集合中只保留属于C的元素，如果当前集合发生变化则返回true；其余抛出异常，不支持的操作、类型装还、空指针等
    boolean retainAll(Collection<?> c);
    
    // 清除集合中的所有元素
    void clear();
    
    // 数组操作
    // 返回包含当前集合所有元素的数组，保证元素的顺序（依据迭代器的顺序）
    Object[] toArray();
    
    // 返回包含当前集合所有元素的数组，所返回的数组的运行时类型是数组a的类型。保证元素的顺序（依据迭代器的顺序）；如果数组a能容下集合的所有元素，则将集合元素写入a并返回，否则创建类型与a相同、长度等于集合长度的数组
    <T> T[] toArray(T[] a);
}
```
JDK提供实现Set接口的3个实用类：***HashSet***、***TreeSet***、***LinkedHashSet***;
#### 1. HashSet
采用Hash表实现了Set接口（源码使用的是HashMap），一个HashSet对象中的元素存储在一个Hash表中，元素没有固定顺序；Hash表结构支持大数据量的访问，所以比线性列表快

#### 2. TreeSet
实现了SortedSet接口（源码中未发现，待研究），采用一种有序树的结构存储集合中的元素，TreeSet对象中的元素按照升序排序

#### 3. LinkedHashSet
实现了Set接口，采用Hash表和链表相结合的结构存储集合中的元素，元素具有固定的顺序，集中了HashSet与TreeSet的优点，即能保证顺序又能够具有较高的存取效率（待研究）

### List
List是一种有序集合，继承自Collection接口。除了Collection中的方法，List接口还增加如下操作：
- 按位置存取元素，按照元素在list中的序号对其进行操作
- 查找，在list中搜寻指定的对象并返回该对象的序号
- 遍历，使用ListIterator实现List的遍历
- 截取子List，建立List视图


```
public interface List<E> extends Collection<E>{
    // 按位置存取元素
    E get(int index);
    E set(int index, E element);
    Boolean add(E element);
    void add(int index, E element);
    E remove(int index);
    boolean addAll(int index, Collection<? extends E> c);
    
    // 查找
    int indexOf(Object o);
    int lastIndexOf(Object o);
    
    // 遍历
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    
    // 子List的截取
    List<E> subList(int from, int to);
}
```


### ArrayList & Vector & LinkedList
####  ArrayList
采用**可变大小的数组**实现List接口，默认增长为1.5倍。ArrayList会随着元素的增加其容积自动扩大，非同步。除此之外，几乎与Vectorc操作是同等的。

##### 特性

1. 主要底层实现是<font color="red">**对象数组**</font>；
2. 和LinkedList相比，它的**查找和访问**元素的速度较快，但**新增，删除**的速度较慢（非绝对）。所以主要使用场景是查询，扬长避短；
3. 可在**构造时初始化底层数组大小**，或者通过无参构造初始化成**默认空数组**，添加数据时才分配默认长度为10的初始容量；为什么是10？10是基于调研的一个常用且最有效的；
4. 可通过**数组扩容**的方式去避免数组有限长度的问题，达到无限制长度的效果；
5. ArrayList(int initialCapacity)会初始化数组大小，但是<font color="red">**List大小是返回size的，所以构造时List大小是无变化的**</font>，add操作之后才会增加List的大小；所以不能在构造ArrayList之后直接进行set操作，因为set内部下标是和size比较的；
6. 线程不安全，线程安全可使用**Vector(同步在方法上)**，或者**用Collections.synchronizedList包装**一个线程安全版本的数组容器使用（方法内同步语句块）；
7. **不适合做队列**。队列特性先进先出，能通过尾部新增，头部移除实现，但是涉及到数据移动，速度慢；
8. 数组适合做队列。前提是<font color="red">**定长数组**，通过两个偏移量来标记读和写的位置来满足，如果超过长度就折回到数组开头；例如：*数组阻塞队列ArrayBlockingQueue*</font>
9. **遍历性能优于LinkedList**。因为底层数组实现，分配的内存连续。CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

##### 扩容操作

1. 何时需要扩容？数组空间已填满，无法插入元素
2. 扩容算法？N+N/2 = 1.5N（N为当前数组长度，所以未指定数组长度的情况，正常的扩容长度依次会是10，15，22，33...）
3. 如何扩容？把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数组的地址换到新数组

##### 增删操作

**1. 新增操作**

新增操作分两类：指定index新增和尾部新增

*第一种：尾部新增*

1. 确认数组长度（是否扩容，是则完成扩容）
2. 加入尾部

*第二种：指定index新增*

1. 确认插入index合法
2. 确认数组长度（是否扩容，是则完成扩容）
3. 指定index开始的数据后移（通过native实现的数组拷贝来完成。并没有真正的拷贝方法，实则通过将index及之后元素一个个后移，清理出index位置的空间）
4. 在index处插入数据

综合上面两种新增方式，不难发现新增速度慢的特性描述并非绝对，是在一定的场景下得出。显然在指定index新增比较符合特性描述，因为即便拷贝操作是在native完成，但是数据量大了之后，根据上述介绍拷贝的原理，这并非是一个高性能的操作。而且扩容操作也涉及到拷贝的过程。

**2. 删除操作**

介绍一种：指定index移除

1. 确认删除index合法
2. 指定index之后的数据前移(还是同上通过数组拷贝完成)，实则覆盖非删除

同新增方式大同小异，数组容量大，效率堪忧。

##### 总结

依其名ArrayList，一个动态数组。

#### Vector
采用**可变体积的数组**实现List接口，默认增长为两倍。该类像数组一样，可以通过索引序号对所包含的元素进行访问，同步的(线程安全)。
#### LinkedList
采用**链表结构**实现List接口。除了List中的方法，该类还提供了在List的开头和结尾进行get，remove和insert等操作。这些操作使得LinkedList可以用来实现**堆栈、队列或双端队列**，非同步。

### Stack

```

package java.util;

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
{'fraction_non_alphanumeric': 0.14628581858003284, 'fraction_numerical': 0.00821317758715094, 'mean_word_length': 4.959216965742251, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2667638', 'n_tokens_mistral': 6701, 'n_tokens_neox': 7656, 'n_words': 658}