List:有序,元素可以重复,可以存储多个null,有索引的集合,常用的实现类有 ArrayList、LinkedList 和 Vector.
Set:无序,元素不可以重复,只可以存储一个null,Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet
Map:存储键值对,key不可以重复无序,value可以重复,Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象,Hashmap的key为null只能存储一个,TreeMap不能存储null
2.如何实现数组和 List 之间的转换
数组转 List：使用 Arrays. asList(array) 进行转换
List 转数组：使用 List 自带的 toArray() 方法
3.ArrayList 和 LinkedList 的区别是什么？
数据结构实现：ArrayList 是动态数组,而 LinkedList 是双向链表
查找和删除的区别:
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，
还存储了两个引用，一个指向前一个元素，一个指向后一个元素
线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全
4.HashSet的实现原理
(1).HashSet是基于HashMap实现的,HashSet的值存放于HashMap的key上,HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值
(2).HashSet是如何保证数据不可重复的
HashCode和Equals
Student对象存储到HashMap的key上
1.计算Student对象的哈希值,得到数组的索引下标.hashCode();
2.判断当前这个Student对象是否已经在哈希表中存在了.equals();
Equals相同的两个对象,hashCode必须相同,就认为是同一个对象哈希表中只能有一个
HashCode相同的对象,说明发生了哈希冲突,Equals不一定相同
5.HashMap
哈希表:基于数组高效查找衍生出的数据结构
哈希函数:将key映射为数组索引
哈希冲突:不同的key经过哈希函数的运算,得到了相同的数字
负载因子(LoadFactor):表示当前哈希表最多的有效元素个数
int[] data = new int[16];
loadfactor = 0.75f;
data.length * loadfactor = 12;//有效的元素个数为12个,超过这个数哈希表就会扩容.
开散列:在冲突的数字索引处转为链表实现,解决哈希冲突
(1).HashMap的实现原理:
(1.1)HashMap 基于 Hash 算法实现的
当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时，如果出现hash值相同的key，此时有两种情况。
(1)如果key相同，则覆盖原始值；
(2)如果key不同（出现冲突），则将当前的key-value放入链表中
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
(1.2).HahMap的数据结构,底层实现:
HashMap 底层是由JDK1.8是,数组+链表+红黑树组成,1.8之前是数组+链表
为什么使用数组+链表+红黑树?
数组：查找效率高,删除效率低
链表：查找效率低,增删效率高
首先通过index找到索引位置,在通过链表找到节点,进行节点的新增/修改/删除操作
如果链表节点>=8就会树化提高效率
(2)HashMap中重要的属性
(3)HashMap.put()方法的具体流程
只是为了得到一个比较平均的值
1.在hashmap中把一个key值放到哪个桶中经历了两步
1.先把hash值高低16位做异或运算得到一个比较平均的哈希值
2.和哈希桶的长度(n)做位运算就可以得到哈希桶的编号(索引)
计算索引!!!
上一步得到的key的哈希值和当前哈希表的长度 - 1 进行&就可以得到索引值
前提n必须为2^n(初始化的哈希桶数量必须为2^n)
(4). 为什么哈希桶的数量必须为2^n?
(4.1).只有在调用put方法时才会初始化哈希桶数组(懒加载)
(4.2) 初始化桶的个数,用户可以随意传,若不是2^n,会经过运算调整为2^n大小
(5)关于resize()方法
首先判断oldcap有没有初始化,要是没有初始化,就先调用初始化方法把他置为默认的容量初始化
要是需要扩容就扩容原来的一倍
