Java集合

集合

集合

集合与数组

定义：集合与数组都是对多个数据进行存储操作的结构，简称Java容器

数组存储的特点：一旦初始化以后，其长度就确定了；数组一旦定义好，其元素的类型也确定了

数组存储的缺点：长度不可修改；数组中提供的方法很有限

集合的分类

集合框架
- Collection接口：单列集合，用来存储一个一个的对象
  - List接口：存储有序，可重复的数据（类似“动态”数组）–ArrayList、LinkedList、Vector
  - Set接口：存储无序，不可重复的数据（类似高中“集合”）–HashSet、LinkedHashSet、TreeSet
- Map接口

Collection接口

遍历Collection元素的方法：

1. 迭代器接口：Iterator

public void test(){
  Collection collection = new ArrayList();
  collection.add(123456);
  Iterator iterator = collection.iterator();
  // 判断是否还有下一个元素
  while (iterator.hasNext()){
    System.out.println(iterator.next());
  }
}

2. foreach（内部仍然调用了迭代器）

//for(集合元素类型 局部变量：集合对象)
for(Object obj:collection){
  System.out.println(obj);
}

Collection子接口：List

存储有序的，可重复的数据

ArrayList：List接口的主要实现类，线程不安全，效率高；底层使用Object[] elementData存储
LinkedList：对于频繁地插入删除操作，使用此类的效率比ArrayList高，底层使用双向链表存储
Vector：List接口的古老实现类，线程安全，效率低，底层使用Object[] elementData存储

常用方法：

增：add(Object obj)

删：remove(int index)/remove(Object obj)

改：set(int index,Object element)

查：get(int index)

插：add(int index, Object element)

长度：size()

遍历：Iterator迭代器、foreach、普通循环

存储元素的要求：添加的对象，所在的类要重写equals（）方法

Collection子接口：Set

存储无序的，不可重复的数据

以HashSet为例

无序性：不等于随机性，存储的数据在底层数组中并非按照索引的顺序添加，而是根据数据的哈希值确定的

不可重复性：保证添加的元素按照equals（）判断时，不能返回true，即相同的元素只能添加一个

元素添加过程：

1.向HashSet中添加元素a，首先调用元素a所在类的hashcode（），计算a的哈希值，此哈希值接着通过某种算法计算出HashSet底层数组中的存放位置
2.判断数组此位置上是否已有元素
- 2.1 没有元素，则元素a添加成功（情况一）
- 2.2 有元素b，则比较元素a和元素b的哈希值
  - 2.2.1 如果hash值不同，则a添加成功（情况二）
  - 2.2.2 如果hash值相同，调用a所在类的equals（）
    - 2.2.2.1 equals（）返回true，a添加失败
    - 2.2.2.2 equals（）返回false，a添加成功（情况三）

情况二和情况三：

jdk7：元素a放到数组中，指向原来的元素

jdk8：原来的元素在数组中不变，指向a

HashSet底层：数组+链表（jdk7）

分类：

HashSet：Set接口的主要实现类，线程不安全的，可以存储null值
LinkedHashSet：HashSet的子类
- 遍历其内部数据时，可以按照添加的顺序遍历（因为在添加数据的同时，每个数据会维护两个引用，分别记录前后的两个数据）
- 对于频繁的遍历操作，LinkedHashSet效率高于HashSet
TreeSet：可以按照添加对象的指定属性，进行排序。底层是红黑树，与排序相关，应用到Comparable

存储对象所在类的要求：

HashSet/LinkedHashSet：向Set中添加的数据，其所在的类一定要重写hashCode（）和equals（）

Map接口

双列数据，存储key-value对的数据

分类：

HashMap：Map的主要实现类，线程不安全，效率高，可以存储null的key，value
LinkedHashMap：HashMap的子类。
- 保证在遍历map元素时，可以按照添加的顺序实现遍历（因为在原HashMap的基础上，添加了一对指针，指向前一个元素和后一个元素）
- 对于频繁的遍历操作，效率高于HashMap
TreeMap：保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用红黑树
HashTable：古老的Map实现类，线程安全，效率低，不能存储null的key或value
Properties：HashTable子类，常用来处理配置文件。key和value都是String类型

HashMap的底层：

数组+链表（jdk7）

数组+链表+红黑树（jdk8）

HashMap的实现原理

一、在jdk7中的实现原理

HashMap map = new HashMap();

在实例化以后，底层创建了长度为16的一维数组Entry[] table

map.put(key1,value1);

Map.put(key2,value2);…

首先调用key1所在类的hashCode（）计算key1的hash值，此hash值经过某种算法计算以后，得到在Entry[]中的存放位置

1 如果此位置上的数据为空，则key1-value1添加成功
2 如果此位置上的数据不为空，则比较key1与其他数据的hash值
- 2.1 key1的hash值与其他数据的hash值不同，则添加成功
- 2.2 key1的hash值与其他数据的hash值相同，则继续比较equals（）
  - 2.2.1 返回false，key1-value1添加成功
  - 2.2.2 返回true，value1替换value x

二、HashMap在jdk8相比于jdk7的不同

new HashMap（）：底层没有创建长度为16的数组
jdk8底层的数组是：Node[]，而不是Entry[]
首次调用put（），底层创建长度为16的数组
七上八下

Collections工具类

作用：操作Collection和Map的工具类