集合.md

集合框架

1. Collection接口

该接口是所有集合的超类(父接口)

1.1 Collection派生出两个子接口：

Set集合	List集合
不重复集	可重复集
无序集	有序集

不重复：指的是Set集合中不能出现两个equals()比较为true的元素，数组不属于集合的范畴

1.2 Collection中常用的方法

• int size():返回集合中元素的数量
• boolean isEmpty():判断集合是否为空
• boolean contains(Object o):判断当前集合中是否包含给定的元素
• void clear():清空集合
• boolean add(E e):向集合中添加元素，添加成功返回true，否则返回false;
• boolean remove(Object o):从集合中删除给定的元素，删除成功返回true;
• boolean addAll(Collection c):将给定集合中的所有元素添加到当前集合;
• boolean removeAll(Collection c):删除当前集合中与给定集合相同的元素;
• boolean retainAll(Collection c):只保留当前集合中与给定集合相同的元素;
• Iterator iterator():返回用于遍历集合的迭代器

2. List集合(接口)

2.1 两个常用的实现类

• ArrayList():内部使用数组实现
• LinkedList():内部使用链表实现
• Vector:不常用

2.2 特有的方法

• Object[] toArray()：该方法用于将集合转换为数组
• Object get(int index)：获取给定下标的元素
• Object set(int index, Object o)：将集合中给定位置的元素替换为给定的元素，返回被替换的元素

3. Set集合

无序集、不重复集：Set集合中不会出现两个equals()比较为true的元素

3.1 Set集合的实现类

元素的存放位置与元素的Hash值有关

• TreeSet：使用二叉树实现（不常用）

• HashSet：使用散列算法实现的

  对于HashSet而言，存取元素时，依赖元素的hashCode()方法。hashCode()是Object类中的方法，所有的类都具备该方法。通常我们重写一个类的equals()方法时，要求一起重写hashCode()方法。

重写HashCode（）的注意事项：

Object类中的hashCode()值是与对象有关，即对象不同，那么hashCode值就不同。所以我们重写一个对象的的hashCode()方法后，才能将hashCode与该对象的属性建立起关系。

• hashCode()在被多次调用时，应当返回一个稳定的值，除非参与的equals()比较的属性发生改变
• 当两个对象equals()比较为true时，两个对象的hashCode()方法返回的hashCode值应该相同。
• 当两个对象equals()比较为false时，不要求hashCode()方法返回的结果不同，但是不相等的两个对象，使用不同的hashCode()会提高散列表的性能。

示例

// Element是我们自定义的类，其中尚未重写equals()和hashCode()方法
Element e1 = new Element(1);
Element e2 = new Element(1);
// 因为equals()是Object的，e1和e2是不同的对象，所以以下的结果都为false
System.out.println(e1.equals(e2));  // false
System.out.println(e1.hashCode() == e2.hashCode());  // false

// 当Element类中重写了equals()和hashCode()方法之后
// 因为重写了两个方法，那么hashCode()与属性相关了，所以以下结果都为true
System.out.println(e1.equals(e2));  // true
System.out.println(e1.hashCode() == e2.hashCode());  // true

/* 只重写equals()，不重写hashCode()，因为hashCode()是Object类的，只与对象有关，因为e1和e2不是同一个对象，那么hashCode()的结果就是不同的，但是equals()一样*/
System.out.println(e1.equals(e2));  // true
System.out.println(e1.hashCode() == e2.hashCode());  // false

4. Map(散列表)

是一个对多行两列的表格，每一行存储一项。一项包含两个部分：key-value(键值对)

• 容量：散列表中散列数组的大小（不能无限大）
• 散列运算：key->根据key计算散列值的算法（散列算法）
• 散列桶：散列值相同元素的线形集合
• 加载因子：是散列数组的加载率，一般小于75%，性能就比较理想(散列因子=元素数量/散列数组的大小)
• 散列查找：根据key计算散列值，再根据散列值的下标去查找value。
• 散列表中的key不同，value可以相同

4.1 HashMap

这是Map常见的实现类：使用散列算法实现的Map。

以键值对存储对象，关键字key是唯一的，不重复的。

1. 知识点

   • key可以是任意对象，value也可以是任意对象
   • key-value成对放置在集合中
   • 重复的Key算一个，重复添加时是替换操作
   • 根据key的散列值计算散列表，元素按照散列值排序（散列值是没有顺序的）
   • HashMap的默认容量是16，默认的加载因子是0.75
   • HashMap可以根据key检索查找value的值
   • HashMap可以在构造器中指定参数：初始容量和加载因子

2. 性能调优

   加载因子的比值如果超过0.75时，散列数组将扩容，存在原来数组中的数据，要重写进行散列运算之后存入新的数组，并不是简单的将原数组中数据复制到新数组中，这个过程称为rehash(重新散列)，那么将扩容数组。rehash会带来一定的性能开销。

3. Map的常用方法

   • V put(K k, V v)

     将一组key-value对存入Map，因为要求key不允许重复，所以若使用相同的key存入不同的元素，是替换操作, put的返回值返回的就是被替换的value

   • V get(Object k)

     根据给定的key获取对应的value，若给定的key不存在，则返回null。注意，若value的类型是8个基本类型的包装类时，接受返回值要针对null做处理，避免因为自动拆装箱而引发的空指针异常

   • boolean containsKey(Object k)

     查看map中是否包含key

   • boolean containsValue(Obect v)

     查看map中是否包含value

4.2 遍历Map的三种方式

• 遍历所有的key

  Set keySet()

• 遍历所有的value（较少情况）

  Collection values()

• 遍历每一字键值对

  Set entrySet()，每一组键值对使用一个Entry类的实例来描述。 Entry:要求定义两个泛型，来说明其描述的键值对中key和value的类型，通常我们使用Map的泛型

  Map<Integer, String> map = new HashMap<>();
  .....
  Set<Entry<Integer, String>> set = map.entrySet();
  for (Entry<Integer, String> entry : set){
      System.out.println(entry.getKey() + ": " + entry.getValue());
  }

4.3 HashTable

HashMap	HashTable
新	旧
速度快	速度慢
线程不安全	线程安全

5. 集合框架（Collection、Map）

集合框架包括集合和映射的子类

5.1 List集合

元素有序，有下标，可重复，继承自Collection接口，实现类ArrayList，LinkedList，Vector

5.2 Set集合

元素无序，不可重复，无下标，是真正意义上的数学里的集合，继承自Collection接口，实现类有HashSet（是一个只有key的HashMap），TreeSet

5.3 Collection

没有说明元素是否重复和有序，很少使用，是集合的超类（所有集合的父接口），通常直接使用其实现类。

Collections是集合的工具类，该类中定义了和集合相关的方法

5.4 Map

描述了成对放置的集合（key=value），key不能重复且无序，value可以重复，实现类有HashMap，HashTable，TreeMap(使用二叉树实现，其中key是有序的)

需要掌握：ArrayList、LinkedLinked、HashSet、HashMap。HashSet就是使用HashMap来实现的，它利用了HashMap对于key不允许重复的特点，以及散列算法的优点。

6. 泛型

java1.5之后推出的新特性

7. 迭代器

Iterator iterator(): 返回用于遍历集合的迭代器

Iterator是一个接口 不同的集合返回的迭代器实现不尽相同 注意：

• 使用迭代器遍历集合的顺序必须遵循：问取删（删除不是必须的）
  • 问：boolean hasNext() 该方法的作用是查看当前集合中是否还有元素可以遍历
  • 取：Object next() 从集合中取出一个元素
  • 删：void remove() 删除通过next()方法遍历出来的元素，删除的是集合中的元素。
• 迭代器在遍历过程中不允许通过集合的方法的来修改集合中的元素（包括增、删、改）
• 迭代器也可以有泛型，没有指定泛型的迭代器next()返回的是一个Object类型。指定的泛型要和原先集合的类型一致，那么next()返回的就是指定的泛型的类型

8. ArrayList和Vector的比较

ArrayList在java1.2版本以后采用了变长数组算法实现，线程不安全，效率高速度快。

Vector在java1.0版本以后，底层也是采用了变长算法实现，线程安全，效率比较低，实现了List接口，不常用

9. ArrayList和LinkedList比较

LinkedList采用双向链表的结构实现的，更适合频繁的增删操作

ArrayList采用变长数组算法实现的，更适合查询操作

10. 新循环

也叫增强for循环（for each） java 1.5之后推出的新特性

• 语法

  for (元素类型 e:集合或数组) {
  	循环体
  }

  新循环有别与传统循环，目的是简化遍历集合或者数组

  新循环就是通过迭代器实现的，Java在编译的时候，会将新循环转换为迭代器的方式，那么在使用新循环遍历过程中，就不能修改集合的内容(包括增删改)

11. 队列(Queue)

11.1 Queue（单向队列）

是一个接口，也是用来保存一组数据的，有别于数组和集合。队列存取元素必须遵循先进先出(FIFO)的原则。LinkedLinked具有存取效率高的特点，所以Java使用该类作为该类的实现类来使用。队列的遍历是一次性的，想要获取队列中的某一个元素，就必须将该队列中该元素之前所有的元素从队列中取出后才能使用和访问。

1. 相关方法()

   方法	描述
   boolean offer(E e)	向队列的末尾追加新元素，入队
   E poll()	获取并从队列中删除队首元素，出队
   E peek()	仅获取队首元素，但是不将其删除

2. 遍历

   若想控制循环系数，一定要保证循环条件参与的数据不能变化，否则不能控制循环次数，对于遍历集合或者队列，若循环中集合的元素会发生变化，那么我们应该“倒着循环”;

   // 倒着循环，这样遍历完之后，队列中就没有元素了
   for (int i = queue.size(); i > 0; i--){
       System.out.println(queue.poll());
   }
   // for-each,遍历完之后，元素还存在
   for (String str : queue){
       System.out.println(str);
   }

11.2 Deque（双端队列）

队列的两端都可以出队和入队。当我们使用双端队列存取元素时，只从一侧操作，就形成了一种存取模式（先进后出（FILO）），就形成了一种数据结构-----栈。使用栈是为了操作具有可追溯性，通常我们实现某个操作有后退动能，常使用栈。

1. 方法

   方法	描述
   void push(E e)	压栈
   E pull()	出栈
   E peek()	获取栈顶元素，但不删除
   E pop()	获取栈顶元素并删除

12. 集合排序

要比较，那么泛型所指的类必须要是可比较的。

12.1 Comparable接口

该接口是类默认的比较规则。

该接口的实现类是可比较的，实现该接口，必须要实现其中的一个方法

public interface Comparable {
	public int compareTo(T t);
}

• compareTo()的返回值是一个整数：

  返回的整数不关心具体的值是多少，关心的是取值范围。当返回值>0时，当前对象比给定对象大；当返回值<0时，当前对象比给定对象小；当返回值=0时，当前对象与给定对象相等。

• 使用方法

  List<String> list = new ArrayList<>();
  list.add("a");
  list.add("b");
  Collections.sort(list);

12.2 Comparator接口

用于定义临时的比较规则，不是默认的规则。

使用方法

• 创建一个类实现Comparator接口，重写方法compare()

class MyComparator implements<String>{
	@Override
	public int compare(String o1, String o2) {
		return o1.length()-o2.length();
	}
}

// 调用以下方法实现排序 Collections.sort(list, new MyComparator());

• 匿名内部类

  Collections.sort(list, new Comparator<String>(){
      @Override
  	public int compare(String o1, String o2) {
  		return o1.length()-o2.length();
  	}
  };)