分析HashSet的扩容和转成红黑树机制

Set 接口实现类-LinkedHashSet

LinkedHashSet的全面说明

1）LinkedHashSet是 HashSet的子类

2）LinkedHashSet底层是一个 LinkedHashMap，底层维护了一个数组+双向链表

3）LinkedHashSet根据元素的 hashCode值来决定元素的存储位置，同时使用链表维护元素的次序（图），这使得元素看起来是以插入顺序保存的。

4）LinkedHashSet不许添重复元素

Map 接口和常用方法

Map 接口和常用方法

注意：这里讲的是JDK8的Map接口特点

1）Map与Collection并列存在。用于保存具有映射关系的数据：Key-Value2）Map中的key和 value可以是任何引用类型的数据，会封装到HashMap$Node对象中

3）Map中的 key不允许重复，原因和HashSet一样，前面分析过源码

4）Map中的value可以重复

5）Map的key可以为 null， value也可以为null，注意 key 为null只能有一个,value为null，可以多个.

6）常用String类作为Map的 key

7）key和 value之间存在单向一对一关系，即通过指定的key总能找到对应的 value

8）Map存放数据的key-value示意图，一对k-v是放在一个HashMap$Node中的，有因为Node实现了 Entry接口，有些书上也说一对k-v就是一个Entry（如图）

Map 接口常用方法

remove:根据键删除映射关系

get：根据键获取值

size:获取元素个数

isEmpty:判断个数是否为0

clear:清除 k-v

containsKey:查找键是否存在

Map 接口遍历方法

1. containsKey:查找键是否存在
2. keySet:获取所有的键
3. entrySet:获取所有关系k-v
4. values:获取所有的值

迭代器

System.out.println(“----使用 EntrySet 的 迭代器(第 4 种)----”);

Iterator iterator3 = entrySet.iterator();

while (iterator3.hasNext()) {

Object entry = iterator3.next();

//System.out.println(next.getClass());//HashMap$Node实现-> Map.Entry (getKey,getValue)

//向下转型 Map.Entry

Map.Entry m = (Map.Entry) entry;

System.out.println(m.getKey() + “-” + m.getValue()

Map 接口实现类- HashMap

HashMap 小结

1）Map接口的常用实现类：HashMap、Hashtable和Properties。

2）HashMap是Map接口使用频率最高的实现类。

3） HashMap 是以 key-val 对的方式来存储数据（HashMap$Node类型）

4）key不能重复，但是值可以重复，允许使用null键和null值

5）如果添加相同的key，则会覆盖原来的key-val，等同于修改.（key不会替换，val会替换）6）与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的.（jdk8的hashMap底层数组+链表+红黑树）

7）HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized

HashMap 底层机制及源码剖析

HashMap 底层机制及源码剖

>扩容机制［和HashSet相同］

1） HashMap底层维护了Node类型的数组table，默认为null

2） 当创建对象时，将加载因子（loadfactor）初始化为0.75.

3） 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。

4） 第1次添加，则需要扩容table容量为16，临界值（threshold）为12（16＊0.75）

5） 以后再扩容，则需要扩容table容量为原来的2倍（32）临界值为原来的2倍，即24，依次类推

6） 在Java8中，如果一条链表的元素个数超过 TREEIFY THRESHOLD（默认是8）并且table的大小 >= MIN TREEIFY CAPACITY（默认64），就会进行树化（红黑树）

Map 接口实现类-Hashtable

HashTable 的基本介绍

1） 存放的元素是键值对：即K-V

2） hashtable的键和值都不能为null，否则会抛出NullPointerException3）hashTable使用方法基本上和HashMap一样

4） hashTable 是线程安全的（synchronized）， hashMap 是线程不安全的

Hashtable 和HashMap对比

Map-Properties

基本介绍

1. Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。
   
2. 他的使用特点和Hashtable类似
   
3. Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象并进行读取和修改
   

总结-开发中如何选择集合实现类(记住)

Collections工具类

Collections工具类介绍

1）Collections是一个操作 Set、List和 Map等集合的工具类

2）Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作14.17.2排序操作：（均为static方法）

2.1）reverse（List）：反转 List中元素的顺序

2.2）shuffle（List）:对 List集合元素进行随机排序

2.3）sort（List）:根据元素的自然顺序对指定 List集合元素按升序排序

2.4）sort（List，Comparator）根据指定的 Comparator产生的顺序对 List集合元素进行排序

2.5）swap（List， int， int）:将指定 list集合中的i处元素和j处元素进行交换

排序操作：（均为 static 方法)

查找、替换

泛型

使用传统方法的问题分析

1）不能对加入到集合ArrayList中的数据类型进行约束（不安全）

2）遍历的时候，需要进行类型转换，如果集合中的数据量较大，对效率有影响泛型的理解和好处

1）编译时，检查添加元素的类型，提高了安全性

2）减少了类型转换的次数，提高效率［说明］

3）不再提示编译警告

泛型介绍

理解：泛（广泛）型（类型） => Integer， String，Dog

1）泛型又称参数化类型，是Jdk5.0出现的新特性，解决数据类型的安全性问题

2）在类声明或实例化时只要指定好需要的具体的类型即可。

3）Java泛型可以保证如果程序在编译时没有发出警告，运行时就不会产生ClassCastException异常。同时，代码更加简洁、健壮

4）泛型的作用是：可以在类声明时通过一个标识表示类中某个属性的类型，或者是某个方法的返回值的类型，或者是参数类型

泛型的语法

泛型的声明

interface 接口｛｝和 class类<K，V>｛｝

比如：List，ArrayList

说明：

1）其中，T，K，V不代表值，而是表示类型。

2）任意字母都可以。常用T表示，是Type的缩写

泛型的实例化

要在类名后面指定类型参数的值（类型）。

如：

1. List strList = new ArrayList（）
2. List strList = new ArrayList< >（）
3. Iterator iterator = customers.iterator（）；

泛型使用的注意事项和细节

1.interface List{}, public class HashSet{).等等

说明：T,E只能是引用类型

看看下面语句是否正确？：

1. List list = new ArrayList(); /OK
2. List list2 = new ArrayList();/错误

2.在给泛型指定具体类型后，可以传入该类型或者其子类类型

3.泛型使用形式

1. List list1 = new ArrayList();
2. List list2 = new ArrayList<>();

3.如果我们这样写 List list3 = new ArrayList();默认给它的泛型是[E就是Object]

自定义泛型类

基本语法

class类名<T，R.>｛/.….表示可以有多个泛型成员}

注意细节

1）普通成员可以使用泛型（属性、方法）

2）使用泛型的数组 不能初始化 因为数组在 new 不能确定 T 的类型就无法在内存开空间

3）静态方法中不能使用类的泛型 因为静态是和类相关的，在类加载时，对象还没有创建所以，如果静态方法和静态属性使用了泛型，JVM 就无法完成初始化

4）泛型类的类型，是在创建对象时确定的（因为创建对象时，需要指定确定类型）

5）如果在创建对象时，没有指定类型，默认为Object

如：

1. Tiger 后面泛型，所以我们把 Tiger 就称为自定义泛型类
   
2. T, R, M 泛型的标识符, 一般是单个大写字母
   
3. 泛型标识符可以有多个
   

自定义泛型接口

基本语法

interface接名<T， R…>｛｝

注意细节

1）接口中，静态成员也不能使用泛型（这个和泛型类规定一样）

2）泛型接口的类型，在继承接口或者实现接口时确定

3）没有指定类型，默认为Object

如：

自定义泛型方法

基本语法

修饰符<T，R.>返回类型方法名（参数列表）

注意细节

1. 泛型方法，可以定义在普通类中，也可以定义在泛型类中
   
2. 当泛型方法被调用时，类型会确定
   
3. public void eat（E e） ｛｝，修饰符后没有<T，R.> eat方法不是泛型方法，而是使用了泛型
   

泛型的继承和通配符

1）泛型不具备继承性

List list = new ArrayList（）;错误示列

2）<？>:支持任意泛型类型

3）<？extends A>:支持A类以及A类的子类，规定了泛型的上限

4）<？super A>:支持A类以及A类的父类，不限于直接父类，规定了泛型的下限