JavaSE高级-集合框架List&Set&Map

一、Collection 接口的继承及实现类：

其中，Interable 迭代器接口，因为Collection接口继承了Interable接口，而Interable中有一个。

二、List接口：
特点：
1.元素存取有序的集合。
2.是一个带有索引的集合，可以通过索引可以精确的操做集合中的元素。
3.是一个可以存储重复元素的集合。通过元素的equals方法，来比较是否为重复的元素。
List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法，如下：
public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
public E get(int index):返回集合中指定位置的元素。
public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
List常用的迭代遍历方式：
主要有四种：
1.foreach (增强For)
集合名.foreach

//1.foreach
System.out.println("-------foreach---------");
for (Object o : list) {
    System.out.println(o);
}

2.For i 通过下标 i ，用list集合中的get() 方法获取集合元素。

//2.通过下标获取
System.out.println("-------get---------");
for (int i = 0; i <list.size() ; i++) {
    System.out.println(list.get(i));
}

3.迭代器 Iterator

//3.迭代器
System.out.println("-------迭代器---------");
Iterator<Object> iterator = list.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

4.Lambda

//4.Lambda
System.out.println("-------Lambda---------");
list.forEach(o -> {
    System.out.println(o);
})

数组：常用的容器之一
1.长度一经定义就无法修改。
2.存储空间有限
3.可以存储基本数据类型和引用数据类型
4.存储的元素内容单一。
集合：常用的容器之一
1.长度可变
2.搭配泛型使用，泛型只能是引用数据类型传递（存储元素是Object的引用数据类型）
List集合： 接口
1.可以存储重复元素
2.有序，按照存储顺序，获取元素。
3.允许存放null 值。
ArrayList集合：实现类
1.基于数组原理实现，在内存中存储是连续的
2.查询快，增删慢
3.线程不安全
4.经常使用到的集合
LinkedList: List 实现类
1.基于双向链表原理实现，在内存中不连续，操作分头尾。（node(nodePrevious、data、nodeNext）
2.查询慢，增删快。
3.分头尾进行操作。
4. 线程不安全。
5.通过下标进行操作。
Vector ：
1.线程安全
2.API 与ArrayList 相似。
总结：
1.若实际中，用到的主要是查询操作，优先选择ArrayList 例如：根据条件分页搜索数据展示
2.若实际中，主要是使用头尾操作（增 删 查），优先选择LinkedList,例如：自定义的数据库连接池、浏览足迹。
Set接口:
1.存储的元素是不可重复的
2.丢失原存储顺序（元素都是无序的(即存取顺序不能保证不一致)）

HashSet 实现类
1.根据对象的哈希值来确定元素在集合中的存储位置，无序状态（存取顺序不能保证不一致）
2.具有良好的存储和查找性能
3.保证元素的唯一性 - equals()和hashCode()
4.线程不安全的

思考：
1.HashSet 怎么出现无序的情况的？
底层计算hash值时，通过(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);计算
计算对应添加元素的的“桶”数组的下标，通过(n - 1) & hash计算。(n 是hash表的长度)

2.HashSet 如何保证元素的唯一性？
根据hashcode()和equals()保证元素的唯一性。
当hashcode一致时，equals不一定一致，需要查看equals是否一致，
若equals一致，则认定为相同元素；
若equals不一致，则认定为不同元素；
当equals一致时，hashcode一定一致，直接认定是相同元素。

3.JDK8版本前后，底层存储结构有什么不同？为什么做出改变？
1).底层是由数组 - 链表组成，当添加新元素时，它会根据元素的hash值找到对应的"桶"，也就是HashMap源码中Node<K, V> 里的元素，
并插入到对应位置的链表中，链表元素个数过长时会转化为红黑树(JDK1.8后的版本)。
2).链表取元素是从头结点一直遍历到对应的结点，这个过程的复杂度是O(N) ，而红黑树基于二叉树的结构，查找元素的复杂度为O(logN) ，
所以，当元素个数过多时，用红黑树存储可以提高搜索的效率。

4.既然红黑树的效率高，那怎么不一开始就用红黑树存储呢？
红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是基于时间和空间的平衡考虑。
此处翻译源代码注释：单个 TreeNode 需要占用的空间大约是普通Node的两倍，所以只有当包含足够多的Nodes时才会转成 TreeNodes，
这个足够多的标准就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize (扩容) 变少后，
红黑树会转变为普通的链表，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。

5.为什么树化标准是8个？
此处翻译源代码注释：如果hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。
在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，
概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据。
若用户使用HashMap过程导致hashCode分布离散很差的场景（思考一下是什么场景），这个时候再转换为红黑树就是一种很好的退让策略。
可以避免查询效率低下的问题，从而有效防止用户自己实现了不好的哈希算法时导致链表过长的情况。

6.底层计算hash值时，为什么要(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);这样运算？
传入key之后，hash()会获取key的hashCode进行无符号右移 16 位，然后进行按位异或，并把运算后的值返回，这个值就是key的哈希值。
这样运算是为了减少碰撞冲突，因为大部分元素的hashCode在低位是相同的，不做处理的话很容易造成冲突。

7.如何计算对应添加元素的的“桶”数组的下标？
tab[i = (n - 1) & hash]) 当查找不到对应的索引时，就会新建一个新的结点作为链表的头结点。
通过位运算，在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，
之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开，达到较好的分布离散效果。

8.为什么退化为链表的阈值是6？
当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6。主要是一个过渡， 避免链表和红黑树之间频繁的转换。
如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的 转换结构无疑会降低性能， 所以阈值才不设置的那么临界。
HashSet 存储结构实现原理：

TreeSet集合:是Set的一个实现类，底层依赖于TreeMap,基于红黑树的实现
特点
1.保证元素的唯一性 -compareTo()
2.元素没有索引
3.用元素的[自然顺序]实现Comparable接口，对元素进行排序
4.线程不安全。

LinkedHashSet: 是继承了HashSet

  1. 不允许重复存放元素，保证元素的唯一性 - equals()和hashCode()
  2. 新增一条链表，来保证存取顺序一致 ，有序（存取顺序一致），加上了链表进行存储保证有序性。
  3. 由于保证了存取顺序，其执行效率不如HashSet.
  4. 根据对象的哈希值来确定元素中的存储位置
  5. 具有良好的存储和查找性能
  6. 线程不安全。

Collections类

Collections 集合的工具类
常用方法：
1.static boolean addAll(Collection<? super T> c, T... elements) 将所有指定的元素添加到指定的集合中。
2.public static void shuffle(List<?> list) :打乱集合顺序。
3.static <T extends Comparable<? super T>> void sort(List list) :将集合中元素按照默认规则排序。 添加的元素具备比较性
4.public static void sort(List list，Comparator<? super T> ):将集合中元素按照指定规则排序。 容器具备比较性

Map 接口：
1.Map<k,v> k键 v值
k键 Set集合
v值 Collection集合
put(k,v) 添加元素
map集合添加元素，保证了键值不重复，一但键值相同，Value值会被覆盖。
HashMap：
1.键不能重复，一旦重复，会造成value值被覆盖
2.添加元素，无法保证键的存取顺序。
3.线程不安全
4.允许null值和null键
5.HashMap和HashSet的原理一样，JDK1.8 哈希表（基于数组 链表 和 红黑树）。
LinkedHashMap：
1.键不能重复，一旦重复就会造成Value值的覆盖
2.添加元素，保证键的存取顺序。
3.LinkedHashMap 和 LinkedHashSet 原理一致，1.8 哈希表（数组+链表+红黑树），会多出一条链表来维护存取顺序
4.线程不安全
5.允许null键 和 null 值。
TreeMap：
1.键不能重复，一旦键重复可能会造成value值的覆盖
2.添加元素，键进行自然排序
3.TreeMap 和 TreeSet 原理一致，基于红黑树的原理。
4.线程不安全。
5.TreeMap不允许存放null键 但可以存放null值
排序性：
1.添加的元素具备比较性 implemnts Comparable 接口 compare To();
2.集合容器自身具备比较性 new Comparator 接口 compare（）
总结： Java 有就近原则，两个比较方法同时存在，会优先选择Comparator方式

JDK 版本 LTS（Long Time Support）
JDK 9 的新特性：
list接口 Set 接口 Map 接口 增加了一个静态的方法 of 可以给集合一次性添加多个元素。
static list of ( E ....element)

使用前提：
当集合中存储的元素个数已确定，不在改变使用。

注意：
1.of 方法只只适用于，list 接口 set接口 map接口 不适用于接口的是实现类。
2. of 方法的返回值是一个不可改变的集合，集合不能在使用add put 方法 添加元素，否则会抛出异常
3. Set 接口和 Map 接口在调用of 方法时，不能有重复的元素，否则会抛出异常。

Propertise 类-----------------> HashTable 类 ------------------> Map接口:
                    extends                         implements
   Propertise 类-----------------> HashTable 类 ------------------> Map接口
   
   HashTable类
   1.实现了一个哈希表，它映射了值的键（类似于HashMap）
   2.任何非null对象可以作为key或值
   3.线程安全的
  Propertise 代表一个持久的特性。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/monkeycode/p/13988063.html