在介绍Java容器之前,先看一个简单的容器分类,以做到可以大体了解Java容器分类:
Java容器类类库的用途是 保存对象
,并将其划分为两个不同的概念:
栈是 后进先出 的容器。 LinkedList具有能够实现栈的所有功能的方法,可以直接将LinkedList作为栈使用 。栈操作:
队列是典型的先进先出的容器。 LinkedList 实现了Queueu接口,从而支持队列的行为。
先进先出描述了最典型的 队列规则 。所谓 队列规则 是指在给定一组队列中的元素的情况下,确定下一个弹出队列的元素的规则。 先进先出 声明的是下一个元素应该是等待时间最长的元素。
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<TestQueueElement> { @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<TestQueueElement> 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 的元素必须定义 equals() 方法以确保对象的唯一性。 Set 具有和 Collection 完全一样的接口,Set接口不保证维护元素的次序。
SortedSet中的元素可以确保处于排序状态。
对Map中使用的键的要求与对 Set 中的元素的要求是一样的。任何键都必须具有一个 equals() 方法,如果建被用于散列Map,那么他还必须具有恰当的 hashCode() 方法,如果键被用于 TreeMap ,那么它必须实现 Comparable。
使用SortedMap(TreeMap 是其现阶段的唯一实现),可以确保键处于排序状态。
只是使用容器,不知道或者说不关心容器的类型,仅仅是获取容器中的元素。 迭代器统一了对容器的访问方式。
迭代器是一个对象,它的工作是遍历并选择序列中的对象,而客户端程序员不必知道或关心该序列底层的结构。此外,迭代器通常被称为 轻量级对象 :创建它的代价小。但是对迭代器的使用是由限制的:
迭代器使用示例:
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 10; i++) list.add(i); System.out.println(list.toString()); Iterator<Integer> 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是一个更加强大的 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<Test> list = new ArrayList<>(); for (int i = 0; i < 10; i++) { Test test = new Test(i); list.add(test); } System.out.println(list.toString()); ListIterator<Test> 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() 方法必须满足下列5个条件:
强调:默认的Object.equals() 只是比较对象的地址。
在明白了如何散列之后,编写自己的hashCode()就更具有意义了。因此设计hashCode()是最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该生成同样的值。所以,如果你的hashCode()方法依赖于对象中易变的数据,此时用户就要当心,因为数据发生变化时,hashCode() 就会生成一个不同的散列码,相当于产生了一个不同的键。此外,也不应该是hashCode() 依赖于具有唯一性的对象信息,尤其是使用this的值,这样将无法生成一个新的键,只能产生很糟糕的hashCode()。应该使用对象内有意义的识别信息。
因此,要想使hashCode()实用,它必须速度快,并且必须有意义。也就是说,它必须基于对象的内容生成散列码。所以,散列码不必是独一无二的(应该更关注生成速度,而不是唯一性),但是通过hashCode()和 equals(),必须能够完全确定对象的身份。
好的hashCode()应该产生分布均匀的散列码。如果散列码都几种在一块,那么HashMap或者HashSet 在某些区域的负载会很重,这样就不如分布均匀的散列函数。
因此一个好的hashCode() 应该遵循的指导是:
域类型 | 计算 |
---|---|
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
; 下面便是遵循这个指导的一个示例:
public class CountedString { private static List<String> 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<CountedString, Integer> 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)); } } } 复制代码