前言

前面我们保存大量数据时，首先会想到数组。但数组长度是固定的，如果保存数量不确定的数据时就存在问题了。本文将带大家了解Java集合框架的体系结构，掌握List、Set、Map接口的区别，重点掌握ArrayList、LinkedList、HashSet、HashMap这几个集合的用法、数据结构和实现原理。

集合框架体系

接口特点：

• Collection接口定义了集合的通用方法，如：添加、删除、集合个数
• List接口可以排序、可以添加重复的数据
• Set接口不能单独访问，数据不能重复
• Map接口键值对，通过键访问

Collection接口的主要方法：

List接口

可以通过下标操作，可以添加重复数据，可以排序主要方法：

ArrayList类

ArrayList类是List接口的实现类，是开发时使用非常多的一种集合。ArrayList的数据结构是：一维数组

ArrayList的优缺点：

• 优点：访问速度快，存储空间是连续的，通过下标直接定位
• 缺点：删除和插入性能差，需要向前或向后移动大量数据

创建方法：

ArrayList arrayList = new ArrayList();

或

ArrayList arrayList = new ArrayList(默认容量);

添加数据：

add(Object 数据)				添加数据到末尾，参数是Object类型，可以添加任何类型的数据。
add(int 下标,Object 数据)	在特定位置添加数据
addAll(Collection 集合）		添加一个集合中所有数据

修改数据：

set(int 下标,Object 数据)		修改特定位置上数据

访问数据：

get(下标）				返回某个下标上的数据

数据个数：

int size()				数据个数

删除数据：

remove(int 下标)			删除特定位置上的数据
clear()					删除所有数据

遍历集合：foreach循环

for(Object obj : list){
	System.out.println("集合中的数据："+obj);
}

普通for循环

int size = list.size();
for(int i = 0;i < size;i++){
	Object obj = list.get(i);
	System.out.println("集合中的数据："+obj);
}

ArrayList源码解析：

问题1：如何保存数据？Object类型的一维数组

transient Object[] elementData;

问题2：数组初始长度是多少？10

private static final int DEFAULT_CAPACITY = 10;

问题3：ArrayList是如何动态扩容的？

如果数据的个数超过原来的容量，就将容量扩展为原来的1.5倍，然后复制数据到新数组中。

private void grow(int minCapacity) {
     // overflow-conscious code
     int oldCapacity = elementData.length;
     int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容1.5倍
     if (newCapacity - minCapacity < 0)
         newCapacity = minCapacity;
     if (newCapacity - MAX_ARRAY_SIZE > 0)
         newCapacity = hugeCapacity(minCapacity);
     // minCapacity is usually close to size, so this is a win:
     elementData = Arrays.copyOf(elementData, newCapacity); //复制数据到新数组中
}

Vector集合

Vector集合与ArrayList相似：

1. 数据结构都是一维数组
2. 方法完全相同

不同点：

1. ArrayList是非线程安全，Vector是线程安全
2. ArrayList性能更高

泛型集合

下面代码可能出现什么问题?

List list = new ArrayList();
list.add(100);
list.add("123");
int n = (int)list.get(1); //存在类型转换的错误
String s = (String)list.get(0); //存在类型转换的错误

非泛型的集合，添加数据的类型没有限制，在取出数据进行类型转换时，存在类型不兼容的问题。

使用泛型集合，就能解决这个问题。

创建方法：

ArrayList<类型> arrayList = new ArrayList<类型>();

例如：

ArrayList<String> arrayList = new ArrayList<String>();
ArrayList<Integer> arrayList = new ArrayList<Integer>();
后面的类型可以省略
ArrayList<Integer> arrayList = new ArrayList<>(); 

优点：

1. 只能添加一种类型的数据，不容易出错
2. 读取数据后不用类型转换，方便

ArrayList<Person> arrList = new ArrayList<Person>();
arrList.add(new Person("张三",20));
arrList.add(new Person("张大三",21));
arrList.add(new Person("张小三",23));
arrList.add(new Person("张三三",26));
arrList.add(100);  //编译错误，不允许添加其他类型
//读取Person对象
Person person = arrList.get(3);
person.hello();
//删除
arrList.remove(0);
//遍历
for(Person per : arrList){
	per.hello();
}

LinkedList

LinkedList的数据结构是：双向链表

LinkedList的优缺点：

• 优点：删除和插入速度快，只需要修改前后的指向，不需要移动数据
• 缺点：访问速度慢，需要依次向前向后，效率低。

LinkedList的方法

LinkedList源码探究

//内部类，保存数据和前后指针
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

插入元素

//在succ节点前，插入新节点
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;  	//succ前一个节点
    //创建新节点，prev指向succ前面节点，next指向succ
    final Node<E> newNode = new Node<>(pred, e, succ); 
    succ.prev = newNode;     		//succ的prev指向新节点
    if (pred == null)
        first = newNode;  		 		//前面没有节点，新节点就是首节点
    else
        pred.next = newNode;  		//否则succ前面节点的next指向新节点
    size++;									//数量加1
    modCount++;
}

插入元素

//删除x节点
E unlink(Node<E> x) {
     final E element = x.item;
     final Node<E> next = x.next;
     final Node<E> prev = x.prev;
     if (prev == null) {       //x前面节点的next指向x节点的后面节点
         first = next;
     } else {
         prev.next = next;
         x.prev = null;
     }
     if (next == null) {       //x后面节点的prev指向x节点的前面节点
         last = prev;
     } else {
         next.prev = prev;
         x.next = null;
     }
     x.item = null;
     size--;
     modCount++;
     return element;
 }

Set接口

Set不能添加重复的数据，里面的数据也不能单独访问

Set接口的常用实现类有：

• HashSet 无序的Set
• TreeSet 会自动排序的Set
• LinkedHashSet 可以保留添加顺序的Set

HashSet

无序，以哈希算法计算保存位置添加到集合中的数据必须实现hashCode和equals方法底层实现是HashMap，数据都是存到HashMap的键中

public class HashSet<E> extends AbstractSet<E>{
   
    private transient HashMap<E,Object> map;
	private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    ...
}

Map接口

键值对结构存取数据，查找方便而且高效常用方法：

HashMap

以哈希表方式存取数据，是使用非常多的集合。创建方法：

HashMap<键类型,值类型> hashmap = new HashMap<>();

使用方法:

//创建HashMap保存人的对象
HashMap<String,Person> map = new HashMap<String,Person>();
Person person1 = new Person("张三",20);
Person person2 = new Person("李四",22);
Person person3 = new Person("王五",20);
//添加人到集合中
map.put(person1.getName(), person1);
map.put(person2.getName(), person2);
map.put(person3.getName(), person3);
//通过键访问值
map.get("张三").hello();
//删除
map.remove("李四");
//添加重复的键,将新的值覆盖原来的值
map.put("李四", new Person("李四",33));
System.out.println("长度：" + map.size());
//遍历所有的键
for(String key : map.keySet()){
	System.out.println("键： " + key);
}
//遍历所有的值
for(Person per : map.values()){
	per.hello();
}
//遍历所有的键和值
for(String key : map.keySet()){
	System.out.println("键： " + key);
	map.get(key).hello();
}

HashMap的特点

1. 如果添加了重复的键，后面添加的值会替换前面的值。
2. 数据是用哈希算法计算存储位置，不是添加顺序
3. 添加的键必须实现hashCode和equals方法

HashMap的数据结构一维数组 + 单向链表 + 红黑树

HashMap保存数据的过程

1. 添加键值对数据时，首先会调用键的hashCode方法，计算出数组下标
2. 如果该下标上的数据为空，就直接存入数据
3. 如果该下标上存在数据，就调用键的equals和该位置上的键进行比较
4. 如果equals返回true，就用新的数据将旧的数据覆盖掉
5. 如果equals返回false，将新的数据放在旧的数据后面，就形成链表
6. 当链表的长度超过8，自动转换为红黑树（java8的优化）

HashMap源码解析

//添加数据
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;                  // 获得数组长度
  if ((p = tab[i = (n - 1) & hash]) == null)     //hashCode对数组长度-1取模获得下标i
      tab[i] = newNode(hash, key, value, null);   //该位置为空就直接添加数据
  else {
      Node<K,V> e; K k;
      if (p.hash == hash &&
          ((k = p.key) == key || (key != null && key.equals(k))))  //不为空就调用equals比较键
          e = p;																				 //键相同就赋值给e，后面直接覆盖value
      else if (p instanceof TreeNode)
          e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      else {
          for (int binCount = 0; ; ++binCount) {
              if ((e = p.next) == null) {
                  p.next = newNode(hash, key, value, null);  //键不相同就放到后面，形成链表
                  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st    
                      treeifyBin(tab, hash);	   //链表长度超过8，转换为红黑树
                  break;
              }
              if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
                  break;
              p = e;
          }
      }
      if (e != null) { // existing mapping for key
          V oldValue = e.value;
          if (!onlyIfAbsent || oldValue == null)
              e.value = value;        //覆盖旧的value
          afterNodeAccess(e);
          return oldValue;
      }
  }
  ++modCount;
  if (++size > threshold)
      resize();
  afterNodeInsertion(evict);
  return null;
}

Hashtable

Hashtable和HashMap的用法和结构相同区别：

1. HashMap非线程安全，Hashtable是线程安全的
2. HashMap可以添加null的键和值，Hashtable不能添加null键和值

TreeMap

特点：添加数据后，会自动对键进行排序数据结构：红黑树

使用时需要注意：

1. 键必须实现Comparable接口
2. 键如果和已存在的键相等，TreeMap就放弃添加

LinkedHashMap

继承于HashMap，通过额外的链表保留键的添加顺序。

如何选择集合

在开发过程中，需要根据实际业务场景，结合集合的特点选择集合

• 可以排序，可以添加重复数据，可以随机访问 ----- List
• 对数据访问要求高 ----- ArrayList
• 对插入和删除要求高 ----- LinkedList
• 不能添加重复的数据，不需要随机访问 ------ Set
• 没有顺序 ----- HashSet
• 可以进行排序 ----- TreeSet
• 保留添加顺序 ----- LinkedHashSet
• 可以进行快速查找 ，以键值对保存------ Map
• 键没有顺序 ----- HashMap
• 键可以排序 ----- TreeMap
• 键保留添加顺序 ----- LinkedHashMap