Java的数据结构
一、Collection
Collection接口有List和Set两个子接口。
1、List
- ArrayList
- 底层动态数据结构，可存储重复元素，存储有序。
- 线程不安全的，效率高。
- 初始化一个ArrayList时，不指定容量，默认会创建一个容量10的数组。随着添加元素，达到数组容量上限时，可自动扩容一倍的容量。
- 查询快，增删慢。底层动态数组，数组的元素在内存中地址是连续的。查询时可直接通过数组索引找到结果。增删时，由于是对数组操作，每增加或删除元素，数组内所有的元素内存地址都会变动，会比较慢。
- LinkedList
- 底层双向链表数据结构，可存储重复元素，存储有序。
- 链表上的节点是一个Node，Node中item是当前节点的值，prev指向上一节点，next指向下一节点。
- 查询慢，增删快。因为LindedList底层实现是链表，链表的每个节点在内存中的存储地址是随机非连续的，节点除了记录自己的值还要记录下一个节点甚至上一个节点的指针。查询时只能遍历链表，equals比较值，找到结果，会比较慢。增加元素，只需要在链表末尾新增一个节点，并将上一个节点的next指针指向新增的节点即可。删除元素，先遍历链表插到要删除的节点，然后置空此节点，将前后节点的指针关联起来。
- Vector
- 和ArrayList特性基本相似，线程安全的，效率低。
- 还有个子类Stack，一般可用于栈的管理。push方法添加一个对象到栈顶，pop方法弹出栈顶的对象，peek方法查看栈顶的对象。
2、Set
- HashSet
- 基于HashMap实现，HashSet的值就是HashMap的key，value是PRESENT对象。
- 不可存储重复元素，存储无序。
- TreeSet
- 底层红黑树数据结构。
- 不可存储重复元素，存储有序。有基于元素key的高效排序算法，存储顺序从小到大。
二、Map
- HashMap
- 线程不安全的，效率略高，集中了ArrayList和LinkedList的优点。
- 存储无需，key值唯一，可存储一组null。
- HashMap底层是一个hash表，元素为单项链表的数组，jdk1.8之前数据的元素是链表，jdk1.8之后，若链表长度达到8时，则会将链表置换为红黑树。
- 初始化HashMap时，若不传入容量，默认会生成长度16，加载因子0.75的数组。随着数组存储长度达到16*0.75时，会自动扩容一倍的容量。
- HashMap中，是以键值对的形式存储，通过key的hashcode值，决定该组键值对在数组的具体位置，然后找到对应的单链表。每组键值对，jdk1.8之前封装成Entry，jdk1.8之后封装成了Node，Node中包含key的hash值，key值，value值，下一个节点的指针。
- HashMap当put键值对时，首先算出key的hashcode值，去遍历数组找对应的下标，找不到，则会在数组末尾添加一组，保存该节点。找到了对应下标后，则会遍历这个位置的链表，根据key值判断是否已有节点，有的话直接用新值覆盖掉旧值，若没有节点，在链表的末尾保存该节点。
- 之所以使用单链表存储，是因为存储的键值对越来越多，就有可能出现key生成的hashcode一样，造成hash冲突，此时，即可把新添加的键值对存在这个数组位置对应的单链表内。单链表里的每个节点，key的hashcode是相同的，但是key值不同，他们在数组的同一个索引位置。
- TreeMap
- 有序的key-value集合，基于红黑树实现，不能存储null。
- 线程不安全的。
- Hashtable
- 和HashMap功能基本相似。
- 但线程安全的，效率低。
Java基本算法、排序方式
- 选择排序：双重for循环，每一趟排序获取最小数，依次将最小数的位置放在已排好序的序列最后。
int[] arr = {6, 4, 9, 1, 5, 3};
for(int i = 0; i < arr.length - 1; i++) {
int k = i;
for(int j = k + 1; j < arr.length; j++) { // 选最小的值
if(arr[j] < arr[k]) {
k = j; // 记下目前找到的最小值所在的位置
}
}
// 找到本轮循环的最小的数以后，再进行交换
if(i != k) { // 交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
- 冒泡排序：双重for循环，依次比较相邻的两个元素，将小数放在前面，大数放在后面。
int[] arr = {6, 4, 9, 1, 5, 3};
int temp;
for(int i = 0; i < arr.length - 1; i++) { // 外层循环控制排序趟数
for(int j = 0; j < arr.length - i - 1; j++) { // 内层循环控制每一趟排序多少次，每一次循环把大数滚到队列末尾
if(arr[j + 1] < arr[j]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
- 快速排序：选择一个关键值作为基准值。比基准值小的都在左边序列，比基准值大的都在右边序列。时间复杂度为O(NlogN)。
public static int[] quickStore(int[] array, int l, int r) {
if (l < r) {
int i = l;
int j = r;
int x = array[l];
while (i < j) {
while (i < j && array[j] >= x) {
// 从右向左找第一个小于x的数
j--;
}
if (i < j) {
array[i++] = array[j];
}
while (i < j && array[i] < x) { // 从左向右找第一个大于等于x的数
i++;
}
if (i < j) {
array[j--] = array[i];
}
}
array[i] = x;
quickStore(array, l, i - 1);
quickStore(array, i + 1, r);
}
return array;
}
- 二分查找法：对有序数列查找，查找时，先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。如此递归执行，直至查找到对象。
// 二分查找递归实现
public static int binSearch(int array[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (array[mid] == key) {
return mid;
}
if (start >= end) {
return -1;
} else if (key > array[mid]) {
return binSearch(array, mid + 1, end, key);
} else if (key < array[mid]) {
return binSearch(array, start, mid - 1, key);
}
return -1;
}
// 二分查找普通循环实现
public static int binSearch(int array[], int key) {
int mid = array.length / 2;
if (key == array[mid]) {
return mid;
}
int start = 0;
int end = array.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (key < array[mid]) {
end = mid - 1;
} else if (key > array[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
