队列（Queue）是常用的数据结构，可以将队列看成特殊的线性表，队列限制了对线性表的访问方式：只能从线性表的一端添加（offer）元素，从另一端取出（poll）元素。
队列遵循先进先出（FIFO First Input First Output ）的原则。
JDK中提供了Queue接口，同时使得LinkedList实现了该接口（选择LinkedList实现Queue的原因在于Queue经常要进行插入和删除的操作，而LinkedList在这方面效率较高）。
Queue方法：
队列
遍历元素：
Deque是Queue的子接口，定义了所谓“双端队列”即从队列的两端分别可以入队（offer）和出队（poll），LinkedList实现了该接口。
Deque方法：
双端队列
如果将Deque限制为只能从一端入队和出队，则可实现“栈”（Stack）的数据结构，对于栈而言，入栈称之为push，出栈称之为pop。
栈遵循先进后出（FILO First Input Last Output ）的原则。
栈的方法：
栈
java提供了一组可以以键值对(key-value)的形式存储数据的数据结构，这种数据结构称为Map。我们可以把Map看成一个多行两列的表格，其中第一列存放key,第二列存放value。
而每一行就相当于一组key-value对，表示一组数据。
Map对存入的元素有一个要求，就是key不能重复，所谓不能重复指的是在Map中不能包含两个equals为true的key。
Map对于key,value的类型没有严格要求，只要是引用类型均可。但是为了保证在使用时不会造成数据混乱，通常我们会使用泛型去约束key与value的类型。
常用实现类：java.util.HashMap(哈希表，散列表)----TreeMap 二叉树实现。
Map方法：
put、get方法
remove方法
还有常用方法是Map中的containsKey方法用于检测当前Map中是否包含给定的key。若当前Map中包含给定的key(这里检查是否包含是根据key的equals比较结果为依据的。)则返回true。
遍历Map的三种方式：
1）遍历所有的key 2）遍历每一组键值对(Entry) 3）遍历所有的value(相对不常用)
两种常用遍历方法
遍历value值
关于HashMap：
影响散列表(HashMap)查询性能的一个主要因素就是作为Key元素equals方法与hashcode方法的结果。妥善重写这两个方法可以避免在HashMap中出现链表导致HashMap检索性能降低。
API手册对这两个方法的重写有说明，重写原则：
1）成对重写。即：当我们需要重写一个类的equals方法时就应当连同重写hashcode
2）一致性。即:当两个对象equals比较为true时，hashcode方法返回的数字应当相等。反之亦然。虽然反之不是必须的，但是应当保证两个对象hashcode值相等时，equals方法比较为true，否则这样的对象在作为key元素在HashMap中使用时会产生链表，降低HashMap查询性能。
3）稳定性。即:当参与equals比较的属性没有发生变化的前提下，多次调用hashcode方法返回的数字必须相同。
一起重写两个方法（eclipse右键Source可自动生成）
散列表中名词：
Capacity：容量， hash表里bucket(桶)的数量，也就是散列数组大小
Initial capacity：初始容量，创建hash表的时 初始bucket的数量， 默认构建容量是16，也可以使用特定容量
Size ： 大小， 当前散列表中存储数据的数量
Load factor：加载因子，默认值0.75(就是75%)， 向散列表增加数据时如果 size/capacity 的值大于Load factor则发生扩容并且重新散列(rehash)
注：当加载因子较小时候散列查找性能会提高， 同时也浪费了散列桶空间容量。 0.75是性能和空间相对平衡结果。在创建散列表时候指定合理容量， 从而可以减少rehash提高性能。
网友评论