JAVA学习第九天之集合

学习目的

  1. 了解集合的概念
  2. 掌握java集合的分类以及作用
  3. 掌握java集合的对象创建,以及常用方法的使用
  4. 熟悉java每一种集合的使用场景
  5. 掌握常见的集合ArrayList、LinkedList、HashSet 、TreeSet、HashMap、Properties、TreeMap
  6. 学会查看集合的底层源代码
  7. 掌握从集合底层的数据结构与实现来洞悉equals()方法与hashCode()方法的重写

一.集合

  1. Java 集合的继承结构体系
    主要分为两大类:Collection 和 Map。


    集合总结构图.png
子类 父类/接口 特点(源码实现)
Iterable 提供Iterator()方法,返回当前集合的迭代器对象
Collection Iterable Set、List集合的父类接口,以单个元素存储数据
List Collection 底层是数组,存取有序,元素可重复
ArrayList List 底层是数组,方便查找;非线程安全
LinkedList 底层是双向链表,方便插入和删除
Vector synchronized修饰,线程安全版本的ArrayList
Stack Vector 已弃用
Set Collection 底层是数组,存取无序,元素不可重复
HashSet Set 底层是HashMap,HashSet存入的元素 = HashMap的key部分;非线程安全
SortedSet 存取无序,元素不可重复,但存入的元素可以排序
TreeSet SortedSet 底层是TreeMap
- -
Map 以键值对key-value 形式存储数据,key部分 = set集合
Hashtable Map 底层是哈希表,synchronized修饰,线程安全
Properties Hashtable 底层是HashMap,key和value都只能存储字符串String形式的数据;线程安全
HashMap Map 底层是哈希表,线程不安全
SortedMap
TreeMap SortedMap 底层是二叉树,TreeMap的key可以自动按照大小排序
  1. 集合的主要常用类型
  • List:有序集合(存入顺序和取出顺序相同),可以存放重复的数据
  • Set:无序集合(存入顺序和取出顺序不同),不允许存放重复的数据
  • Map:无序集合,以键-值对形式存放数据。集合中包含一个键对象,一个值对象,键对象不允许重复,值对象可以重复。
  1. 集合与数据结构
    每一种集合在底层都对应着不同的数据结构,即每一种集合对数据的存储方式都不一样,因此效率和性能也不一样。不同的数据结构,数据存储方式不同。
  • 数组:ArrayList,Vector;有序,可重复,查询快;
  • 二叉树:TreeSet,TreeMap;无序,可排序;
  • 链表:LinkedList;无序,不可重复,增删快;
  • 哈希表:HashSet,HashMap,Hashtable;无序,不可重复,增删查询综合较快;
  • 图:Map;无序;
  • 数组+链表/树:HashSet,HashMap,综合数组、链表、树的特点;
  • 栈:Stack;已失效。
  1. 集合在程序中的应用


    集合与数据库数据的底层实现.png
  2. 集合的选择
  • 以单个方式存储元素:Collection及其子类;
  • 以键值对方式存储元素:Map及其子类;
  • 线程安全:Hashtable、Properties;
  • 非线程安全:ArrayList、HashSet、HashMap。
  1. 集合之间的转换
  • 查看每个集合底层的源码,查看构造方法,keySet()、entrySet()方法等。

1.1 Collection

  1. 概念
    Collection是集合层次结构中的根接口,是 List 和 Set 的父接口,LIst 和 Set都继承了Collection接口的属性和方法。而Collection同时也继承于Iterable接口,并且实现其Iterator()方法,该方法返回得到一个迭代器对象。通过迭代器对象,可以遍历所有的Collection集合中的元素。
  2. Collection体系继承结构


    Collection 集合继承结构图.png
  3. 性质特点
  • 单个元素存储:在Collection集合中,所有子类集合都是采用 **单个元素方式存储数据;
  • 存储地址:所有的Collection子集合存储的元素都是"内存地址",而不是元素本身,不管该元素是基本类型还是引用类型**。
  1. Collection 接口常用方法
  • Collection c = new LinkedList():面向接口编程,创建Collection对象;
  • int size() :返回集合中元素的总个数;
  • boolean isEmpty():判断集合是否为空,底层使用size属性==0判断;
  • boolean add(Object o):往集合中添加单个元素;
  • boolean remove(Object o):从集合中移除单个指定元素;
  • void clear():移除集合对象中的所有元素;
  • Object[] toArray() :将集合对象中所有元素返回为一个数组中;
  • boolean contains(Object o):判断集合中是否包含指定元素;
  • boolean equals(Object o):比较集合对象与指定对象o是否相等。
        //创建一个数组集合对象
        Collection c1 = new ArrayList();
        String s1 = new String("abc");
        String s2 = new String("efg");
        c1.add(s1);
        c1.add(s2);
        System.out.println(c1.size());//输出2
        String x = new String("abc");
        /*c1.add(x);//往集合c中添加重复元素 abc
        System.out.println(c1.size());//输出2
        System.out.println(c1.contains(x));//c集合中是否包含x:true
        /*
        ArrayList底层的contains(Object o)方法中又使用equals()方法
        o.equals(elementData[i]);//判断ArrayList是否已存在元素o
         */
contains方法内存解析.png
  • Iterator it = collection.iterator():最重要的方法,返回一个当前集合的迭代器,遍历当前集合;
//指定元素类型E的迭代器接口
Iterator<E> iterator() ;
//面向接口编程,创建Collection对象
Collection c = new ArrayList();
//创建一个可以在c对象上操作的迭代器对象
Iterator iter = c.iterator();

//迭代器遍历集合,若该集合有元素则输出
while (iter.hasNext()) {
          Integer v = (Integer)iter.next();//对集合c进行迭代遍历得到的元素类型 转型成 Integer类型
          System.out.println(v);
}
//for循环迭代器遍历集合,若该集合有元素则输出
for (Iterator iter1 = c.iterator() ; iter1.hasNext() ; ) {
          Integer v = (Integer)iter1.next();
          System.out.println(v);
}

1.1.1 List<列表>

  1. 概念
    List是一个有序接口,意为列表或序列。List底层是数组存储元素,因此可以根据数组下标,对List中的每个元素进行位置插入、访问、搜索等。List是一个存入和输出顺序相同、可以存放重复数据的Collection集合。
  2. 分类
  • ArrayList:数组列表,有序可重复,查询快;
  • LinkedList:链表,有序可重复,增删快;
  • Vector:向量,线程安全的ArrayList,但已被ArrayList淘汰;
  • Stack:栈,已被LinkedList淘汰。
  1. 特点
  • 可提供带下标索引的方法(底层是数组)
  • 有序:元素存入和取出是相同的顺序;
  • 可重复:可以加入重复的元素;
  • 默认在集合的末尾添加元素
        List list = new ArrayList();
        list.add(123);//在集合中添加元素,默认在集合末尾添加
        list.add(666);
        list.add("abc");
        list.add(123);
        list.add(88.88);
        //在集合指定下标处 添加指定元素
        list.add(4,999);
        //创建在c集合上的迭代器对象,并迭代遍历c的所有元素         
        for ( Iterator it  = list.iterator();it.hasNext();){
            Object o =  it.next();
            System.out.print(o + " ");//加入与输出的顺序:123 666 abc 123 999 88.88 
        }
        for (int i =0;i<list.size();i++){
            //根据下标对list集合进行遍历
            System.out.println(list.get(i));
        }
3.1.1.1 ArrayList
  1. 概念
    ArrayList是底层采用数组形式 的数据结构进行存储元素的集合,是一个可增长的数组,可以提供快速迭代和随机访问的能力。
  2. 特点
  • 末尾添加元素:ArrayList底层的源码方法规定,在数组列表的末尾添加元素;
  • 检索效率高:每个元素占用空间大小相同,内存地址连续的,知道首元素内存地址和下标,通过数学表达式计算出 元素的内存地址,因此检索效率最高;
  • 非线程安全:ArrayList底层的方法都是无synchronized修饰的;
  • 自动扩容:当ArrayList增加的元素过多,超出初始化的容量10时,会自动扩容,且每一次扩容是原来的1.5倍。
  1. 字段
  • int DEFAULT_CAPACITY = 10:创建一个初始默认容量为10的ArrayList对象;
  • Object[] EMPTY_ELEMENTDATA = {}:存储元素数据,初始为空元素数据容量的数组;
  • Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}:默认空元素数据容量-添加元素后,默认容量=10;
  • Object[] elementData:ArrarList底层实际用于存储元素的数组;
  1. 常用方法
    对于ArrayList常用的方法,可以到源码的java.util.ArrayList类中查看具体的实现,学会查看源码,理解源码。(其他类的常用方法亦如此)
//带参构造,创建并初始化指定容量大小的ArrayList对象
public ArrayList(int initialCapacity) {  
}
//无参构造,创建默认空元素数据容量的ArrayList对象,添加元素后,默认容量也=10
public ArrayList() {   
}
//返回数组长度-数组中元素的个数
public int size() {   
    return size;   
}
//判断数组是否为空
public boolean isEmpty() {   
    return size == 0;  
}
//判断数组是否包含指定元素--调用同类中的indexOf()方法
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
//返回指定元素在数组中-第一次出现的下标
public int indexOf(Object o) {
    }
//返回指定元素在数组中-最后一次出现的下标
 public int lastIndexOf(Object o) {
}
//复制一份该数组-浅克隆
public Object clone() {
}
//按顺序+指定长度,将ArrayList中所有的元素-使用数组返回
public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
//返回指定下标的元素
public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
//用指定的元素 替代 指定下标位置的元素
public E set(int index, E element) {
    }
//将指定的元素添加到尾部,此方法限定ArrayList的添加元素特点
public boolean add(E e) {
    }
//在ArrayList中指定位置添加元素
public void add(int index, E element) {
    }
//移除、删除指定下标位置的元素,返回该元素
public E remove(int index) {
    }
//删除指定下标位置的元素
public boolean remove(Object o) {
    }
//清楚列表中的所有元素,清空列表
public void clear() {
    }
//删除列表中指定 [ 范围)内的元素
protected void removeRange(int fromIndex, int toIndex) {
    }
3.1.1.2 LinkedList
  1. 概念
    LinkedList是底层采用 双向链表形式的数据结构存储元素,可以提供快速插入删除的能力。
  2. 特点
  • 增删容易:地址不连续,使用节点保存数据和下一个节点的地址,删除时不需要移动每一个节点元素;
  • 非线程安全:
  • 由节点组成,节点保存数据和内存地址
  1. 链表图解
  • 单链表


    单向链表.png
  • 双链表:LinkedList底层的实现原理就是双向链表,采用内部类-节点的形式


    双向链表.png
  1. 字段
  • int size = 0:初始化链表长度为0;
  • Node<E> first:前一个节点内存地址;
  • Node<E> last:后一个节点内存地址;
  • class Node<E>:静态内部类,静态内部节点。
  1. 常用方法
    LinkedList常用方法与ArrayList常用方法差不多,基本都是创建对象的构造器,往集合中加元素、删元素、和查元素等,可查看底层源码了解方法的具体实现
public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //静态内部类-节点    
    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;
        }
    }
    //无参构造
    public LinkedList() {
    }
    //带参构造
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    //LinkedList底层采用 双向链表 的实现原理    
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    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++;
    }
}
3.1.1.3 Vector(非重要)
  1. 概念
    Vector**底层采用数组形式 **的数据结构存储元素,意为向量,目前已极少使用。
  2. 特点
  • 效率慢<性能低>:使用synchronized关键字修饰,需要额外处理安全问题导致直接操作数据的效率低下;
  • 线程同步:Vector 中的方法都是使用synchronized关键字修饰的,是线程安全版本的ArrayList;
  • 自动扩容:当Vector增加的元素过多,超出初始化的10时,会自动扩容,且每一次扩容是原来的两倍。
  1. 字段
  • Object[] elementData:底层采用数组形式存储数据 ;
  • int elementCount:该集合的总元素个数;
  • int capacityIncrement:指定每次自动扩容的容量。
  1. 常用方法
public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //构造器,可以创建不同形式、不同容量的Vector对象    
    public Vector(int initialCapacity, int capacityIncrement) {  //指定初始化容量,且设定每次自动扩容的大小  
    }
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    public Vector() {
        this(10);
    }
    public Vector(Collection<? extends E> c) {
    }

    //自动扩容实现原理
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}
3.1.1.4 Stack(非重要)
  1. 概念
    继承 Vector接口 实现的一个栈,结构是后进先出,目前已经被 LinkedList 取代。

3.1.2 Set

  1. 概念
    Set的底层采用HashMap形式的数据结构存储元素的一个接口。是一个无序,不允许存放重复数据的集合。也是HashSet和TreeSet的父类接口。
  2. 特点
  • 无序:无序指的是元素存入和取出的顺序不同。HashMap底层采用的是哈希算法对元素进行存储,哈希算法本身就具有无序的特点(散列性);
  • 不允许重复:底层HashMap存储数据的形式是键值对,键key是无序且不允许重复的。而Set集合中存入元素 == HashMap中存key,因此Set集合与HashMap存储数据的特点是一样的。
  1. 常用方法
  • int size():获取set集合中元素的个数;
  • boolean isEmpty():判断集合是否为空,底层使用siz() == 0判断;
  • boolean contains(Object o):判断集合中是否包含指定元素o;
  • Iterator<E> iterator():产生一个在该set集合上的迭代器对象;
  • Object[] toArray():将set集合中所有的算数转换成数组输出;
  • boolean add(E e):往set集合中添加指定元素;
  • boolean remove(Object o):从set集合中移除指定元素;
  • void clear():清楚set集合中所有的元素;
  • boolean equals(Object o):判断指定对象是否与该set集合对象相等。
public interface Set<E> extends Collection<E> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();

    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();
}

3.1.2.2 HashSet
  1. 概念
    HashSet即Hash + Set,使用哈希算法存储数据的Set集合。HashSet 底层使用的是HashMap[]存储数据。HashSet 中的数据是无序的,不可存放重复的数据,原因同Set。
  2. 特点
  • 无序:数据存入顺序和读出顺序不相同,HashSet按照哈希算法存取数据,综合了数组和链表的特点,具有非常好的性能;
  • 不可重复数据:底层采用HashMap存储元素,存入的元素 == HashMap中的key,key不能重复。
  1. 工作原理
    当向 HashSet 中插入数据时,先调用对象的 hashCode() 方法得到该对象的哈希码,然后根据 哈希码 计算出该对象插入到集合中的位置。
  2. 代码解释
         //面向接口编程,创建一个HashSet对象          
         Collection c = new HashSet();
        //创建在c集合上的迭代器对象
        Iterator it ;
        c.add(123);//同理依次往Collection集合c中add():666 abc 456 new Object() 123 efg 456 88.88 efg
        c.add(666);
        //测试HashSet的无序(元素存入和取出是不同的顺序),以及不可重复(元素不能重复)
        for (it = c.iterator();it.hasNext();){
            Object o =  it.next();//迭代遍历c集合上的所有元素
            System.out.print(o + " ");
            //存入和输出顺序:abc efg 456 java.lang.Object@4554617c 666 88.88 123 
        }
3.1.2.3 SortedSet
  1. 概念
    SortedSet是一个继承于Set的接口,继承了Set接口的特性-无序,不可重复。但是存放到SortedSet集合中的元素<key部分>可以按照大到小的顺序自动排序,排序的元素需实现Comparable接口(重写compareTo()方法)或实现Comparator接口(重写compare()方法)。
3.1.2.4 TreeSet
  1. 概念
    TreeSet底层采用 TreeMap[ ]形式 的数据结构存储数据的集合,TreeMap底层又是二叉树(红黑二叉树)。TreeSet 是可以对 Set 集合<key部分> 进行自动排序的一种集合,默认自动升序<从小到大升序>,但不可存放重复的数据。
  2. 特点
  • 不可重复:因为TreeSet存入元素 = TreeMap的key,key不可重复;
  • 对排序的 Set集合的元素类型只能是一种类型排序。如:Set集合中元素是 int 类型时,不能加入 String字符串类型,否则将无法排序;
  • 无序,但可排序:无序指的是存入元素的顺序和取出来的顺序不一样,但是存入的元素会按照从小到大排序,也就是说排序后的顺序可能还是和存入的顺序不一样。
  1. 代码示例
public static void main(String[] args) {
        Set set = new TreeSet();
        set.add("a");//同理往set集合中add():aa d f bb c aa f
        //foreach增强循环遍历set集合
        for (Object s:set) {
            System.out.print(s + " ");//输出a aa bb c d f
        }
}
  1. 扩展
    TreeSet集合中添加自定义类型的元素,有两种方法:
  • 自定义类紧密实现Comparable接口,并重写其compareTo()方法,在方法内部写明比较规则。创建TreeSet集合时调用无参构造,初始化comparator对象为null。
        Person p1 = new Person();
        //构造器底层初始化Comparator对象为null
        TreeSet<Person> h = new TreeSet<>();
        h.add(p1);
//实现Comparable接口并重写compareTo()方法
class Person implements Comparable<Person>{
     public int compareTo(Person p) {  //比较规则 }
}
  • 自定义类分离实现Comparator接口,并重写其compare()方法,在方法内部写明比较规则。创建TreeSet集合时调用带参构造,初始化comparator对象为new Comparator。
        User u4 = new User();
        UserComparator us = new UserComparator();//创建Comparator比较器对象
        TreeSet<User> ts = new TreeSet<>(us);//构造器底层初始化Comparator
        ts.add(u4);

class User{  }
//实现Comparator接口并重写compare()方法
class UserComparator implements Comparator<User>{
    @Override
    public int compare(User u1, User u2) {  //比较规则}
}

3.2 Comparable 接口<TreeSet排序>

  1. 概念
    当需要将自定义类型的元素放入到TreeSet集合中存储时,那么自定义类型的类 就必须要实现Comparable 接口,并且重写实现Comparable 接口的compareTo()方法。在compareTo()方法内重写的内容就是关于自定义类进行比较的规则。
  2. 实现Comparable接口的作用
  • 对基本类型元素排序: TreeSet 会对放入集合中的元素进行排序,如基本类型的包装类和 String 在底层都实现了 Comparable 接口,自动实现升序排序;
  • 对自定义类型元素排序:Comparable 接口还可以对TreeSet中的自定义数据类型进行排序,但需要实现Comparable接口。未实现而放入TreeSet 中时,会出现ClassCastException类型转换异常--自定义类型不能转换为comparator类型。
  1. 典型方法
  • int compareTo(Object o) :自定义类重写compareTo() 后,根据其返回值确定自定义类的排序顺序;
  • 返回 = 0:表示添加到TreeSet中的元素相等,不需要更换顺序;
  • 返回 > 0:表示添加到TreeSet中的元素,左边大于右边,升序排序;
  • 返回 < 0:表示添加到TreeSet中的元素,左边小于右边,降序排序;
  1. 代码示例
//自定义类 和 Comparable接口紧密实现
class Person implements Comparable {
         String name;
         int age;
         //重写compareTo方法,实现自定义类的比较规则,返回值0表示相等,返回-1表示降序排序,返回>0表示升序排序
         public int compareTo(Object o) {
               if (o instanceof Person) {
                   Person p = (Person)o;
                   //return (this.age - p.age);//升序
                   return (p.age - this.age);//降序
              }
                throw new IllegalArgumentException("非法参数:o=" + o);
          } 
}

3.3 Comparator比较器 接口<TreeSet排序>

  1. 概念
    Comparator是用于比较两个元素的比较器,实现该接口的类,可以使用该接口特有的方法或比较规则 进行类的比较。
  2. 使用位置
    TreeSet的add()方法底层调用TreeMap的put()方法;TreeMap底层的put()方法的实现采用Comparator作为比较器,用于比较TreeMap中的两个元素。
  3. 自定义类与Comparator分离
public static void main(String[] args) {
           Person p1 = new Person( "张三",20);
           Person p3 = new Person( "张三",40);
           Person p2 = new Person( "李四",30);
           //创建比较器接口,比较两个对象(可能多属性)是否相等,然后排序
           Comparator personComparator = new PersonComparator(); 
           //创建set对象,同时初始化set集合的比较器(指定比较器对象)
           Set set = new TreeSet(personComparator);
           set.add(p1);  
           set.add(p2);  
           set.add(p3);
           //循环遍历迭代器,每个集合都实现了迭代器接口
           for (Iterator iter=set.iterator(); iter.hasNext();) {
                      Person p = (Person)iter.next();
                      System.out.println("name=" + p.name + ", age=" + p.age);
            } 
      } 
}
class Person {
          String name;
          int age;
          public Person( String name,int age){
                this.name = name;
                this.age = age;
          }
}
//Person实现Comparator比较器,可完成Person类的大小比较
class PersonComparator implements Comparator {
      public int compare(Object o1, Object o2) {
            if (!(o1 instanceof Person)) {
                    throw new IllegalArgumentException("非法参数:o1=" + o1);
            }
            if (!(o2 instanceof Person)) {
                    throw new IllegalArgumentException("非法参数:o2=" + o2);
            }
             Person p1 = (Person)o1;
             Person p2 = (Person)o2;
             return p1.age - p2.age;//根据Person的年龄排序
        }
}

四.Iterator接口

  1. 概念
    Iterator 称为迭代接口,实现了Iterator接口的类,表示该类是可以被迭代的。同时Iterable接口中的iterator()方法返回的就是在一个集合元素的迭代器,以证明可以遍历集合中的数据。
    迭代:即遍历,可以循环输出集合中的元素。
  • 迭代输出:将集合中的元素一个个的使用hasNext()方法进行判断,判断是否有内容,如果有内容就使用next()方法把内容输出。
  1. 性质特点
    Iterator 是一种遍历查询模式,主要可以统一数据结构的访问元素的方式,不用关心各个数据结构 的具体实现。
  2. 主要方法
  • boolean hasNext():判断该集合中是否有元素,如果仍有元素可以迭代,则返回 true;
  • Object next():返回可以迭代的下一个元素;
  • void remove():利用迭代器 从基础集合中移除迭代返回的最后一个元素,不会改变迭代集合的结构。若在集合的迭代过程中使用集合的remove()方法移除集合元素,会改变当前迭代器的迭代结构。
    public static void main(String[] args) {
        Collection c = new ArrayList();
        //在集合添加元素之前得到的迭代器,迭代集合时会发生异常:ConcurrentModificationException
        //Iterator it = c.iterator();
        c.add(1);//add加入的是Object类型数据,已使用自动装箱,1已装成Integer
        c.add(2);
        c.add(3);
        //在集合添加元素后得到的迭代器,遍历的集合结构会不一样
        Iterator it = c.iterator();
        while (it.hasNext()){
            it.next();
            //c.remove(1);//不能使用集合对象在迭代过程中remove元素,会改变迭代器迭代集合的结构,抛出异常:ConcurrentModificationException
            it.remove();//迭代过程中使用迭代器进行remove删除元素不会改变迭代集合的结构
        }
    }
  1. 迭代器的执行原理


    迭代的实现原理.png

五.Map<图>

  1. 概念
    Map是一个无序、采用键值对的形式存储数据的图。Map中的每一个元素包含一个键对象 和 一个值对象,即Map元素 = 键对象 + 值对象。键对象不允许重复,值对象可以重复<如:身份证号—姓名>。
  2. 性质特点
  • 键值对key-value:在Map中,所有子类都是采用键值对的方式存储元素,和Collection集合毫无关联关系;
  • 无序:map中存入元素和取出元素的顺序不相同,put()添加元素的底层实现,采用hash()算法对key进行位置存储处理;
  • key键不可重复:所有Map中存储的键key都是无序不可重复的,Map的key和Set集合存储元素的特点相同;
  • key-Set转换:Set集合存元素在底层是put到map中的key部分,而map中的key也可以通过keySet()方法返回一个set集合。
  1. 继承关系
    Map无继承父类和实现接口。和Collection同级,但和Collection、Iterator都无关,被HashMap、SortedMap<TreeMap>、HashTable等子类实现。
  2. 使用特点
  • Map的实现类较常用的是HashMap,HashMap对键的存取和HashSet 一样采用哈希算法;
  • 如果使用自定义类<引用数据类型>作为 Map 的键对象,自定义类必须重写 equals() 和 hashCode()方法。
  1. Map继承结构体系


    Map继承结构图.png
  2. 特殊点
    Map中使用静态内部类Entry,将map中的键值对关系抽取出来形成set集合中存储的元素关系。
  3. map遍历
  • Set<K> keySet()方法:将所有key抽取出来到一个set集合中,对set集合迭代遍历,再使用get(key)方法获取得到对应的value,该方法将map中key-value的形式变成set中"key=value"的形式;
  • Set<Map.Entry<K, V>> entrySet():将所有的key和value全部抽出来到set集合中,而该set集合使用map的内部类map.entry<>作为集合元素类型。对set集合遍历后,使用get(key)和get(value)就可以获取对应的值。
  1. 常用方法
  • map.put(k,v):往map中添加元素,key和value都只能存储引用数据类型-存地址
  • map.size():获取Map中存在的键值对数量;
  • map.isEmpty():判断map是否为空,底层调用size看键值对数是否为0;
  • map.get(key):根据key获取对应的value;
  • map.containsKey(key):判断是否包含指定key;
  • map.containsValue(value):判断是否包含指定value;
  • map.remove(key):根据指定键key删除一个数据;
  • map.replace(key,newValue):根据指定key,使用指定的新value替换旧value;
  • map.keySet():获取map中所有的key,并将获得key存到set集合中;
  • map.clear():清空map中的所有键值对
         //面向接口编程,创建一个map对象,并使用泛型指定map中存储的元素类型  
         Map<Integer,String> map = new HashMap();
        //往map中添加元素,key和value都只能存储引用数据类型-存地址
        map.put(1,"aaa");
        map.put(2,"bbb");
        map.put(3,"ccc");
        map.put(4,"dddd");
        map.put(5,"hahahah");
        map.put(5,"dududu");//key不能重复,往相同的key存储value时,会使用后面的value替换前面的value
        System.out.println(map.size());
        System.out.println(map.get(5));

        //获取map中所有的key存到set集合中
        Set<Integer> keys = map.keySet();
        //遍历Set中的key和value
        for (int i = 0;i<map.size();i++){
            System.out.println(map.get(i));
        }
        //for-each遍历
        for (Integer key:keys) {
            System.out.println(map.get(key));
        }
        //迭代器遍历
        Iterator<Integer> iterator = keys.iterator();
        while (iterator.hasNext()){
            Integer key = iterator.next();
            System.out.println(map.get(key));
        }

       //将map中所有的key和value抽取出来到set集合中,由(key,value) ---变成---> "key=value"
        Set<Map.Entry<Integer, String>> sets = map.entrySet();
        //对sets集合for-each遍历,泛型就是元素类型 = Map.Entry<Integer, String>
        for (Map.Entry<Integer, String> entry:sets) {
            System.out.println(entry.getKey() + "==" + entry.getValue());
        }
        //迭代器遍历
        Iterator<Map.Entry<Integer,String>> iterator1 = sets.iterator();
        while (iterator1.hasNext()){
            //遍历得到的元素类型就是指定的泛型Map.Entry<Integer,String>     
            Map.Entry<Integer,String> entry = iterator1.next();
            System.out.println(entry.getKey() + "==" + entry.getValue());
        }

5.1 哈希表

  1. 概念
    哈希表是一种数据结构,能够提供快速存取操作<通过数组元素的值,可以换算出数据元素的下标,通过下标就可以快速定位数组元素>
  2. 性质特点
    哈希表是基于数组和哈希算法的,因此存在一旦创建将不能扩展,并且无序(哈希算法的散列特点)。
  3. 实质
    哈希表 = 数组元素的值 + 元素值对应的下标(下标由元素值经过哈希算法得到)


    哈希表示例图.png

5.2 HashMap

  1. 概念
    HashMap即Hash+Map,使用哈希算法存储数据的Map<键,值>集合。底层采用哈希表的数据结构存储数据,因此存入元素是无序不可重复的。HashMap的方法是无synchronized修饰的,因此是线程不安全的。
  2. 静态接口Map.Entry<K,V>
    Map.Entry<K,V>是Map中的内部接口,HashMap实现了该内部接口,意为图的条目(所有键值对的个数)。该接口主要存储了Map中所有的key和value,并将该接口作为一个set集合的泛型,相当于将map中所有键值对存到set集合中,方便查询。
  3. HashMap实现


    HashMap底层图解.png
  4. 字段
  • int size:map中键值对的个数;
  • int DEFAULT_INITIAL_CAPACITY = 1 << 4:默认初始化容量为16,1 << 4表示 二进制数1左移4为得到二进制数16;
  • int MAXIMUM_CAPACITY = 1 << 30:左移30位最大容量;
  • float DEFAULT_LOAD_FACTOR = 0.75f:默认加载因子,当HashMap集合底层数组容量达到75%时,Node<>[]数组开始扩容;
  • int TREEIFY_THRESHOLD = 8:默认临界值,当数组元素下的单向链表节点数超过8个时,链表变成红黑树;
  • int UNTREEIFY_THRESHOLD = 6:取消临界值,当红黑树的节点个数小于6个时,将节点变成单向链表;
  • int MIN_TREEIFY_CAPACITY = 64:最小树容量。
  1. 常用方法
  • K getKey():获取map中的key;
  • V getValue():获取map中的value;
  • String toString() :
  • int hashCode() :获取当前map的hashCode()内存地址;
  • V setValue(V newValue) :使用新的value替换旧value;
  • boolean equals(Object o):判断map中的key是否与指定o相等;
  • int hash(Object key):获取指定key的哈希值,即key在数组中的下标;
  • map.put(k,v):添加键值对元素;
  • v = map.get(k):根据指定key获取对应的value值;
  • 遍历Map:先取出key,再根据key获取value;
  • 遍历Map:将key和value都取出,直接获取对应的key和value。
  1. 底层实现
    //Node<>实现Map的内部接口,将key和value保存为一个泛型-元素类型   
    //HashMap底层存储形式Node<>[]的自我实现     
    static class Node<K,V> implements Map.Entry<K,V> {
    //该hash是key调用hashCode()得出哈希值,将哈希值通过哈希算法得到的数组下标
        final int hash;// hash == 下标
        final K key;//key键
        V value;//键对应的value值
        Node<K,V> next;//下一个节点(de内存地址)
        //内部类构造方法        
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

    //HashMap底层存储元素的形式就是数组,而该Node<>[]数组在HashMap内部已自己实现(如前面显示)
    transient Node<K,V>[] table;
    //HashMap底层的内部接口,用于实现entrySet()方法    
    transient Set<Map.Entry<K,V>> entrySet;
}
5.1.1 HashMap与红黑树
  1. 关系
    在HashMap的底层实现中,HashMap使用 Node<>[]数组 + 链表的组合形式进行存储数据的,每个数组元素下挂着一条单向链表。HashMap规定了当链表的节点个数超过8个时,该单向链表变成红黑树;而当红黑树的节点个数少于6个时,该红黑树变成单向链表。
  2. 原因
    当HashMap中存储的元素过多时,不管是Node<>[]还是数组下的链表,都会影响执行效率,因此改变单向链表结构为成红黑树时,可以提高数据的查询检索效率。

5.2 SortedMap

  1. 概念
    SortedMap是一个可以排序的Map集合,实现SortedMap的子类可以完成对key的自动升序排序。
5.2.1 自平衡二叉树
  1. 概念
    自平衡二叉是一种完全二叉树,始终遵循左小右大的原则,即左子树永远小于右子树,左节点数小于右节点数。
  2. 图解


    自平衡二叉树的实现.png
  3. 自平衡二叉树遍历方式
  • 先序遍历:根-左-右
    先遍历数的根节点root,
    再遍历左节点(左节点若有分支也是从根节点开始,然后左节点,到右节点),
    再遍历右节点(右节点若有分支也是从根节点开始,然后左节点,到右节点)
  • 中序遍历:左-根- 右(TreeSet和TreeMap默认中序遍历)
    先遍历左子树(若左子树有分支,也是先遍历左节点,到根节点,然后右节点),
    再遍历根节点root,
    再遍历右子树(若左子树有分支,也是先遍历左节点,到根节点,然后右节点)
  • 后序遍历:左-右-根
    先遍历左子树(若左子树有分支,也是先遍历左节点,到右节点,然后根节点),
    再遍历右子树(若左子树有分支,也是先遍历左节点,到右节点,然后根节点),
    再到根节点root

5.3TreeMap

  1. 概念
    TreeMap即Tree + Map,TreeMap首先是一颗二叉树,而二叉树中的每一个节点是Map<>类型。TreeMap是可以对 Map中的键key 进行排序的集合。底层采用二叉树的数据结构存储元素。
  2. 要求
  • 基本数据类型或String类型:TreeMap底层可以自动对基本数据类型和String类型的元素进行自动排序,且排为升序。
  • 自定义类型:若 map 中的 key 采用的是自定义的引用数据类型,那自定义的引用类需要实现Comaprable 或 Comparator 接口完成排序。
  1. 字段
  • Comparator<? super K> comparator:Comparator比较器,使用于put方法的实现中,完成对元素的排序;
  • Entry<K,V> root:二叉树的root根节点;
  • int size = 0:二叉树节点个数;
  • int modCount = 0:用于统计的变量,初始为0;
  • 内部类:在TreeMap的底层实现中,定义了许多静态内部类、成员内部类等,满足底层自我需求。
  1. 常用方法
  • int size():获取TreeMap中二叉树节点的个数;
  • boolean containsKey(Object key):判断是否包含指定key的节点;
  • boolean containsValue(Object value):判断是否包含指定value的节点;
  • V get(Object key):根据指定key返回对应的value值;
  • Comparator<? super K> comparator():获取当前TreeMap中元素的比较器;
  • K firstKey():获取二叉树中的第一个key;
  • K lastKey():获取二叉树中的最后一个key;
  • Entry<K,V> getEntry(Object key)
  • V put(K key, V value):给指定key替换新的value值,返回旧的value值;
  • V remove(Object key):根据指定key删除节点,返回被删除key对应的value值;
  • void clear():清楚所有键值对,底层直接将size置0,根节点root置null;
  • Object clone():复制一份当前TreeMap对象,可能使用深克隆;
  • Map.Entry<K,V> firstEntry():
  • Set<K> keySet():获取二叉树中所有节点的key,并将其返回到set集合中;
  • Collection<V> values():获取二叉树中所有节点的value,并将其返回到Collection集合中;
  • Set<Map.Entry<K,V>> entrySet():获取二叉树中所有节点的key和value,并返回到set集合中;
  • V replace(K key, V value):使用新的value值替换指定key的旧value值;
  • void forEach():在当前TreeMap上进行for-each增强循环,调用该方法即可循环,不需要手动编写for-each循环。
  1. 底层部分关键源码实现
//TreeMap底层实现了
public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
  
    //无参构造,创建TreeMap对象时,comparator比较器初始化为null
    public TreeMap() {
        comparator = null;
    }
    //带参构造,创建TreeMap对象时,初始化comparator比较器对象为comparator的实现类
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    //根据指定键key获取二叉树结点    
    final Entry<K,V> getEntry(Object key) {
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
}

5.4 Hashtable<哈希表、散列表>

  1. 概念
    Hashtable底层采用哈希表的数据结构存储数据,因散列点的特点具有无序性。且Hashtable中的方法都是由synchronized修饰,因此是线程安全的。
  2. 实现
    Hashtable是根据关键码-值<键值对>而直接访问的数据结构,通过把关键码映射到表中一个位置来访问元素。通过hash()算法得到key的下标来读取元素值value。
  3. 性质特点
    哈希表就是将数组 和 链表两者结合的产物,查找容易<数组的特点>,插入删除也很快<单向链表的特点>。
  • 数组的特点:查找容易,插入删除困难;
  • 链表的特点:查找困难,但是插入删除容易。
  1. Hashtable实现原理


    Hashtable图解.png
  2. Hashtable实现关键
  • hashCode()方法:重写hashCode()方法可以得到key在哈希表数组部分的下标;
  • equals()方法:重写equals()方法可以匹配目标key和原链表key是否相等,也因key匹配的不一定就是数组下标的key,可能是数组元素下链表中的key,因此Hashtable和HashMap存入顺序与读取顺序是不一样的。HashSet也是如此。

5.4.1 Properties

  1. 概念
    Properties是继承于Hashtable的一个子类,底层也是采用键值对的形式存储数据,而且存储的键和值只能是 String字符串类型的,加上Properties中所有的方法都是synchronized修饰的,因此Properties也是线程安全的。
  2. 性质特点
  • 线程安全:Properties存储的key和value都只能是String类型的;Properties的方法都是synchronized修饰的
  1. 常用方法
  • String setProperty("key","value"):往Properties中存入数据,存入的key和value只能是String类型;
  • String getProperty("key"):从Properties取出数据,取出的key只能是String类型。

六. java.util.Collections 工具类

  1. 概念
    Collections类完全由 在collection上进行操作或返回collection的静态方法组成,是collection功能的扩展类。
  2. 特点
    提供一系列实用的方法,可以完成对collection集合排序,对集合中的内容查找等。
  3. 常用方法
  • 排序方法 Collections.sort(集合对象):对一个集合进行排序,只能对List类型的集合排序;
  • 二分查找 int Collections.binarySearch(集合对象, 目标元素):返回一个目标元素的下标;
  • 反转字符串 Collections.reverse(集合对象):将一个字符串的顺序反转;
  • synchronizedCollection(集合对象):将非线程安全的集合通过外挂将其变成线程安全的。
        //创建一个List对象,Collections.sort()中只能对List类型集合排序      
        List<Integer> list = new ArrayList<>();
        list.add(234);
        list.add(678);
        list.add(856);
        list.add(444);
        list.add(91);
        Collections.sort(list);
        for (Integer i:list) {
            System.out.println(i);
        }

        int n = Collections.binarySearch(list,234);//234的下标:n = 1
        List<String> l = new ArrayList<>();
        l.add("Are you ok");
        Collections.reverse(l);

七.泛型<E>

  1. 概念
    在java程序编码中,泛型指的是一些 包含类型参数的类。泛型参数只可以代表类的种类/种型,不能代表个别对象。
  2. 实质
    泛型就是 泛参数类型,属于引用数据类型,泛型 = 集合/数组中元素的类型。
  3. 作用特点
  • 泛型就是元素的类型,泛型限定了集合的元素类型,能更早的发现错误。如ClassCastException 类型转换异常,jvm通常在运行期才会现;如果使用泛型,jvm在编译期就会发现错误。
  • 发现错误越早,越容易调试,越容易减少成本;
  • 泛型定义后,该泛型的类型集合中 不能存储与泛型不同的参数数据;
  • 泛型实现功能与 instanceOf字符类似,使用泛型后,可以不用进行强制转换。

7.1 泛型的类型

  1. 类-泛型
    使用类泛型,可以指定方法的返回结果是自定义类的泛型,而不是一般的Object类型。使用字母T表示类泛型,T表示所有类型的公共高级接口,包括原始类型、参数化类型、数组类型、类型变量和基本类型等。
class My<T>{
    public T doMy(){
        return null;
    }
}
  1. 方法参数-泛型
    使用方法形参泛型,可以指定方法的参数类型。
public class AutoGeneric<autoString> {
    //基本类型参数
    public void dosome(int i){
        System.out.println(i);
    }
    //泛型类型的参数
    public void domore(autoString str){
        System.out.println(str);
    }
}

7.2 自定义泛型

  1. 概念
    使用自定义的 引用数据类型(即自定义类)作为泛型,限定集合中只能存储自定义类类型的元素,从而满足实际的开发需求。
  2. 特点
    通常情况下,自定义泛型一般使用 T 和 E 表示。
  • T:type,表示所有类型的公共高级接口。它们包括原始类型、参数化类型、数组类型、类型变量和基本类型;
  • E:element,表示一个程序元素,如包、类、方法;
  1. 作用
    使用泛型可以指定自定义泛型类中方法的参数类型、方法的返回结果类型都是泛型;不使用泛型时,方法的返回结果类型通常都是Object类型。
class My<T>{
    public T doMy(){
        return null;
    }
}
class AutoGeneric<autoString> {
    public void dosome(int i){
        System.out.println(i);
    }
    public void domore(autoString str){
        System.out.println(str);
    }

    public static void main(String[] args) {
        //使用泛型创建对象        
        AutoGeneric<String> ag = new AutoGeneric<>();
        ag.domore("autoString type");//IDEA提示参数类型是autoString泛型
        ag.dosome(23);//IDEA提示参数类型是int类型

        //不使用泛型创建对象
        AutoGeneric aug = new AutoGeneric();
        aug.domore("Object type");//提示参数类型是Object类型
        ag.dosome(88);//提示参数类型是int类型

        My m = new My();
        m.doMy();//调用方法时,IDEA提示返回的结果是Object类型
        My<Integer> my = new My<Integer>();
        my.doMy();//调用方法时,IDEA提示返回的结果是Integer类型
    }
}

7.3 自动类型推断机制

  1. 概念
    自动类型推断机制又称钻石表达式。在集合的泛型中,jvm支持自动类型推断,当子类型集合没有写明泛型时,可自动根据父类型的泛型推断出子类型集合的元素类型。
  2. 示例
public static void main(String[] args) {
        // ArrayList<此泛型类型自动推断>(),JDK8之后才允许
        List<Animal> myList = new ArrayList<>();
        //List<> list1 = new ArrayList<Animal>();//支持父类型泛型自动推断出子类型,不支持子类型泛
        myList.add(new Animal());
        myList.add(new Cat());
        myList.add(new Bird());
        // 遍历
        Iterator<Animal> it = myList.iterator();
        while(it.hasNext()){
            Animal a = it.next();
            a.move();
        }

        List<String> strList = new ArrayList<>();
        /*类型不匹配
        strList.add(new Cat());
        strList.add(123);
        */
        //自动类型推断参数类型为String            
        strList.add("http://www.126.com");
    }

7.4 for-each循环增强遍历机制

  1. 优缺点
  • 优点:语法格式简洁,对于集合或数组可以快速遍历
  • 缺点:遍历时无下标,因此在使用下标遍历的需求中不合适
  1. 示例
public static void main(String[] args) {
        // 创建List集合
        List<String> strList = new ArrayList<>();
        // 添加元素
        strList.add("hello");
        strList.add("world!");
        strList.add("kitty!");
        // 遍历,使用迭代器方式
        Iterator<String> it = strList.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        // 使用下标方式(只针对于有下标的集合)
        for(int i = 0; i < strList.size(); i++){
            System.out.println(strList.get(i));
        }
        // 使用foreach
        for(String s : strList){ //泛型使用的是String类型,所以返回也是String 
            System.out.println(s);
        }
    }

常见面试题

  1. 为什么重写hashCode()方法的同时需要重写equals()方法?
    答:
  • 因为在Map中,数据是以键值对的形式存在的。
  • 而在Hashtable中,Hashtable底层是使用Node<>[ ]数组+链表的组合形式存储数据的,数组的同一个下标之下有一条单向链表。
  • 重写hashCode()只能得到key在数组中的下标,但是并未能确定key在链表的具体位置,也不能确定key是否之前已经存在。
  • 因此还需要重写equals()方法,可以更加确定key的位置,并且判断key是否已存在。
  • 同一个数组下有一条链表,链表中存储了多个不同的key,因此hashCode相同只能得到相同的key数组下标,不能判断key对应的value就一定相等。
  • 重写的hashCode()方法也因此不能只返回一个固定值。
  1. 这么多的集合中,你用哪个集合最多?
    答:ArrayList集合。
    因为往数组添加元素,实则在它的末尾添加元素,效率不受影响。另外,我们在实际运用中,搜索和查找某个元素的操作比较多,数组查找元素的效率高。
    检索效率比较高(每个元素占用空间大小相同,数组的内存地址是连续的,知道首元素内存地址,知道下标,通过数学表达式计算出元素的内存地址,所以检索效率最高)。

  2. 使用集合模拟单向链表的实现?
    答:单向链表的特点,以节点为基础单元,每个节点包含数据部分+指向下一个节点的地址组成。可以将节点当作一个对象,而链表就是由多个节点组成。

//节点类
public class Node {
    int data;//节点的数据
    Node next = null;//指向下一节点的内存地址,起初都为空
    public Node() {
    }
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}
//链表
public class Link {
    private Node head = null;//链表头节点,初始为空
    private int size;//链表长度
    //创建节点
    public Link() {
    }
    public Link(Node head) {
        this.head = head;
    }

    public int size(){
        size = 0;//链表初始长度为0
        Node currentNode;//创建新节点-指向当前节点
        currentNode = head;//size=0时,头节点为当前节点
        while (currentNode != null){
            size++;//
            currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点保存
        }
        return size;
    }
    //添加节点:找到链表的末尾节点,把新的数据节点添加在后面
    public void addNode(int data){
        //创建要添加的节点对象
        Node newnode = new Node(data);
        if (head == null) {     //判断头结点是否为空--遍历从头到尾
            head = newnode;//头节点为空,直接保存新节点
            return;
        } else {
            /*
            Node currentNode = head;
            currentNode.next = newnode;//将要添加的节点作为下一个节点
             */
            Node currentNode = head;
            while (currentNode.next != null) {  //找到下一个节点直至末尾
                currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点
            }
            currentNode.next = newnode;//将要添加的节点作为下一个节点
        }
    }
    //删除节点:根据下标找到相应的节点,将删除节点的前一节点 指向 删除节点的下一节点
    //由 前-> 删除-> 后  ===变成===>  前-> 后
    public boolean deleteNode(int index){
        if (index < 1 || index > size()) {
            System.out.println("删除的元素下标超出范围");
            return false;
        }
        if (index == 1) {
            head = head.next;
            return true;
        }
        Node pre_node = head;//前节点
        Node cur_node = pre_node.next;//要删除的节点
        int i = 2;//
        while (pre_node != null) {
            if (i == index) {
                pre_node.next = cur_node.next;//删除当前节点,将删除节点的下一个节点内存地址 赋给 前一节点
                return true;
            } else {//向下遍历链表
                pre_node = pre_node.next;
                cur_node = cur_node.next;
                i++;
            }
        }
        return true;
    }
    //查询节点,根据数据data查找节点,返回节点的下标
    public int selectNode(int data){
        Node node = head;//从头开始遍历链表
        int index = 0;//从下标0开始遍历链表
        while (node != null){
            if (node.data == data){
                return index;
            }
            node = node.next;//遍历下一个节点
            index++;
        }
        return -1;//
    }
   //修改节点
    public boolean updateNode(int Index,int data){
        Node node = head;//从头开始遍历链表
        int index = 0;
        while (node != null){
            if(index == Index){
                node.data = data;
                return true;
            }
            node = node.next;//遍历下一个节点
            index++;
        }
        return false;
    }
    //遍历输出节点
    public void printLink() {
        Node node = head;//从头开始遍历链表
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.next;//遍历下一个节点
        }
        System.out.println();
    }
}
//测试
  1. 简单描述一下泛型机制?
    答:

  2. 讲述以下HashMap和Hashtable的区别?
    答:

  • HashMap:底层是哈希表的数据结构,采用数组存储元素。HashMap的方法无synchronized修饰,是非线程安全的;HashMap允许存入的key或value都为null;HashMap初始化容量为16,扩容的容量为原来的两倍(超过75%就扩容);
  • Hashtable:底层是哈希表的数据结构,采用数组存储元素。Hashtable的方法采用synchronized修饰,是线程安全的;Hashtable不允许存入的key或value任何一个为null,Hashtable在使用put()方法存入元素时,底层都调用了equals()方法判断存入的值是否为空;Hashtable初始化容量为11,扩容的容量为原来的两倍+1。
  1. Comparator 和 Comparable 的区别?
    答:
  • Comparable是默认的比较接口,Comparable 和需要比较的对象紧密结合到一起;
  • Comparator 可以分离比较规则,更具灵活性。
    一个类实现了 Camparable 接口则表明这个 类的对象 之间是可以相互比较的,这个类对象组成的集合也就可以直接使用 sort 方法排序。
    Comparator 可以看成一种算法的实现,将算法和数据分离<对象 和 对象的比较实现>
  1. 请使用两种方法完成从一个数组中查找得到一个目标数据,并讲明原理。
    冒泡排序
    选择排序

  2. 说一下数组和链表的认识,查询效率更高的是哪个?修改删除效率更高的是哪个?说明原因。
    答:
    第一:空间存储上,内存地址是连续的。
    第二:每个元素占用的空间大小相同。
    第三:知道首元素的内存地址。
    第四:通过下标可以计算出偏移量。
    通过一个数学表达式,就可以快速计算出某个下标位置上元素的内存址,直接通过内存地址定位,效率非常高。

优点:检索效率高。
缺点:随机增删效率较低,数组无法存储大数据量。
注意:数组最后一个元素的增删效率不受影响。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 222,681评论 6 517
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 95,205评论 3 399
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 169,421评论 0 362
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 60,114评论 1 300
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 69,116评论 6 398
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,713评论 1 312
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 41,170评论 3 422
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 40,116评论 0 277
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,651评论 1 320
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,714评论 3 342
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,865评论 1 353
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,527评论 5 351
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 42,211评论 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,699评论 0 25
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,814评论 1 274
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 49,299评论 3 379
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,870评论 2 361

推荐阅读更多精彩内容