search

集合框架

  1. 什么是集合？

    集合是Java提供的数据结构和算法的api。不需要像C一样另造轮子，就能使用数据结构和算法了。

    ​

  2. Collection接口

    Collection类图

  3. List

    • ArrayList:

         package jihe.list;

   /**
    * 手写ArrayList
    * 底层维护了数组，增删效率低，查询效率高
    * @author xiasj
    *
    */
   public class TestArrayList<E> {

       //List维护此数组
       private Object[] elementData;
       private int size;
       //如果New一个新的ArrayList但是没指定默认大小，则设为10
       private static final int DEFALT_CAPACITY=10;
       /**
        * 构造
        */
       public TestArrayList() {
           elementData=new Object[DEFALT_CAPACITY];
       }
       public TestArrayList(int capacity) {
           if(capacity<0) {
               throw new RuntimeException("容量不合法"+capacity);
           }else if(capacity==0){
               elementData=new Object[DEFALT_CAPACITY];
           }
           elementData=new Object[capacity];
       }

       /**
        * get
        */
       public E get(int index) {
           return (E)elementData[index];
       }
       /**
        * set
        */
       public void set(E element,int index) {

           //对索引index判断
           if(size<0 || index>size-1) {
               throw new RuntimeException("索引不合法"+index);
           }
           elementData[index]=element;
       }
       /**
        * 扩容
        * @param element
        */
       public void add(E element) {
           //什么时候扩容
           if(size==elementData.length) {
               //扩容
               Object[] newArray=new Object[elementData.length+(elementData.length>>1)];//x>>n=x/(2^n)
               System.arraycopy(elementData, 0, newArray, 0, elementData.length);
               elementData=newArray;

           }
           elementData[size++]=element;
       }

       /**
        * remove
        * 会完成自己给自己拷贝，把index后面的元素都拷贝一遍，所以效率低
        */
       public void remove(E element) {
           //将element和所有元素比较，第一个为true的，返回
           for (int i = 0; i < size; i++) {
               if(element.equals(get(i))) {

                   //将该元素从此处移除
                   remove(i);
               }
           }

       }

       public void remove(int index) {
           //A B C D 删除1位置的B
           //A C D 会完成自己给自己拷贝，把index后面的元素都拷贝一遍，所以效率低
           if(elementData.length-index-1>0) {
               System.arraycopy(elementData, index+1, elementData, index, elementData.length-index-1);
           }

           elementData[--size]=null;

       }

       @Override
       public String toString() {
           StringBuilder sb=new StringBuilder();

           sb.append("[");
           for(int i=0;i<size;i++) {
               sb.append(elementData[i]+",");
           }
           sb.setCharAt(sb.length()-1,']');

           return sb.toString();

       }
       public static void main(String[] args) {
           TestArrayList<String> tl=new TestArrayList<String>();
           for (int i = 0; i <100; i++) {
               tl.add("text"+i);
           }
           tl.set("xxx", 1);
           System.out.println(tl);

           tl.remove(1);
           System.out.println(tl);
       }
   }

    • LinkedList:

      ```java package jihe.list;

      import javax.management.RuntimeErrorException;

      /**

      • 为双向链表：查询效率低，增删效率高线程不安全

      • 每个节点有

      • class Node {

         Node  previous;      //前一个节点
 Object  element;    //本节点保存的数据
 Node  next;          //后一个节点

        }

        删除ax就把ax-1的next指向ax+1，ax+1的previous指向ax-1

        *

      • @author xiasj / public class TestLinkedList {

        private Node first; private Node last;

        private int size;

        public TestLinkedList() {

  • Vector:

    Vector底层是用数组实现的List，相关的方法都加了同步检查，因此“线程安全,效率低”。

  1. Map

    • HashMap: 线程不安全，效率高。允许key或value为null；

      JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）

      .JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

    • HashTable: 线程安全，效率低。不允许key或value为null。

    • HashMap源码分析： 1. 数据存储可以由数组和链表进行存储，它们有各自的特点：

      • 数组：占用的是连续的空间，随机访问快，但是增加删除效率低；

      • 链表：占用的是不连续的空间，访问慢，增加和删除快 那么，结合了数组和链表的哈希表就非常重要了,好接下来分析源码： 2. 源码：(Jdk1.7) 数组+链表， 1.HashMap通过key的hashcode通过“扰动函数”处理后得到hash值， 2.然后通过hash&(n-1)得到存放到数组的位置， 3.生成Entry对象，一个Entry对象包括 hash,key,value,指向下一个Entry对象的引用； 4.如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同， 如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

        扰动函数：就是hash方法，目的是： 把hashcode这个整数，转化到[0,length-1]的范围内，但是要求尽量均匀的分布在其中，以减少hash冲突。 jdk1.8在这进行了修改： 由

        变成了

        扰动了1次提升了效率。

      • 加载因子：loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0， loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

      • HashMap的部分源码：

        Node节点：

        put方法：

  2. ConcurrentHashMap

Previous语法基础Next机器学习

Last updated