Java 容器基本介绍-白红宇

在介绍Java容器之前，先看一个简单的容器分类，以做到可以大体了解Java容器分类：

容器基本介绍

Java容器类类库的用途是保存对象，并将其划分为两个不同的概念：

Collection:一个独立元素的序列，这些元素都服从一条或多条规则。 List 必须按照插入的顺序保存元素，而 Set 不能有重复元素。 Queue 按照排队规则来确定对象产生的顺序。

Map：一组成对的键值对，允许你使用键来查找值。又被称为映射表、关联数组、字典。

List

ArrayList：擅长随机访问元素，但是在List的中间插入和移除元素时较慢。

LinkedList：通过较低的代价可以在List中间进行插入和删除操作，提供了优化的顺序访问。LinkedList在随机访问方面相对比较慢，但是它的特性集较ArrayList更大。
- LinkedList 也像 ArrayList 一样实现了基本的List接口。
- LinkedList还添加了可以使其用做栈、队列或双端队列的方法。
- getFirst() 和 element() 完全一样，都返回列表的头（第一个元素）,而并不移除它，如果 List 为空，则抛出 NoSuchElementException。 peek() 方法，在列表为空时返回null。
- removeFirst() 和 remove() 也完全一样，移除并返回列表的头，如果 List 为空，则抛出 NoSuchElementException。poll()，在列表为空时返回null。
- add() 和 addLast() 一样，将某个元素插入到列表的尾部。
- removeLast() 和 pollLast（） 移除并返回列表的最后一个元素。

Stack

栈是 后进先出 的容器。LinkedList具有能够实现栈的所有功能的方法，可以直接将LinkedList作为栈使用。栈操作：

push() ：入栈。

peek（） :获取栈顶元素，但是并不将其从栈顶移除。

pop() :移除并返回栈顶元素。

Queue

队列是典型的先进先出的容器。LinkedList 实现了Queueu接口，从而支持队列的行为。

offer() :将一个元素插入到队尾。

peek() 和 element() 都将在不移除的情况下返回对头，element() 在队列为空，则抛出 NoSuchElementException。 peek() 方法，在列表为空时返回 null 。

poll() 和 remove() 移除并返回对头。**remove()**如果队列为空，则抛出 NoSuchElementException。poll()，在列表为空时返回null。

PriorityQueue

先进先出 描述了最典型的 队列规则 。所谓 队列规则 是指在给定一组队列中的元素的情况下，确定下一个弹出队列的元素的规则。 先进先出 声明的是下一个元素应该是等待时间最长的元素。

PriorityQueue是优先级队列，其声明下一个弹出的元素是最需要的元素（具有最高优先级）。

当你在PriorityQueue 上调用 offer（） 方法来插入一个对象时，这个对象会在队列中排序。默认的排序将使用对象在队列队列中的自然顺序，但是你可以通过提供自己的Comparator接口实现来修改这个顺序。PriorityQueue 可以确保当你调用peek()、poll()和remove()方法时，获取的元素将是队列中优先级最高的元素。

使用示例：

public class TestQueueElement {    public int getAge() {        return age;    }    public int getSex() {        return sex;    }    public String getName() {        return name;    }    private int age;    private int sex;    private String name;    public TestQueueElement(int age, int sex, String name) {        this.age = age;        this.sex = sex;        this.name = name;    }    @Override    public String toString() {        return getClass().getSimpleName() + " { name:" + name + " ,age:" + age + ",sex:" + sex + "}";    }}/** * 1.以age字段的升序进行排序， * 2.在age相同时，以name字段的长度的升序进行排序 */public class TestQueueElementComparator implements Comparator
    
      {    @Override    public int compare(TestQueueElement o1, TestQueueElement o2) {        int result = 0;        if (o1.getName().length() > o2.getName().length()) {            result += 1;        } else if (o1.getName().length() < o2.getName().length()) {            result -= 1;        }        if (o1.getAge() > o2.getAge()) {            result += 2;        } else if (o1.getAge() < o2.getAge()) {            result -= 2;        }        return result;    }}public class Main {    public static void main(String[] args) {        PriorityQueue
     
       pq = new PriorityQueue<>(10, new TestQueueElementComparator());        pq.offer(new TestQueueElement(10, 0, "name1"));        pq.offer(new TestQueueElement(9, 0, "name1"));        pq.offer(new TestQueueElement(11, 0, "name1"));        pq.offer(new TestQueueElement(10, 0, "name11"));        pq.offer(new TestQueueElement(10, 0, "name111"));        pq.offer(new TestQueueElement(8, 0, "name"));        pq.offer(new TestQueueElement(8, 0, "name111"));        while (!pq.isEmpty()) {            System.out.println(pq.poll());        }    }}输出结果：TestQueueElement { name:name ,age:8,sex:0}TestQueueElement { name:name111 ,age:8,sex:0}TestQueueElement { name:name1 ,age:9,sex:0}TestQueueElement { name:name1 ,age:10,sex:0}TestQueueElement { name:name11 ,age:10,sex:0}TestQueueElement { name:name111 ,age:10,sex:0}TestQueueElement { name:name1 ,age:11,sex:0}复制代码

Set

存入 Set 的每个元素都必须是唯一的，因为 Set 不保存重复元素。加入 Set 的元素必须定义 equals() 方法以确保对象的唯一性。Set 具有和 Collection 完全一样的接口，Set接口不保证维护元素的次序。

HashSet:为快速查找而设计的Set，存储顺序没有意义。存入 HashSet 的元素必须定义 hashCode()。如果没有其他限制，这应该是默认的选择，因为其对速度进行了优化。

TreeSet：按照比较结果的升序保存对象，将元素存储在红-黑树数据结构中。保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现 Comparable 接口。

LinkedHashSet：按照被添加的顺序保存对象，使用了链表来维护元素的插入顺序。具有HashSet的查询速度，且内部使用链表维护元素的顺序（插入的次序）。于是在使用迭代器遍历 Set 时，结果会按元素插入的次序显示。元素也必须实现 hashCode()方法。

SortedSet

SortedSet中的元素可以确保处于排序状态。

Comparator comparator(): 返回当前Set使用的Comparator;或者返回null,表示以自然方式排序。

Object first():返回容器中的第一个元素。

Object last():返回容器中的最后一个元素。。

SortedSet subSet(fromElement,toElement)生成此Set的子集，范围由fromElement（包含）到 toElement(不包含)的键确定。

SortedMap headSet(toElement)生成次Set的子集，由小于toElement的元素组成。

SortedMap tailSet(fromElement)生成此Set的子集，由大于fromElement的元素组成。

Map

对Map中使用的键的要求与对 Set 中的元素的要求是一样的。任何键都必须具有一个 equals() 方法，如果建被用于散列Map，那么他还必须具有恰当的 hashCode() 方法，如果键被用于 TreeMap ,那么它必须实现 Comparable。

HashMap:提供最快的查找技术，没有按照任何明显的顺序来保存元素。HashMap就是利用对象的 hashCode() 进行快速查询的，此方法可以快速提高性能。在没有其他的限制时，HashMap是默认选择。插入和查询 键值对 的开销是固定的。可以通过构造器设置容量和负载因子，已调整容器的性能。

TreeMap:基于红黑树的实现，按照比较结果的升序保存键值对，它们会被排序（次序由 Comparable 或 Comparator 决定）。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap 是唯一的带有 subMap() 方法的，他可以返回一个子树。

LinkedHashMap:按照插入顺序保存键，只是比Hashmap的速度慢一点，而在迭代访问时反而更快，因为它是使用链表维护内部次序的。

WeakHashMap:弱键映射，允许释放映射所指向的对象。如果映射之外没有引用指向某个键，则此键可以被垃圾收集器回收。

ConcurrentHashMap:一种线程安全的Map，它不涉及同步加锁。

IdentityHashMap:使用 == 代替 equals() 对键进行比较的散列映射。

SortedMap

使用SortedMap（TreeMap 是其现阶段的唯一实现）,可以确保键处于排序状态。

Comparator comparator(): 返回当前Map 使用的Comparator;或者返回null,表示以自然方式排序。

T firstKey():返回Map中的第一个键。

T lastKey():返回Map中的最后一个键。

SortedMap subMap(fromKey,toKey)生成此Map的子集，范围由fromKey（包含）到 toKey(不包含)的键确定。

SortedMap headMap(toKey)生成次Map的子集，由键小于toKey的所有键值对组成。

SortedMap tailMap(fromKey)生成此Map的子集，由键大于或等于fromKey的所有键值对组成。

迭代器

只是使用容器，不知道或者说不关心容器的类型，仅仅是获取容器中的元素。迭代器统一了对容器的访问方式。

迭代器是一个对象，它的工作是遍历并选择序列中的对象，而客户端程序员不必知道或关心该序列底层的结构。此外，迭代器通常被称为 轻量级对象：创建它的代价小。但是对迭代器的使用是由限制的：

使用方法 iterator() 要求容器返回一个 Iterator。 Iterator 将准备好返回序列中的第一个元素。

使用 next() 获取序列中的下一个元素。

使用 hasNext() 检查序列中是否还有元素。

使用 remove() 将迭代器新近返回的元素删除。意味着在调用 remove() 之前必须先调用 next() 。

迭代器使用示例：

public static void main(String[] args) {        List
    
      list = new ArrayList<>();        for (int i = 0; i < 10; i++) list.add(i);        System.out.println(list.toString());        Iterator
     
       it = list.iterator();        //遍历迭代器对象，循环结束，it中不在具有元素        while (it.hasNext()) {            Integer integer = it.next();            System.out.println(integer.toString());        }        it = list.iterator();                //删除it迭代器中的元素，同时list中对应的元素也被删除        for (int i = 0; i < 5; i++) {            it.next();            it.remove();        }    }复制代码

ListIterator

ListIterator 是一个更加强大的 Iterator 的子类型，它只能用于各种 List 类的访问。尽管 Iterator 只能向前移动，但是 ListIterator 可以双向移动 )。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引，并且可以使用 set() 方法替换它访问过的最后一个元素。你可以通过调用 listIterator() 方法产生一个指向 List 开始处的 ListIterator，并且还可以通过调用 listiterator(n) 方法创建一个一开始就指向列表索引为n的元素处的 ListIterator。

使用示例：

public class Test {    private String id;    public Test(int id) {        this.id = "test:" + id;    }    @Override    public String toString() {        return id;    }} public static void main(String[] args) {        List
    
      list = new ArrayList<>();        for (int i = 0; i < 10; i++) {            Test test = new Test(i);            list.add(test);        }        System.out.println(list.toString());        ListIterator
     
       it = list.listIterator();        while (it.hasNext()) {            //it.next() 获取下一个元素            //it.nextIndex() 获取下一个元素的索引            //it.previousIndex() 获取上一个元素的索引            System.out.println(it.next() + "," + it.nextIndex() + "," + it.previousIndex() + ";");        }        System.out.println();        // 是否有上一个元素        while (it.hasPrevious()) {            //it.previous() 获取上一个元素            System.out.println(it.previous() + " ");        }        it = list.listIterator(3);        while (it.hasNext()) {            it.next();            it.set(new Test(20));        }        System.out.println(list.toString());    }复制代码

散列和散列码

散列码是 相对唯一 的，用以代表对象的int值，它是通过将对象的某些信息进行转换而生成的。hashCode() 是根类Object中的方法，因此所有的Java 对象都可以产生散列码。

首先，使用散列的目的在于：想要使用一个对象来查找另一个对象。

其次，散列的价值在于速度：散列将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以使用它来表示键的信息 （注意；所说的是键的信息，而不是键本身）。由于数组不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码，由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成。

为解决数组容量被固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突。因此，数组多大就不重要了，任何键总能在数组中找到它的位置。

于是查询一个值得过程就是计算散列码，然后使用散列码查询数组。如果能够保证没有冲突，那可就有了一个完美的散列函数，但是这种情况只是特例。通常，冲突由外部链接处理：数组并不直接保存值，而是保存值的list。然后对list中的值使用equals()方法进行线性查询。这部分的查询自然会比较慢（因为线性查询是最慢的查询方式），但是，如果散列函数好的话，数组的每个位置就只有较少的值。因此，不是查询整个list，而是快速的跳到数组的某个位置，只对很少的元素惊醒比较。从而使HashMap的查询速度加快。

当用自己创建用作 HashMap 的键的类，必须在其中放置必须的方法：equals() 和 hashCode() 两个方法。HashMap 使用 equals() 判断当前的键是否与表中存在的键相同。hashCode()并不需要总是能够返回唯一的标识码，但是equals()方法必须严格地判断两个对象是否相同。

如何正确的覆盖 equals()

正确的 equals() 方法必须满足下列5个条件：

自反性：对任意x, x.equals(x) 一定返回 true。

对称性：对任意x和y，如果y.equals(x)返回true,则x.equals(y)也返回true。

传递性：对任意x,y,z,如果x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定返回true。

一致性：对任意x和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，返回的结果应该保持一致，要么一直是true,要么一直是false。

对任意不是null的x,x.equals(null)一定返回false。

强调：默认的Object.equals() 只是比较对象的地址。

如何正确的覆盖 hashCode（）

在明白了如何散列之后，编写自己的hashCode()就更具有意义了。因此设计hashCode()是最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该生成同样的值。所以，如果你的hashCode（）方法依赖于对象中易变的数据，此时用户就要当心，因为数据发生变化时，hashCode() 就会生成一个不同的散列码，相当于产生了一个不同的键。此外，也不应该是hashCode() 依赖于具有唯一性的对象信息，尤其是使用this的值，这样将无法生成一个新的键，只能产生很糟糕的hashCode（）。应该使用对象内有意义的识别信息。

因此，要想使hashCode()实用，它必须速度快，并且必须有意义。也就是说，它必须基于对象的内容生成散列码。所以，散列码不必是独一无二的（应该更关注生成速度，而不是唯一性），但是通过hashCode（）和 equals()，必须能够完全确定对象的身份。

因为在生成桶的下标前，hashCode() 还需要做进一步的处理，所以散列码的生成范围并不重要，只要是int即可。

好的hashCode()应该产生分布均匀的散列码。如果散列码都几种在一块，那么HashMap或者HashSet 在某些区域的负载会很重，这样就不如分布均匀的散列函数。

因此一个好的hashCode() 应该遵循的指导是：

给 int 变量result 赋予某个非零值常量。

为对象内每个有意义的域f(即每个可以做equals()操作的域)计算出一个int散列码c;

域类型	计算
boolean	c=(f?0:1)
byte、char、short或int	c=(int)f
long	c=(int)(f^(f>>>32))
float	c=Float.floatToIntBits(f)
doble	long L = Double.doubleToLongBits(f); c=(int)(L^(L>>>32))
Object,其equals（）调用这个域的 equals()	c=f.hashCode()
数组	对每个元素应用上述规则

合并计算得到的散列码：result = 37 * result + c;

返回result。

检查hashCode（）最后导出的结果，确保相同的对象就有相同的散列码。

下面便是遵循这个指导的一个示例：

public class CountedString {    private static List
    
      created = new ArrayList<>();    public String getString() {        return mString;    }    public void setString(String string) {        mString = string;    }    private String mString;    private int id;    public CountedString(String string) {        mString = string;        created.add(string);        for (String s2 : created) {            if (s2.equals(mString)) id++;        }    }    @Override public String toString() {        return "String:" + mString + " id:" + id + " hashCode():" + hashCode();    }    @Override public int hashCode() {        int result = 17;        result = 37 * result + mString.hashCode();        result = 37 * result + id;        return result;    }    @Override public boolean equals(Object obj) {        return obj instanceof CountedString && mString                .equals(((CountedString) obj).mString) && id == ((CountedString) obj).id;    }    public static void main() {        Map
     
       map = new HashMap<>();        CountedString[] cs = new CountedString[5];        for (int i = 0; i < cs.length; i++) {            cs[i] = new CountedString("hi");            map.put(cs[i], i);        }        System.out.println(map);        for (CountedString cst : cs) {            System.out.println("Looking up:" + cst);            System.out.println(map.get(cst));        }    }}复制代码