超级重要的Java知识点详解集合框架

　　前言
　　前面我们保存大量数据时，首先会想到数组。但数组长度是固定的，如果保存数量不确定的数据时就存在问题了。本文将带大家了解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：数组初始长度是多少？10private 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相似：数据结构都是一维数组方法完全相同
　　不同点：ArrayList是非线程安全，Vector是线程安全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 arrayList = new ArrayList(); ArrayList arrayList = new ArrayList(); 后面的类型可以省略 ArrayList arrayList = new ArrayList<>();
　　优点：只能添加一种类型的数据，不容易出错读取数据后不用类型转换，方便ArrayList arrList = new ArrayList(); 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 item;     Node next;     Node prev;     Node(Node prev, E element, Node next) {         this.item = element;         this.next = next;         this.prev = prev;     } }
　　插入元素//在succ节点前，插入新节点 void linkBefore(E e, Node succ) {     final Node pred = succ.prev;  	//succ前一个节点     //创建新节点，prev指向succ前面节点，next指向succ     final Node 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 x) {      final E element = x.item;      final Node next = x.next;      final Node 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 无序的SetTreeSet 会自动排序的SetLinkedHashSet 可以保留添加顺序的SetHashSet
　　无序，以哈希算法计算保存位置添加到集合中的数据必须实现hashCode和equals方法底层实现是HashMap，数据都是存到HashMap的键中public class HashSet extends AbstractSet{         private transient HashMap 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 map = new HashMap(); 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的特点如果添加了重复的键，后面添加的值会替换前面的值。数据是用哈希算法计算存储位置，不是添加顺序添加的键必须实现hashCode和equals方法
　　HashMap的数据结构一维数组 + 单向链表 + 红黑树
　　HashMap保存数据的过程添加键值对数据时，首先会调用键的hashCode方法，计算出数组下标如果该下标上的数据为空，就直接存入数据如果该下标上存在数据，就调用键的equals和该位置上的键进行比较如果equals返回true，就用新的数据将旧的数据覆盖掉如果equals返回false，将新的数据放在旧的数据后面，就形成链表当链表的长度超过8，自动转换为红黑树（java8的优化）
　　HashMap源码解析//添加数据 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                    boolean evict) {   Node[] tab; Node 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 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)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的用法和结构相同区别：HashMap非线程安全，Hashtable是线程安全的HashMap可以添加null的键和值，Hashtable不能添加null键和值TreeMap
　　特点：添加数据后，会自动对键进行排序数据结构：红黑树
　　使用时需要注意：键必须实现Comparable接口键如果和已存在的键相等，TreeMap就放弃添加LinkedHashMap
　　继承于HashMap，通过额外的链表保留键的添加顺序。
　　如何选择集合
　　在开发过程中，需要根据实际业务场景，结合集合的特点选择集合可以排序，可以添加重复数据，可以随机访问 ----- List对数据访问要求高 ----- ArrayList对插入和删除要求高 ----- LinkedList不能添加重复的数据，不需要随机访问 ------ Set没有顺序 ----- HashSet可以进行排序 ----- TreeSet保留添加顺序 ----- LinkedHashSet可以进行快速查找 ，以键值对保存------ Map键没有顺序 ----- HashMap键可以排序 ----- TreeMap键保留添加顺序 ----- LinkedHashMap