Collection类型

List:是一个有序的，元素可以重复 ArrayList:底层维护的是一个Object数组，特点查询快，增删慢 LinkedList:底层维护的是一个双向列表，特殊增删快，查询慢 Vector:底层维护的是Object数组，线程安全的，效率非常慢 Set:是一个无序，元素不可以重复

• HashSet:
• LinkedHashSet:
• TreeSet:

Set:

1.Set不允许出现重复元素 2.Set我一般都说是无序的(但不是随机)。

HashSet:

HashSet是Set接口的典型实现，大部分时候，我们说Set用的都是HashSet

特点:

1. 不能保证元素的迭代顺序
2. 此类允许使用 null 元素
3. 不是线程安全的

HashSet的无序性:

HashSet的元素不重复:

如果元素是对象可以通过重写equals()和HashCode()的方法来达到元素不重复的目的

HashSet本质上还是依靠数组进行维护的。但是在数据添加的时候他会进行如下处理:

1. 先获取数据的HashCode的值
2. 通过过一个哈希算法，算出HashCode的具体值(这个值其实也就是索引位置)
3. 将数据插入到指定索引位置

创建一个对象，然后对象分别添加到Set集合当中，但是Set并没有给我们去重的原因：

因为每一个对象的hashCode都是不同的，而现在默认是比较地址值是否相同

解决方法及解释:

重写了子类的equals方法，但是却并没有被调用

原因，因为现在每一个对象的hashCode地址不同，所以直接就插入，根本不需要equals进行判断使equals调用起来

equals调用的前提是对象的hashCode相等，算出来索引位置相等，才会进行二次对比(调用equals)

让对象具备相同的散列码(哈希地址)

可以直接使用IDEA进行生成重写hashCode方法,默认使用的是Arrays的hashCode()

hashCode()的原理

result = 31 * result + (element == null ? 0 : element.hashCode());

31占用的是5bits, 如果相乘造成的数据溢出的概率会比较的小，现在很多虚拟机基本都有进行优化，原则你的散列系数越大 效率也就越高，也就越安全。

31是不是一个素数，素数的作用就是如果我用每一个数字来乘以这个素数，那么最终的结果只能被素数本身和1来进行整除(一定程度上减少冲突)

注意:

1. HashSet并不是随机性的,而是通过哈希码计算的值跟我们理想插入顺序不一致而已，取出还是顺序进行取出的
2. 重写equals，在HashSet并不会进行调用，此时应该保证相同对象必须具备相等散列码 所以斤应该重写对象的HashCode，致使equals能够被调用起来。

通常来说，参与计算equals的值应该同步放到HashCode进行同步计算。

LinkedHashSet:

• LinkedHashSet其实就是HashSet的子类，本质上也是通过计算hashCode来决定元素的存储位置（跟HashSet处理的方式也一致）。
• LinkedHashSet保证插入和取出顺序一致的原理
• 其实就是LinkedHashSet又多提供了一个双向链表进行维护次序，所以就使得元素看起来是迭代顺序有序的。
• 从性能来说LinkedHashSet插入的性能略低于HashSet。

HashSet:

底层维护的是数组，初始化容量16,如果容量的使用率超过0.75(160.75=12),就会自动扩增原来容量的2倍(162=32)

HashSet(或者HashMap)的实现原理是：

因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap（适配器模式）。

HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。 根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式，另一种是冲突链表方式。Java HashMap采用的是冲突链表方式。

TreeSet提供排序方式:

TreeSet可以确保我们集合的元素处于一个排序状态。

其实他排序的底层实现的是二叉树结构(红黑树)来进行数据的存储。

1. 自然排序

   只要你的数据具备自然排序的规则，就可以默认的使用Comparable进行排序， 如果说，元素不具备排序规则，那么就会造成类型转换失败(排序的前提一定是同一个类型，且具备排序规则) 如果是对一个对象的某个字段进行排序，则需执行两个步骤:

   1. 实现Comparable接口
   2. 重写compareTo方法

   重写方式 this.成员变量 - o.成员变量(转型的问题)

   Comparable: 此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。 ClassCastException:类型转换失败异常

2. 定制排序

   1. 自己定义个排序类
   2. 该类实现Comparator这个接口
   3. 重写该类的compare的方法，制定排序规则

   	public class MyComparable implements Comparator {
   		//重写规则
   		public int compare(Object o1, Object o2) {
   			Book b1 = (Book)o1;
   			Book b2 = (Book)o2;
   			return (int) (b1.price - b2.price);
   		}
   	}
   

   4. 创建TreeSet类,并且将自定义的排序类创建对象，传到TreeSet对象构造当中

   	MyComparable mc = new MyComparable();
   	TreeSet ts = new TreeSet(mc)
   	//匿名内部类(安卓开发常用,javaee开发基本不用)
   	TreeSet ts = new TreeSet(new Comparator() {
   		public int compare(Object o1, Object o2) {
   			 Book b1 = (Book)o1;
   			 Book b2 = (Book)o2;
   			 return (int) (b1.price - b2.price);
   		}
   	});
   

# HashMap的解析:
	//默认的初始化容量为16
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	//最大的容量为2^30
	static final int MAXIMUM_CAPACITY = 1 << 30;
	//默认的负载因子为0.75
	static final float DEFAULT_LOAD_FACTOR = 0.75f;