集合框架的介绍
集合就是用于存储对象的容器。 只要是对象类型就可以存进集合框架中。集合的长度是可变的。 集合中不可以存储基本数据类型的值 。
集合和数组的区别
数组和集合相比，数组的长度是固定的，没有办法动态扩展。二集合存储数据时是没有长度限制的，可以动态扩展。基于数组 根据不同的数据结构 创建了多个类 而这些类统称 为集合框架。
1.集合的框架
2.为什么使用集合
手撕可变长度的容器。
public class MyArray {
private Object[] arr; //声明一个Object类型的数组
private int size; //声明数组的下标
public MyArray(){ //无参构造函数
this(3);
}
public MyArray(int initSize){ //有参构造函数
if(initSize<0){ //长度不合法
throw new ArrayIndexOutOfBoundsException("数组长度有误");
}
arr = new Object[initSize];
}
public void setData(Object o){
if(size>=arr.length){ //判断数组是否已满
arr = Arrays.copyOf(arr,size*2); //扩容
}
arr[size] = o;
size++;
}
public Object getData(int index){ //根据下标获取数组中的元素
if(index>=size){
throw new ArrayIndexOutOfBoundsException("下标越界");
}
return arr[index];
}
}
3.List集合
List:----->它是一个接口，该集合中的元素可以重复，而且是有序的(有下标)。
ArrayList--->它的底层是数组结构，它的查询效率高，但是它的添加和删除效率低--因为它要牵涉到数据的迁移。
常见方法: add();size();indexOf(); contains(); get();remove();isEmpty();
LinkedList--->底层双向链表结构，它增加和删除效率高，但是它的查询效率低。
常见的方法: 它的方法和ArrayList中的方法比较相似，它也有自己特有的方法:
addFirst() addLast() getFirst() getLast()
4. ArrayList集合
4.1 创建集合对象
List list = new ArrayList(); //创建一个集合对象 如果没有指定集合容器的长度默认为10
List list3 = new ArrayList(12);4.2添加的操作
//添加任意类型
list.add("java01");
list.add("java02");
list.add(12);
list.add(3.4);
list.add(new Date());
System.out.println(list);
list.add(2,"Hello"); //下标为2的位置添加元素
List list2 =new ArrayList();
list2.add("a");
list2.add("b");
list.addAll(list2); //添加多个元素 把list2中的每个元素一一添加到list中
System.out.println(list);4.3 删除的操作
/删除操作
list.remove(1); //移除下标为2的元素
list.clear(); //清空集合中的元素4.4修改的操作
//修改操作
list.set(1,"孙悟空");
System.out.println(list);4.5查询的操作
//查询操作
Object o = list.get(1); //根据下标获取元素
System.out.println(0);
int size = list.size(); //获取集合元素的个数
System.out.println(size);
boolean f = list.contains("java03"); //判断元素是否在集合中
System.out.println(f);
int index = list.indexOf(12); //查询元素在集合中第一次出现的次数
System.out.println(index);
System.out.println(list);4.6ArrayList底层代码
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { //大于0
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { //等于初始化为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else { //抛出一个异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
==========add("java01")======E理解为Object类型================
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 扩容
elementData[size++] = e; //把元素赋值给数组的相应位置
return true;
}
==========indexOf("java02") 判断元素在集合中第一次的位置=============
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i])) //和数组中的每个元素内容进行比对
return i; //返回元素在集合中位置
}
return -1;
}
===========size() 请求数组的长度======================
public int size() {
return size;
}
============contain("java05")判断元素是否在集合中==============
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
===============get(1) 获取指定位置的元素========
public E get(int index) {
rangeCheck(index); //判断指定的位置是否合法
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
============toString() 为什么不打印对象的引用地址
[java01, java02, java03, java02]因为重写了Object里面的toString方法。
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
} 通过对ArrayList方法的底层代码分析：底层就是对数组的操作。
ArrayList的底层就是基于数组实现的。
5.LIinkedList集合
它是一个链表结构。
5.1 添加
LinkedList linkedList = new LinkedList();
linkedList.add("java01"); //添加
linkedList.addFirst("java02"); //添加到头部
linkedList.addLast("java03"); //添加到尾部
linkedList.add("java04");
linkedList.add("java05");
linkedList.add("java06");
System.out.println(linkedList);5.2删除操作
//删除操作
linkedList.removeFirst(); //移除头部元素
linkedList.removeLast(); //移除尾部元素
System.out.println(linkedList);5.3修改操作
//修改操作
linkedList.set(1,"java09");
System.out.println(linkedList);5.4查询操作
//查询操作
int size = linkedList.size(); //求长度
Boolean empty = linkedList.isEmpty(); //是否为空
System.out.println(empty);
Boolean f = linkedList.contains("java05"); //判断元素是否在集合中
System.out.println(f);
Object first = linkedList.getFirst(); //获取第一个元素
System.out.println(first);
Object last = linkedList.getLast(); //获取最后一个元素5.5LinkedList的底层源码
1.凡是查询源码 ，我们都是从类的构造方法入手:
/**
* Constructs an empty list.
*/
public LinkedList() {
}
该类的构造方法内是空的，没有任何的代码。 但是该类中有三个属性。
transient int size = 0; //索引
transient Node<E> first; //第一个元素对象
transient Node<E> last; //表示最后一个元素对象。
================ add的源码=====E:理解为Object类型==========================。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
//上一个节点 数据 下一个节点
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
==================Node的源码 内部类=======================================
private static class Node<E> { //<E>泛型--object
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;
}
}1、==================== get(1)-----获取元素========================
public E get(int index) {
checkElementIndex(index); //检查index下标是否正确。
return node(index).item; //李四Node对象
}
========================node(index)=============================
Node<E> node(int index) {
//>> 位运算二进制运算 ----- size >> 1 一半的意思size/2
if (index < (size >> 1)) { //前半部分
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //后半部分
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}LinkedList查询效率低。因为它要一个节点一个节点的往后找。
6.Set集合
7.HashSet集合
7.1创建HashSet对象
HashSet hashSet = new HashSet();
HashSet hashSet1 = new HashSet(12);//初始容器的大小
//loadFactor:--->0.7f 表示负载因子 当空间使用70%时 要求扩容
HashSet hashSet2 = new HashSet(10,0.7f);7.2添加操作
hashSet.add("java01");
hashSet.add("java02");
hashSet.add("java05");
hashSet.add("java03");
hashSet.add("java04");
hashSet.add("java03");
HashSet hashSet1 = new HashSet();
hashSet1.add("孙悟空");
hashSet1.add("猪八戒");
hashSet1.add("沙悟净");
hashSet.addAll(hashSet1);
System.out.println(hashSet);7.3删除操作
//删除操作
hashSet.remove("java02");
hashSet.clear();//清空容器集合
System.out.println(hashSet);7.4修改操作
//修改操作
boolean f = hashSet.isEmpty(); //判断是否为空
System.out.println(f);
boolean f2 = hashSet.contains("java04"); //判断是否在集合中
System.out.println(f2);7.5HashSet遍历
//for each遍历
for(Object o:hashSet){
System.out.println(o);
}
//迭代器遍历
Iterator iterator = hashSet.iterator(); //获取迭代器对象 有序：有下表
while (iterator.hasNext()){ //判断是否指针能够移动
Object next = iterator.next(); //指针移动并获取当前的元素
System.out.println(next);
}8.TreeSet集合
TreeSet中的方法和HashSet中的方法一模一样 只是他们的实现不一样。
TreeSet 基于TreeMap 实现。TreeSet可以实现有序集合，但是有序性需要通过比较器实现。
8.1添加操作
TreeSet treeSet = new TreeSet();
treeSet.add("java01");
treeSet.add("java02");
treeSet.add("java03");
treeSet.add("java04");
treeSet.add("java05");
System.out.println(treeSet);存储一个对象类型:
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add(new Student("孙悟空", 35));
treeSet.add(new Student("猪八戒", 32));
treeSet.add(new Student("沙悟净", 21));
treeSet.add(new Student("唐僧", 21));
System.out.println(treeSet);
}通过运行我们发现出现错误:
发现: TreeSet中的元素必须实现Comparable接口 方可放入TreeSet
解决办法有: 让你的类实现Comparable接口
public static void main(String[] args) {
TreeSet treeSet = new TreeSet();
treeSet.add(new Student("孙悟空", 35));
treeSet.add(new Student("猪八戒", 32));
treeSet.add(new Student("沙悟净", 21));
treeSet.add(new Student("唐僧", 21));
System.out.println(treeSet);
}
}
class Student implements Comparable{
private String name;
private Integer age;
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
public Student(String name, Integer age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
//排序：---返回如果大于0 表示当前元素比o大 如果返回-1 当前添加的元素比o小 返回0表示相同元素。
@Override
public int compareTo(Object o){
Student student = (Student) o;
//System.out.println(this+"======"+o);
if(this.age>student.age){
return 1;
}
if(this.age<student.age){
return -1;
}
return 0;
}9.Map属于键值对模式
9.1如何创建Map对象
Map map = new HashMap(); // 默认初始化大小为16，负载因子为0.75
Map map1 = new HashMap(13);
Map map2 = new HashMap(15,07f);9.2添加操作
//添加操作 key:name value:张三
map.put("name","张三"); //注意：要求map的key必须唯一
map.put("age",24);
map.put("name","李四"); //因为key不能重复，所以或者会把前者覆盖
System.out.println(map);
Map m1= new HashMap();
m1.put("s1","aaa");
m1.put("s2","bbb");
m1.put("s3","ccc");
map.putAll(m1);
System.out.println(map);
map.putIfAbsent("age2",21); //如果指定key值存在，则不放入map中,如果不存在则放入map中
System.out.println(map);9.3删除操作
//删除操作
map.remove("age");
System.out.println(map);
map.clear();9.4修改操作
//修改操作
map.replace("name","王五");
System.out.println(map);9.5查询操作
//查询操作
boolean f = map.containsKey("s1"); //判断map是否存在指定的key
System.out.println(f);
Object v = map.get("s3"); //根据指定的key获取对应的value值
System.out.println(v);
Set keys = map.keySet(); //返回该map中所有的key值
System.out.println(keys);
//遍历map
for(Object k:keys){
Object value = map.get(k);
System.out.println(k+"===="+value);
}9. 6HashMap实现类
HashMap实现了Map接口，拥有Map接口的基本特点。HashMap线程不安全，效率高。HashMap的底层是由哈希表、链表加红黑树构成的。
Map接口特点:
- 以键值对方式存储数据（Collection是单值集合）
- 键不能重复，键重复时，后面的数据会覆盖前面的数据
- 可以存储null
- 键值对数据无序
9.7HaspMap底层原理
JDK1.8 HashMap原理
Hashmap得原理，存储元素使用得put(key,value)，根据key得hash计算出相应得哈希值，根据相应得算法求出该元素在数组中得位置， 如果求出得哈希值相同，则称为哈希冲突，会根据equals来判断元素是否一致，如果equals不同，则存入单向链表上， 如果哈希碰撞得个数超过8个，则把链表转换为红黑二叉树。
JDK1.7和JDK1.8 HashMap得区别。
JDK1.7使用得数据结构: 数组+链表 而且链表插入模式为头部插入（造成死循环）。
JDk1.8使用得数据结构: 数组+链表+红黑树 而且链表得插入模式为尾部插入。
HashMap的put()和get()的实现
1) map.put(key,value)实现原理
第一步：首先将k,v封装到Node对象当中（节点）。
第二步：它的底层会调用K的hashCode()方法得出hash值。
第三步：通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equals。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
2) map.get(key) 实现原理
第一步：先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
底层代码
从构造函数入口:
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
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)
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))))
//如果key得hash值相同，判断key得equals是否相同，替换原来得元素
e = p;
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);
// 判断链表得长度是否超过8个
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 把链表转换为红黑树结构
treeifyBin(tab, hash);
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;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}10.泛型
泛型：对要管理的数据进行类型限定，方便数据的处理。
为什么实用泛型:
我们原来在定义集合时，是如下得定义方式：
List list=new ArrayList();//该集合没有使用泛型
list.add("java01");
list.add("java02");
String str= (String) list.get(0);//获取元素 需要进行强制类型转换
System.out.println(str);
获取元素时，不方便对元素进行相应得其他操作。
在往集合中存储数据的时候缺乏类型检查，不安全
泛型：类型检查机制；
好处：省略了装箱和拆箱，效率高；类型安全。
语法:
Plain Text
List<E>:E类型约束
Set<E> : E类型约束
Map<K,V>:K,V类型约束
泛型类：针对类中的属性限定类型。在具体使用的时候设置类型
10.1如何使用泛型
List<String> list = new ArrayList<>(); //限制了集合中每个元素的类型
list.add("Hello"); //集合中只能添加String类型
list.add("java");
String s = list.get(1); //在获取元素时，默认就是相应的数据类型，无需再进行转换
//<k,v>:K：表示键的泛型，V:表示值的泛型
HashMap<String,Integer> map = new HashMap<>();
map.put("name",24);
map.put("age",12);
Set<String> keys = map.keySet();
System.out.println(keys);10.2自定义泛型
public static void main(String[] args) {
Point<Integer> p1 = new Point<>(23,26);
Integer x = p1.getX();
Integer y = p1.getY();
System.out.println(x);
System.out.println(y);
p1.show();
}
}
class Point<T>{
private T x;
private T y;
public Point(T x, T y) {
this.x = x;
this.y = y;
}
public void show(){
System.out.println("x坐标为："+x+" y坐标为："+y);
}
public T getX() {
return x;
}
public void setX(T x) {
this.x = x;
}
public T getY() {
return y;
}
public void setY(T y) {
this.y = y;
}
}11.自定义链表
链表是最简单的动态数据结构，数据存储在节点(Node)中，其节点的数据结构如下：
Java
class Node{
E e;//数据存储的地方
Node next;//也是一个节点，他指向当前节点的下一个节点
}
我们可以把链表理解成为一个火车，每个链表，其实就是一节车厢，数据存储在车厢中中，而每个火车节都有一个指针，连接着下一个火车节。
链表有一个优点：
真正的动态数据结构，无需关系创建的空间是否过大，不需要像数据一样担心容量的问题。
缺点：
不能像数组那样，给一个索引就能查找到指定的值。
1.单向链表
单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。
2.单向循环链表
单向循环链表和单向列表的不同是，最后一个节点的next不是指向null，而是指向head节点，形成一个“环”。
3.双向链表
从名字就可以看出，双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null。
4.双向循环链表
双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。而LinkedList就是基于双向循环链表设计的。
因篇幅问题不能全部显示，请点此查看更多更全内容