java集合--单链

数据结构	说明
数组结构	在内存是连续的一片空间查询速度快，帯角标。长度不可变。
栈结构	是线性结构，先进后出。First in Last Out（栈内存：当调用一个方法f1时，该方法进栈放在栈内存中，运行过程中又调用一个方法f2，f2进栈，运行完出栈，接着f1继续执行，执行完毕才出栈。）--->手枪弹夹
队列结构	先进先出。First in First Out -->排队买票
哈希结构	数组中存储的都是元素<-->哈希值的对应关系，该数组称为哈希表（底层也是数组，但是存取方式不一样，通过算法算出元素应在位置）查询速度要比数组快 （一般堆内存中是hash结构）
二叉树结构	左子树，右子树，是有序的，顺序是根据对象的比较方法来排序

List子集：
Vector：可增长的数据结构，但是Vector是同步的。效率低，已被ArrayList替代。
ArrayList：数组结构，长度可变（原理：创建新数组+复制数组），查询速度快。弊端：增删较慢。不同步。
LinkedList：

• 链表结构。（前一个元素记录后一个元素的地址）增删速度快，不同步。弊端：查询速度慢
• 可用于实现堆栈，队列。

----对于已有的数据类型，可以通过另一容器来存储，遍历当前list与临时容器每个元素进行比较，没有就存入，有就进行下一个。
----对于自定义的数据类型，也是通过以上方法，但是需要重写自定义元素的equal()方法。
----太麻烦了 由此寻找集合中的其他框架
set：不包含重复元素，顺序不保证一致，该接口中的方法与Collection中方法一致
取元素的方式只有一种：迭代器。

知识点1：根据元素自身的数据算出应该存在哪个位置上！查找的速度更快，不必挨个遍历，定位是通过算法完成。java这种算法依赖于系统。因为空间是由window开辟的。这种算法叫做hash算法。翻译过来就是-->散列
知识点2：数组中存储的都是元素<-->哈希值的对应关系，该数组称为哈希表（底层也是数组，但是存取方式不一样，通过算法算，）查询速度要比数组快。
知识点3：先比较各自的hash值，再比较equals 内容。因此重复元素存不进去，保证元素的唯一性。
知识点4：哈希冲突怎么办？
哈希值一致(hashcode)，会再次判断元素的内容是否相同（equals）,如果equals返回true，意味着两个元素相同，不存！
如果equals返回false，意味着两个元素不相同，存储。存到哪个位置？如果继续通过算法算出位置。其中一个方法，拉链法。

知识点5：为什么自定义对象没有保证唯一性呢？通过对哈希表的分析，存储元素是，先调用了元素对象的hashCode()方法，因为都是新建对象所以hashCode值都不相同，也就不需要判断equals。因此需要对hashcode重写

/**
     * 重写hashCode方法，建立Student对象的hash值算法内容。 通过学生对象特有数据姓名和年龄值来算出hash值。
     */
    @Override
    public int hashCode() {
        final int NUMBER = 24;
        return name.hashCode() + age * NUMBER;// 乘以24(随意)为了尽量保证hash值不同
    }
/**
     * 重写了equals方法，建立Student对象判断相同的依据。
     */
    @Override
    public boolean equals(Object obj) {
        System.out.println("equals");
        if (this == obj)
            return true;
        if (!(obj instanceof Student)) {
            throw new ClassCastException();
        }
            Student stu = (Student) obj;
        return this.name.equals(stu.name) && this.age == stu.age;
    }

知识点6：为什么将字符串存入hashset中可以保证唯一性？
因为字符串本生就建立自己的hashcode的算法和equals方法

知识点7：通过Generater hashcode()和equals() 自动生成自己的方法。

@Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Student other = (Student) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

子集：
Hashset：哈希表结构，不同步，可以保证元素唯一性。依赖于hashcodeI()、equals()，查询速度快。
其子类LinkedHashSet:具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现(hash表中存有链表，每个元素除了hash值还记录了下个元素的地址。简单来说：如何存入，就如何取出)
TreeSet：可以对Set集合中的元素进行排序。使用的是二叉树结构，保证元素的唯一性通过对象的比较方法（comparTo）结构是否为0，是0，视为相同元素。
- 元素自身具备自然排序，其实就是实现了Comparable接口重写了compareTo方法。如果元素自身不具备自然排序，或者具备的自然排序不是所需要的，这时只能用第二种方式。
- 比较器排序，其实就是在创建TreeSet集合时，在构造函数中指定具体的比较方式。需要定义一个类实现Comparator接口，重写compare方法。
到此为止：再往集合中存储对象时，通常该对象都需要覆盖hashCode，equals，同时实现Comparale接口，建立对象的自然排序。通常还有一个方法也会复写toString()。
自定义对象，使用TreeSet添加元素会出现异常。
Exception in thread "main" java.lang.ClassCastException: cn.domin.Student cannot be cast to java.lang.Comparable
通过源码解读，底层实现基于TreeMap
Comparable<? super K> k = (Comparable<? super K>) key;
TreeSet的add方法内部最终实现：
* 需要将元素转成Comparable类型，为什么？因为这个类型具备排序的能力。
* 这个类型中有一个专门为排序提供了一个compareTo方法。
* 如果要让学生具备比较排序的功能，需要让学生扩展功能，实现Comparable接口

该方法虽然没有主动去调用，但是在内部底层在调用，将数据放在TreeSet容器中，容器底层使用对象的方法。
@Override
    public int compareTo(Object o) {
        if(! (o instanceof Student)){
            throw new ClassCastException("类型不一致");
        }
        Student stu = (Student)o;   
        return this.age - stu.age;
    }
但是也要保证元素的唯一性，相同年龄的存不进去
下一步改进：
在比较时，必须明确主次。主要条件相同，继续比较次要条件。
        int temp = this.age - stu.age;
        return temp==0?this.name.compareTo(stu.name):temp;//字符串也有copmareTo方法。

相关练习：

• TreeSet集合中要对字符串进行长度(由短到长)排序。

字符串之所以可以排序，因为是已经实现Comparable接口重写compareTo方法。建立了字符串的自然排序。但是自然排序不是需求中所需要的。咋办？ 只能使用比较器。需要自定义一个比较器。
构造集合时传入比较器对象。比较器中的方法如下：
@Override
    public int compare(Object o1, Object o2) {
        String s1 = (String) o1;
        String s2 = (String) o2;    
        int temp =s1.length()-s2.length();
        return temp==0?s1.compareTo(s2):temp;
    }

相关面试题：
去除list集合中的重复元素：对于自定义对象需要覆盖equals方法。

        List temp = new ArrayList();        
        for (Iterator it = list.iterator(); it.hasNext();) {
            Object obj = it.next();
            //对遍历到的每一个元素都到临时容器中去判断是否包含。
            if(!temp.contains(obj)){//如果不存在，
                temp.add(obj);//添加到临时容器。
            }
        }
        //唯一性的元素已经被记录到临时容器中。
        //清空原容器中的元素。
        list.clear();   
        //把临时容器中的元素添加到原容器中。
        list.addAll(temp);

看集合对象的小技巧
集合分体系。List Set
子类对象的后缀名是所属体系，前缀名是数据结构名称。

    List：新出的子类都是以List结尾的，通常都是非同步的。
        |--ArrayList ：看到array，就知道数组，查询速度快。
        |--LinkedList：看到link，就知道链表，增删速度快。   
    Set:
        |--HashSet:看到hash，就知道哈希表，查询速度更快，并想到元素唯一，通过hashCode(),equals方法保证唯一性。
        |--TreeSet:看到tree，就知道二叉树，可以排序，排序想到Comparable-compareTo Comparator--compare方法。