Java基础 Day20

一、HashSet 集合类

1、简介

HashSet 集合底层采取哈希表存储数据

底层是HashMap

不能使存取有序

JDK8之前的哈希表是数组和链表，头插法

JDK8之后的哈希表是数组、链表和红黑树，尾插法

2、存储元素

（1）如果要保证元素的唯一性，需要同时重写对象中的 hashCode 方法和 equals 方法

因为Object类的hashCode方法是调用底层的C++代码计算了一个随机数

（2）hashCode方法计算哈希值，equals方法比较元素

当添加对象的时候, 会先调用对象的hashCode方法计算出一个应该存入的索引位置, 查看该位置上是否存在元素

不存在：直接存

存在：调用equals方法比较内容

false：存

true：不存

3、底层原理细节（JDK8及以后）

（1）哈希扰动

底层会先计算出原始哈希值，设为 h

计算 h ^ ( h >> 16 ) 作为新的哈希值

以减少哈希冲突

（2）取模运算

用最终的哈希值对底层数组长度取模，得到索引位置

初始数组长度为16

计算时，并不是直接 H % 16

而是 ( 16 - 1 ) & H

对16取模相当于取后四位，和1111做与运算也是取后四位

与运算的效率高于取模运算

（3）数组扩容与树化操作

扩容数组的条件：

当数组中的元素个数到达了 16 * 0.75 (加载因子) = 12，扩容到原数组 2 倍的大小

链表挂载的元素超过了8 (阈值) 个 , 并且数组长度没有超过64

链表转红黑树的条件：

链表挂载的元素超过了8 (阈值) 个, 并且数组长度到达了64

二、LinkedHashSet 集合类

1、简介

存取有序、去重、无索引

2、原理

底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序

三、几种单列集合的选择

1、元素可重复，用 ArrayList（最常用）

2、元素可重复，且增删多于查询，用LInkedList

3、元素不重复，用HashSet（最常用）

4、不重复且存取有序，用LinkedHashSet

5、想对元素排序，用TreeSet

四、可变参数

可变参数用在形参中可以接收多个数据

可变参数的格式：数据类型...参数名称

传输参数非常灵活，方便，可以不传输参数，可以传输1个或者多个，也可以传输一个数组

可变参数在方法内部本质上就是一个数组

注意：一个形参列表中可变参数只能有一个，可变参数必须放在形参列表的最后面

public static void main(String[] args) {System.out.println(add(1)); // 1System.out.println(add(1,2,3)); // 6int[] arr = {1,2,3,4};System.out.println(add(arr)); // 10
}public static int add(int... nums) {int sum = 0;for (int num : nums) {sum += num;}return sum;
}

五、Collections 集合工具类

Collections并不属于集合，是用来操作集合的工具类

public static <T> boolean addAll(Collection<? super T> c, T... elements)	给集合对象批量添加元素
public static void shuffle(List<?> list)	打乱List集合元素的顺序
public static <T> int binarySearch (List<T> list,  T key)	以二分查找法查找元素
public static <T> void max/min(Collection<T> coll)	根据默认的自然排序获取最大/小值
public static <T> void swap(List<?> list, int i, int j)	交换集合中指定位置的元素
public static <T> void sort(List<T> list)	将集合中元素按照默认规则排序
public static <T> void sort(List<T> list，Comparator<? super T> c)	将集合中元素按照指定规则排序

六、Map 接口

1、Map 集合

Map 集合是一种双列集合，每个元素包含两个数据

Map 集合的每个元素的格式：key = value(键值对元素)

key (键)：不允许重复

value (值)：允许重复

键和值是一一对应的，每个键只能找到自己对应的值

key + value 这个整体称为“键值对”或者“键值对对象”，在Java中使用Entry对象表示

2、常用方法

Map是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用的

V put(K key,V value)	添加元素，若键已存在，则覆盖原值，返回被覆盖的值
V remove(Object key)	根据键删除键值对元素
void clear()	移除所有的键值对元素
boolean containsKey(Object key)	判断集合是否包含指定的键
boolean containsValue(Object value)	判断集合是否包含指定的值
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，也就是集合中键值对的个数

3、特点

双列集合底层的数据结构都是针对于键有效，和值无关

HashMap：键唯一（重写hashCode方法和equals方法）

TreeMap：键排序（实现comparable接口并重写compareTo方法）

LinkedHashMap：键唯一且存取有序

4、遍历方式

（1）通过键找值

V get(Object key)	根据键查找对应的值
Set<K> keySet()	获取 Map 集合中所有的键

（2）通过键值对对象获取键和值

Set<Map.Entry<K,V>> entrySet()

获取集合中所有的键值对对象

（3）通过 forEach 方法遍历

default void forEach​ (BiConsumer<? super K, ? super V> action)

遍历Map集合, 获取键和值