[TOC]

常用容器类相关

• 在 java.util 包中，包括三个常用的数据结构接口：List / Set / Map

• 详细点儿的包含继承关系如下 Collection

  • List

    • LinkedList
    • Vector
    • ArrayList

  • Map

    • TreeMap
    • HashMap
    • Hashtable

  • Set

    • TreeSet
    • HashSet

  • Queue

    • PriorityQueue

Collection

• Collection 是所有集合类的接口，List / Set 都由 Collection 继承而来，基本操作都实现了，下面是API 文档的方法摘要
• Collections 是所有操作集合的工具类，提供了很多使用便捷的方法，集合的操作，排序等，大部分集合接口的实现类都不是多线程同步的，要是想使用多线程同步的话，需要使用 Collections.synchronized*(new *)来创建线程同步的集合类

List

• ArrayList / Vector 是线性表，效率都比不上数组，但是可以扩展较为固定的数组，此外使用 ArrayList 效率一般比较好，但是，Vector 默认是线程同步的，而 ArrayList 不是线程安全的
• LinkedList 是基于链表实现的，对于频繁的删除插入，使用 LinkedList 的效率更好
• LinkedList 的几个常用方法

Method

Description

add([int index,] E element)

在 index 处插入元素

addFirst(E e)

在列表头部加入指定元素

addLast(E e)

在列表尾部加入指定元素

contains(Object o)

判断列表中是否包含 o

peekFirst()

获取但不删除列表头部元素

pollLast()

获取并移除列表尾部元素

remove([int index])

移除指定位置[首位]的元素

remove(Object o)

移除列表中第一次上出现的指定元素

size()

列表元素个数

Map

• HashMap

  • HashMap 的实质的存储一个 Entry 对象，每次将 put 进来的键值对转换成一个 Entry 对象储存到一个 Entry 数组中，位置是由 key 的哈希值和数组长度计算的来，采用直接覆盖的形式添加元素，即先通过 hashcode 找到数组中的某一个元素，再通过 key 的 equals 方法在链表中找到与之对应的 value

• TreeMap

  • TreeMap 的实现是一个由 Entry 元素构成的红黑树，每次 put 进入的蒜素按照定义时传入的 Comparator 进行排序，依然保证 key 唯一有序

• HashTable

  • HashTable 和 HashMap 差不多，但是区别在以下几点

    • HashMap 不是线程安全的，当有多个线程共用，不会被同步锁锁定，而是会抛出异常
    • HashMap 可以另存储的 key 是 null， 但是 HashTable 不可以
    • HashMap 中元素的顺序是不固定的

• 经常创建的不是 Map，而是 HashMap，方法比较多，记录几个极其常用的

  • get(Object Key) 获取指定的 key 键的 value 值
  • put(Object Key, Object value) 覆盖性的存放当前的键值对
  • containsKey(Object Key) 判断 Map 中是否包含某一个 key 键元素

• 需要覆盖重写的方法

  • equals(Object o)
  • hashCode()

• Map 遍历没有直接的获取方式，只能通过“视图”的方式，分别是

  • entrySet() 返回值是 Map 映射的 Set 视图，每一个元素都是 Map.Entry 对象，获取键 / 值得方法是 getKey() / getValue()
  • keySet() 返回 Map 的 Set 视图，此时对 Set 操作将会关联性得影响 Map 中的映射
  • values() 返回 Map 的 Collection 视图，同操作关联
  • 每一种便利还都无法直接遍历，都必须使用 Iterator 迭代器

/_ ForEach 方法 _/
Map<Integer, Integer> dic = new HashMap<Integer, Integer>();

/_ 遍历全部 Map 映射的 Key 和 Value _/
for (Map.Entry<Integer, Integer> now : map.entrySet()) {
System.out.println(now.getKey());
System.out.println(now.getValue());
}

/_ 仅仅遍历 Map 映射的 Key 键 _/
for (Integer now : dic.keySet()) {
System.out.println(now);
}

/_ 仅仅遍历 Map 映射的 Value 值 _/
for (Integer now : dic.values()) {
System.out.println(now);
}

• ForEach 方法只能用于 JDK 5 之后的版本，并且在遍历之前必须检查 Map 是否为空，避免遍历空 Map 抛出 NullPointerException 异常

/_ 使用 Iterator 方法， 可以在遍历的时候通过迭代器删除元素(it.remove()) _/

/_ 使用泛型 _/
Map<Integer, Integer> dic = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> it = dic.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Integer, Integer> now = it.next();
System.out.println(now.getKey());
System.out.println(now.getValue());
}

/_ 不使用泛型 _/
Map dic = new HashMap();
Iterator it = dic.entrySet().iterator();
while(now.hasNext()) {
Map.Entry now = (Map.Entry) it.next();
Iterator key = (Iterator) now.getKey();
Iterator value = (Iterator) now.getValue();
System.out.println(key);
}

• 下面这种方法效率太低，不建议使用

Map<Integer, Integer> dic = new HashMap<Integer, Integer>();
for(Integer key : map.keySet()) {
Integer value = map.get(key);
}

• HashMap 的排序，使用 Collections 的 sort 或者自身 List 的 sort

  • sort 需要传入一个自定义的 Comparator 参数，重载其 compare 方法，根据返回值正负实现比较排序， Comparator 的类型是需要比较的类型
  • 根据 key 进行比较可以只传一个类型，但是对于 value 排序必须先将其转换为 ArrayList，Comparator 使用 Map.Entry<>类型

Map<String, Integer> dic = new HashMap<>(16);
List<Map.Entry<String, Integer>> dicList = new ArrayList<>(dic.entrySet());
// Collections.sort(dicList, new Comparator<Map.Entry<String, Integer>>() {
dicList.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2){
return -o1.getValue() + o2.getValue();
}
});

• TreeMap 的排序可以在一开始就指定，在 new 的时候默认参数写入一个 Comparator 即可，与上文类似

Method

Description

put(K key, V value)

创建 key 到 value 的映射

get(Object key)

返回指定键的值，不存在返回 null

size()

返回映射的个数

keySet()

返回此映射中包含的所有键的 set 视图

values()

返回映射中包含键的 Collection 视图

remove(Object key)

如果映射中包含映射，则删除

hashCode()

返回哈希码

Set

• Set 内部保证不含有重复元素，但是储存时无序的，判断重复根据的是 equals 方法，空元素也至多有一个
• Set 的方法继承自 Collection，但是增加了禁止元素重复和
• HashSet 基于哈希表，实际上是维护了一个 HashMap

• 默认认为同一个对象的所有引用都是相同的元素，但是如果想要使得两个不同的元素某种情况下相等，就必须重写 hashCode（hashCode 一般默认是根据对象的内存地址计算出来的） 和 equals 方法

  • 如果调用 hashCode 返回结果相同但是 equals 返回 false，Set 也会加入元素，此时元素的 hashCode 依然相同，但是会在此哈希值下继续储存，放在一个该哈希值的集合中
  • 如果调用 hashCode 放回结果是不同的，则 Set 认为无论如何而这不可能相等

Queue

• 主要是优先队列，一般基于最大最小堆实现，可以实现根据优先级高低进行取值访问
• 在使用时，尽量使用 offer 来加入元素，使用 poll 来获取首元素，避免 add 和 remove 方法错误时抛出异常
• LinkedList 实现了 Queue 的接口，因此可以使用 Queue 来 new LinkedList

排序接口 Comparator

• 可以作为参数被传递到 Collection.sort 和 Arrays.sort 方法中，也可以传入某些数据结构中，控制排序
• 与 equals 一致的排序：compare(e1, e2) == 0 与 e1.equals(e2) 的真假相同时，Comparator 进行的排序
• 一个参数需要 Override 的是 compare，用来比较排序的两个参数，另一个是 equals