常用数据结构及其Java实现

这玩意就是得温故而知新，时常看看琢磨琢磨
基于链接：https://segmentfault.com/a/1190000009797159

前言

首先给出Java集合框架的基本接口/类层次结构：

java.util.Collection [I]
    +--java.util.List [I]
       +--java.util.ArrayList [C]    
       +--java.util.LinkedList [C]  
       +--java.util.Vector [C]    //线程安全
          +--java.util.Stack [C]  //线程安全
    +--java.util.Set [I]                   
       +--java.util.HashSet [C]      
       +--java.util.SortedSet [I]    
          +--java.util.TreeSet [C]    
    +--Java.util.Queue[I]
        +--java.util.Deque[I]   
        +--java.util.PriorityQueue[C]  
java.util.Map [I]
    +--java.util.SortedMap [I]
       +--java.util.TreeMap [C]
    +--java.util.Hashtable [C]   //线程安全
    +--java.util.HashMap [C]
    +--java.util.LinkedHashMap [C]
    +--java.util.WeakHashMap [C]

[I]：接口
[C]：类
本图来源于网络。

数组

• 数组是相同数据类型的元素按一定顺序排列的集合，是一块连续的内存空间。

• 优点：get和set操作时间上都是O(1)；

• 缺点：add和remove操作时间上都是O(N)。

• Java中，Array就是数组，此外，ArrayList使用了数组Array作为其实现基础，跟一般的Array相比，最大的好处是在添加元素时不用考虑越界，ArrayList会自动扩张保证容量。

• Vectory和ArrayList相比，主要区别在于多了一个线程安全，但是效率比较底下。java.util.concurrent包提供了许多线程安全的集合类，不必再使用Vectory。

int[] ints1 = new int[10];
ints1[0] = 5;
int[] ints2 = new int[]{2,3,4,5};
int a = ints2[1];
int length = ints2.length;

链表

• 链表是一种非连续、非顺序的结构，数据元素的逻辑顺序是通过链表中指针的链接次序实现的，链表由一系列节点组成；

• 优点：add和remove操作时间上都是O(1);

• 缺点：get和set操作时间上都是O(N)，且需要额外空间存储指向其他数据的地址项；

• 查找操作对于未排序的数组和链表时间上都是O(N)；

• Java中LinkedList使用链表作为其基础实现；

队列

• 队列是一中特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，即先进先出（FIFO）；

• Java中，LinkedList实现了Deque，可以作为双向队列（自然也可以作为单向队列）；

• PriorityQueue实现了带优先级的队列，即队列的每一个元素都有优先级，且元素按照优先级排序；

Deque<Integer> integerDeque = new LinkedList<>();
// 尾部入队的两种方法，区别在于：
// 如果失败，add()会抛出IllegalStateException异常，而offer()返回false
integerDeque.offer(122);
integerDeque.add(122);

// 头部出队的两种方法（从队列中删除），区别在于：
// 如果失败，remove()抛出NoSuchElementException异常，而poll方法返回false
int head = integerDeque.poll(); // 返回并删除
head = integerDeque.remove();  // 返回并删除

// 头部出队的两种方法（不删除），区别在于：
// 如果失败，element()抛出NoSuchElementException异常，而peek()不会
head = integerDeque.peek();
head = integerDeque.element();

栈

• 又名堆栈，是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一段称为栈顶。提现了后进先出（LIFO）特定；

• Java中，Stack实现了这种特性，但是Stack也继承了Vector，所以具有线程安全和效率低下两个特性；

• JDK8中，推荐使用Deque来实现栈；

Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(12); // 尾部入栈
stack.push(16); // 尾部入栈
int tail = stack.pop(); // 尾部出栈，并删除元素
tail = stack.peek(); // 尾部出栈，不删除元素

集合

• 集合是指具有某种特定性质的具体或抽象的对象汇成的集体，这些对象成为集合的元素；

• 主要特性是：元素不可以重复；

• Java中HashSet提现了这种数据结构，HashSet是在HashMap的基础上构建的；

• LinkedHashSet继承了HashSet，使用HashCode确定在集合中的位置，使用链表的方式确定位置，所以有顺序。

• TreeSet实现了SortedSet接口，是排好序的集合（在TreeMap基础之上构建），因此，查找操作比普通的HashSet要快（log(N)），插入操作要慢（log(N)），因为要维护有序；

HashSet<Integer> integerHashSet = new HashSet<>();
integerHashSet.add(12121);//添加
integerHashSet.contains(121);//是否包含
integerHashSet.size();//集合大小
integerHashSet.isEmpty();//是否为空

散列表

• 又名哈希表，是根据键值对（key-value）进行访问的数据结构，通过把键映射到表中一个位置来访问记录，加快查找速度，这里的映射函数叫做散列函数；

• Java中HashMap实现了散列表，而HashTable比它多了一个线程安全，但是由于HashTable使用了全局锁导致性能较低，使用ConcurrentHashMap替代；

• TreeMap实现SortedMap接口，能够把它保存的记录按照键排序。

• LinkedHashMap保留了元素插入的顺序；

• WeakHashMap是一种改进的HashMap，对key实行“弱引用”，如果一个key不再被外部引用，则可以被GC回收，不需要我们手动删除；

https://www.cnblogs.com/skywang12345/p/3311092.html
WeakHashMap和HashMap一样，也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。