经典容器 数组/链表/队列/散列表/映射表，及相关内容的排序方式
编程技术 / houtizong 发布于 3年前 67
Java 经典容器 数组/链表/队列/散列表/映射表，及相关内容的排序方式
了解java容器的必要性：
javaEE开发大家经常用的也就是 数组，ArryList，Set等，其它的就用的很少了
或是没有听说过。
多了解一些内容，对于同一问题的解决可能拿出更优的解决方案，
优秀的代码能够给与程序性能、用户体验的提升，优秀的解决方案能够
让咱们轻轻松松解决问题。
性能与解决方案都取决于我们经验的积累，也就是我们知识的积累。
因为是学习，所以很多地方可能不到位或是错误的地方大家指正，一定要指正啊！！
我学习的基本思路是：
理论理解，经典实现举例，代码练习及结果，对应例子的使用场景，与使用中与之关联较紧密内容的拓展。
大致内容：数组，链表，队列，散列集，映射表，链接散列集，链接映射表
容器：就是不同数据结构存储的不同实现。
(一)链表：包含3部分，data、next、previous 三部分都是双向链表
特性：高效利用内存，新增、修改、删除效率较高，因为只是涉及到数据域前链存储地址或后链存储地址等地址指向的
变更。
不支持快速随机访问（就是通常用的get）,如果为快速随机访问且能够提供下标最好用数组或ArrayList
不是线程安全的，多线程中需要使用Collections.synchronizedList进行包装或自己实现线程同步方法
Collections工具类中提供的同步方法
List list = Collections.synchronizedList(new LinkedList(...));
然后其它线程对list可以同时进行操作，如list.add() list.remove() ....
使用场景：堆栈、队列或双端队列。
例：LinkedList
默认含有List接口提供的方法，调用add方法时默认数据被放入链尾
实现了Queue Deque 队列接口。
方法
boolean add(E e): 将指定元素添加到此列表的结尾。
add(int index, E element)：在此列表中指定的位置插入指定的元素。
addLast(E e)： 将指定元素添加到此列表的结尾。
addFirst(E e)： 将指定元素插入此列表的开头。
boolean offer(E e)： 将指定元素添加到此列表的末尾（最后一个元素）。
boolean offerFirst(E e)： 在此列表的开头插入指定的元素。
boolean offerLast(E e)： 在此列表末尾插入指定的元素。
push(E e)：压栈
由于实现了List Queue Deque 等接口，所以同一操作方法也比较多，区别在于是否知道操作成功与否
及抛出的异常信息
作为队列能够提供：能够根据需要提供各种灵活的进出策略，
比如： FIFO（先进先出） LIFO（后进先出）
(二) 队列
：队列是特殊的线性表，在表头删除在表尾删除
自认为链表结构都是双端队列，数组结构可以理解为单向队列
双端队列，有限队列，有限双端队列,优先级队列都可以用字面去理解、
特性： 可以同时在表头删除元素在表尾添加元素。
队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），
另一种返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是用于专门为有容量
限制的 Queue 实现设计的；在大多数实现中，插入操作不会失败。
队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或
堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对
元素进行排序。无论使用哪种排序方式，队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO
队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现
必须指定其顺序属性。
使用场景：任务排队处理，批量任务处理，线程池中任务的处理
其实就是有先后的任务处理，或数据的批量处理
队列接口 Queue Java源码中提供的队列实现基本都实现了Queue及后续对Queue拓展的Deque等
举例：LinkedList
AbstractQueue
ArrayBlockingQueue
ArrayDeque
ArrayBlockingQueue
PriorityQueue(优选级队列)
等
队列提供的方法：
通用：插入 add(e) offer(e)
移除 remove() poll()
检查 element() peek()
boolean add(E e) :成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。
boolean offer(E e) 当使用有容量限制的队列时，此方法通常要优于 add(E)，后者可能无法插入元素，而只是抛出一个异常。
E remove() 获取并移除此队列的头。
E poll() 获取并移除此队列的头，如果此队列为空，则返回 null。
E element() 获取，但是不移除此队列的头。
E peek() 获取但不移除此队列的头；如果此队列为空，则返回 null。
拓展：优先级队列：使用堆数据结构的队列，堆是一个可以自我调整的二叉树，
树执行add remove操作都可以让最小元素移动到根，不用排序
优先级队列中可以保存实现了comparable接口的对象，
也可以保存指定排序方式实现Comparator接口的对象。
优先级队列 PriorityQueue
例：PriorityQueue<XX> pq = new PriorityQueue<XX>();
pq.add(new XX);'
打印get 看获取出来是不是最小的对象。
(三) 散列表
：可以快速的查找所需要的对象，散列表为每个对象计算出一个散列码hash code 根据对象实例域产生的整数
自定义类需要实现hash code方法，实现的hash code方法必须与equals方法兼容
散列表用链表数组实现，每个列表被称作桶 hashcode%桶的数目=保存元素桶的索引
我理解的桶就是 一个双数组，根据key在数组中的下标，来取另一个数组的值
Entry(int h,Key key,Value value,Entry<K,V> next) 表感觉是指的Entry []
散列集的默认实现：HashSet
1.HashSet是无序的
2.在数据大时存储效率较高
public HashSet() {
map = new HashMap<E,Object>();
}
TreeSet
TreeSet排序方式是升序存储对象类必须实现了Compareable接口的compare to方法
也可以通过指定对象排序方式，通过指定使用Comparator类接口的compare方法
new TreeSet(object,new Comparator{public int compare(Obj1,Obj2){xxxxx}})
WeakHashMap多用于缓存，存的值key 是使用了java的WeakReference
软引用 SoftReference
弱引用WeakReference
WeakHashMap的key的排序也可以使用Compareable或Comparator方法进行排序，
LinkedHashMap链接映射表：
LinkedHashMap实现了LRU缓存算法，最近使用原则，丢弃长时间没访问的数据项，
通过重写父类方法:removeEldestEntry(Map.Entry<K,V> eldest){}方法实现，
请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
技术博客集 - 网站简介：
前后端技术：
后端基于Hyperf2.1框架开发,前端使用Bootstrap可视化布局系统生成
网站主要作用：
1.编程技术分享及讨论交流，内置聊天系统;
2.测试交流框架问题，比如：Hyperf、Laravel、TP、beego;
3.本站数据是基于大数据采集等爬虫技术为基础助力分享知识，如有侵权请发邮件到站长邮箱，站长会尽快处理;
4.站长邮箱：[email protected];
文章归档
文章标签
友情链接
