Java集合框架

2022-11-20
作者 GLK
~16.01K 字

HashMap

方法

1：put方法：put(key，value)，我们经常用存储一些常用的数据，比如flag、百分比之类的，我们就可以返回map结构，如果key相同则值会覆盖，允许key和value为null。

2：get方法：get(key)，主要用来取map中存储的数据，我们根据其key值，可以取到对应的value值，没有该key对应的值则返回null。

3：remove方法：remove(key)，主要用来删除map中对应的key及其value值。

4：clear方法，用法：clear()，会清空map中的数据。

5：containsKey(key)，判断map集合中是否包含某个key。

6：containsValue(value)，判断map集合中是否包含某个value。

7：entrySet()：hashmap.entrySet().iterator()，entrySet()的效率比keySet()要高。key和value存储在entry对象里面，遍历的时候，拿到entry对象就可以取到value了。

8：keySet()：hashmap.keySet().iterator()，keySet是把key放到一个set集合中，通过迭代器遍历，再用hashmap.get(key)来取到value的值。

9：Map.getOrDefault(key，默认值)；

map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
//Map中会存储一一对应的key和value。
//如果 在Map中存在key，则返回key所对应的的value。
//如果 在Map中不存在key，则返回默认值。

简介

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着他不是线程安全的，它的key、value都可以为null，此外，HashMap中的映射不是有序的。

JDK 1.8之前是由数组+链表组成的。数组是HashMap的主体，链表则是主要为了解决哈希冲突**(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)**而存在的(‘拉链法解决hash冲突’)
JDK1.8 以后，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。

这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。具体可以参考 treeifyBin方法。

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时，链表转换为红黑树时，效率也变的更高效。

特点：

1.存取无序的

2.键和值位置都可以是null，但是键位置只能是一个null

3.键位置是唯一的，底层的数据结构控制键的

4.jdk1.8前数据结构是：链表 + 数组 jdk1.8之后是：链表 + 数组 + 红黑树

5.阈值(边界值) > 8 并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

数据结构

说明：

1.面试题：HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？

对于key的hashCode做hash操作，无符号右移16位然后做异或运算。
还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。至于底层是如何计算的我们下面看源码时给大家讲解。

2.面试题：当两个对象的hashCode相等时会怎么样？

会产生哈希碰撞，若key值内容相同则替换旧的value.不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。

3.面试题：何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞？

只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

4.面试题：如果两个键的hashcode相同，如何存储键值对？

hashcode相同，通过equals比较内容是否相同。
相同：则新的value覆盖之前的value
不相同：则将新的键值对添加到哈希表中

5.在不断的添加数据的过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

6.通过上述描述，当位于一个链表中的元素较多，即hash值相等但是内容不相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度(阀值)超过 8 时且当前数组的长度 > 64时，将链表转换为红黑树，这样大大减少了查找时间。jdk8在哈希表中引入红黑树的原因只是为了查找效率更高。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。如下图所示。

但是这样的话问题来了，传统hashMap的缺点，1.8为什么引入红黑树？这样结构的话不是更麻烦了吗，为何阈值大于8换成红黑树？

JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

至于为什么阈值是8，我想，去源码中找寻答案应该是最可靠的途径。下面我们在分析源码的时候会介绍。

jdk8存储过程:

继承关系

说明：

Cloneable 空接口，表示可以克隆。创建并返回HashMap对象的一个副本。
Serializable 序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。
AbstractMap 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

补充：通过上述继承关系我们发现一个很奇怪的现象，就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构。

据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

成员

成员变量

1.序列化版本号

private static final long serialVersionUID = 362498820763181265L;

2.集合的初始化容量( 必须是二的n次幂 )

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

问题： 为什么必须是2的n次幂？如果输入值不是2的幂比如10会怎么样？

HashMap构造方法还可以指定集合的初始化容量大小：

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

根据上述讲解我们已经知道，当向HashMap中添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。 HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法。

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算(这点上述已经讲解)。所以源码中做了优化,使用 hash&(length-1)，而实际上hash%length等于hash&(length-1)的前提是length是2的n次幂。

为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；

小结：

1.由上面可以看出，当我们根据key的hash确定其在数组的位置时，如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。

2.另一方面，一般我们可能会想通过 % 求余来确定位置，这样也可以，只不过性能不如 & 运算。而且当n是2的幂次方时：hash & (length - 1) == hash % length

3.因此，HashMap 容量为2次幂的原因，就是为了数据的的均匀分布，减少hash冲突，毕竟hash冲突越大，代表数组中一个链的长度越大，这样的话会降低hashmap的性能

4.如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字。

源代码如下：

//创建HashMap集合的对象，指定数组长度是10，不是2的幂
HashMap hashMap = new HashMap(10);
public HashMap(int initialCapacity) {//initialCapacity=10
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10
     if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}
  /**
   * Returns a power of two size for the given target capacity.
  */
    static final int tableSizeFor(int cap) {//int cap = 10
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

默认的负载因子，默认值是0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

当链表的值超过8则会转红黑树(1.8新增)

//当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;

因为树节点的大小大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点(参见TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时，就会被转换回普通的桶。在使用分布良好的用户hashcode时，很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布

因为树节点的大小大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点(参见TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时，就会被转换回普通的桶。在使用分布良好的用户hashcode时，很少使用树箱。理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布

红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

集合最大容量

//集合最大容量的上限是：2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;

原因：

1 int类型是32位整型，占4个字节。

2 Java的原始类型里没有无符号类型。 –> 所以首位是符号位正数为0，负数为1

3 java中存放的是补码，1左移31位的为 16进制的0x80000000代表的是-2147483648–>所以最大只能是30

1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648

当链表的值小于6则会从红黑树转回链表

//当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;

当Map里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD (8)

//桶中结构转化为红黑树对应的数组长度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

table用来初始化(必须是二的n次幂)(重点)

//存储元素的数组 
transient Node<K,V>[] table;

table在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构其中table就是HashMap中的数组，jdk8之前数组类型是Entry<K,V>类型。从jdk1.8之后是Node<K,V>类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的。

用来存放缓存

//存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

HashMap中存放元素的个数(重点)

//存放元素的个数，注意这个不等于数组的长度。
 transient int size;

size为HashMap中K-V的实时数量，不是数组table的长度。

用来记录HashMap的修改次数

// 每次扩容和更改map结构的计数器
 transient int modCount;

用来调整大小下一个容量的值计算方式为(容量*负载因子)

// 临界值 当实际大小(容量*负载因子)超过临界值时，会进行扩容
int threshold;

哈希表的加载因子(重点)

// 加载因子
final float loadFactor;

说明：

1.loadFactor加载因子，是用来衡量 HashMap 满的程度，表示HashMap的疏密程度，影响hash操作到同一个数组位置的概率，计算HashMap的实时加载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的数量，也就是 table 的长度length。

loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。，所以开发中尽量减少扩容的次数，可以通过创建HashMap集合对象时指定初始容量来尽量避免。

同时在HashMap的构造器中可以定制loadFactor。

构造方法：
HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。

2.为什么加载因子设置为0.75,初始化临界值是12？

loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。

threshold计算公式：capacity(数组长度默认16) * loadFactor(负载因子默认0.75)。这个值是当前已占用数组长度的最大值。当Size>=threshold的时候，那么就要考虑对数组的resize(扩容)，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。扩容后的 HashMap 容量是之前容量的两倍.

遍历方式

public class HashMapStudy {
    public static void main(String[] args) {
        //一般来说,最好初始化一下, 小于12的就不要初始化了
        // 默认的就是16,因为加载因子是0.75,也就是到16*0.75=12的时候会扩容
        Map<String, String> map = new HashMap<>(3);

        map.put("welcome","to");
        map.put("java","study");
        map.put("wechat","best396975802");

        //遍历方法1: 先遍历key , 再取出value
        System.out.println("遍历方法1: 先遍历key , 再取出value");
        for (String key : map.keySet()) {
            System.out.println("key is "+key);
            System.out.println("value is "+ map.get(key));
        }
        //遍历方法2: 直接遍历value
        System.out.println("遍历方法2: 直接遍历value");
        for (String value : map.values()) {
            System.out.println("value is "+value);
        }

        //遍历方法3: 通过遍历entry来取Key和value,推荐的方法!!!
        System.out.println("遍历方法3: 通过遍历entry来取Key和value,推荐的方法!!!");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println("key is "+entry.getKey());
            System.out.println("value is "+ entry.getValue());
        }

        //遍历方法4: 通过forEach方法直接遍历key和value
        System.out.println("遍历方法4: 通过forEach方法直接遍历");
        map.forEach((key,value)->{
            System.out.println("key is "+ key);
            System.out.println("value is "+ value);
        });
    }
}

容量的初始化

把默认容量的数字设置成 initialCapacity/ 0.75F + 1.0F

集合概述

概念：对象的容器，定义了对多个对象进项操作的的常用方法。可实现数组的功能。
和数组的区别：

数组长度固定，集合长度不固定。
数组可以存储基本类型和引用类型，集合只能存储引用类型。

位置： java.util.*;

Collection

Collection父接口

特点：代表一组任意类型的对象，无序，无下标，不能重复。
方法：
- boolean add(Object obj) //添加一个对象。
- boolean addAll(Collection c) //讲一个集合中的所有对象添加到此集合中。
- void clear() //清空此集合中的所有对象。
- boolean contains(Object o) //检查此集合中是否包含o对象。
- boolean equals(Object o) //比较此集合是否与指定对象相等。
- boolean isEmpty() //判断此集合是否为空。
- boolean remove(Object o) //在此集合中移除o对象。
- int size() //返回此集合中的元素个数。
- Object[] toArray() //姜此集合转换成数组。

Collection子接口

LinkedList

增加：
add(E e)：在链表后添加一个元素；通用方法
addFirst(E e)：在链表头部插入一个元素；特有方法
addLast(E e)：在链表尾部添加一个元素；特有方法
push(E e)：与addFirst方法一致
offer(E e)：在链表尾部插入一个元素
add(int index, E element)：在指定位置插入一个元素。
offerFirst(E e)：JDK1.6版本之后，在头部添加；特有方法
offerLast(E e)：JDK1.6版本之后，在尾部添加；特有方法

删除：
remove() ：移除链表中第一个元素; 通用方法
remove(E e)：移除指定元素；通用方法
removeFirst(E e)：删除头，获取元素并删除；特有方法
removeLast(E e)：删除尾；特有方法
pollFirst()：删除头；特有方法
pollLast()：删除尾；特有方法
pop()：和removeFirst方法一致，删除头。
poll()：查询并移除第一个元素特有方法

查：
get(int index)：按照下标获取元素；通用方法
getFirst()：获取第一个元素；特有方法
getLast()：获取最后一个元素；特有方法
peek()：获取第一个元素，但是不移除；特有方法
peekFirst()：获取第一个元素，但是不移除；
peekLast()：获取最后一个元素，但是不移除；
pollFirst()：查询并删除头；特有方法
pollLast()：删除尾；特有方法
poll()：查询并移除第一个元素特有方法

ArrayList

1、add(Object element) 方法
2、size() 方法
3、get(int index) 方法
4、add(int index, Object element) 方法
5、set(int i, Object element) 方法
6、clear() 方法
7、isEmpty() 方法
8、iterator() 方法
9、contains(Object o) 方法
10、remove(int index) 方法
11、remove(Object o) 方法

Queue

add 增加一个元索如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素如果队列为空，则返回null
peek 返回队列头部的元素如果队列为空，则返回null
put 添加一个元素如果队列满，则阻塞
take 移除并返回队列头部的元素如果队列为空，则阻塞

PriorityQueue

// 最小堆完整代码
import java.util.PriorityQueue;
public class App {
    public static void main(String[] args) {
        // 创建一个最小堆实例
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
       
        // 创建一个空的最大堆
		//PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

		// 创建带初始值的「堆」， 或者称为「堆化」操作，此时的「堆」为「最小堆」
		//PriorityQueue<Integer> heapWithValues= new PriorityQueue<>(Arrays.asList(3,1,2));
        
        
        // 分别往最小堆中添加3，1，2
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);
        // 查看最小堆的所有元素，结果为：[1, 3, 2]
        System.out.println("minHeap: "+minHeap.toString());
        // 获取最小堆的堆顶元素
        int peekNum = minHeap.peek();
        // 结果为：1
        System.out.println("peek number: "+peekNum);
        // 删除最小堆的堆顶元素
        int pollNum = minHeap.poll();
        // 结果为：1
        System.out.println("poll number: "+pollNum);
        // 查看删除1后最小堆的堆顶元素，结果为：2
        System.out.println("peek number: "+minHeap.peek());
        // 查看新的最小堆的所有元素，结果为：[2,3]
        System.out.println("minHeap: "+minHeap.toString());
        // 查看最小堆的元素个数，也是最小堆的长度
        int heapSize = minHeap.size();
        // 结果为：2
        System.out.println("minHeap size: "+heapSize);
        // 判断最小堆是否还有元素
        boolean isEmpty = minHeap.isEmpty();
        // 结果为： false
        
        System.out.println("isEmpty: "+isEmpty);
    }
}

HashSet

public class Main {
    public static void main(String[] args) {
        // 1. 初始化哈希集合
        Set<Integer> hashSet = new HashSet<>();     
        // 2. 新增键
        hashSet.add(3);
        hashSet.add(2);
        hashSet.add(1);
        // 3. 删除键
        hashSet.remove(2);        
        // 4. 查询键是否包含在哈希集合中
        if (!hashSet.contains(2)) {
            System.out.println("键 2 不在哈希集合中");
        }
        // 5. 哈希集合的大小
        System.out.println("哈希集合的大小为: " + hashSet.size());     
        // 6. 遍历哈希集合
        for (Integer i : hashSet) {
            System.out.print(i + " ");
        }
        System.out.println("在哈希集合中");
        // 7. 清空哈希集合
        hashSet.clear();
        // 8. 查看哈希集合是否为空
        if (hashSet.isEmpty()) {
            System.out.println("哈希集合为空！");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // 1. 初始化哈希表
        Map<Integer, Integer> hashmap = new HashMap<>();
        // 2. 插入一个新的（键，值）对
        hashmap.putIfAbsent(0, 0);
        hashmap.putIfAbsent(2, 3);
        // 3. 插入一个新的（键，值）对，或者更新值
        hashmap.put(1, 1);
        hashmap.put(1, 2);
        // 4. 获得特定键对应的值
        System.out.println("键 1 对应的值为: " + hashmap.get(1));
        // 5. 删除键
        hashmap.remove(2);
        // 6. 检查键是否存在于哈希表中
        if (!hashmap.containsKey(2)) {
            System.out.println("键 2 不在哈希表中");
        }
        // 7. 哈希表的大小
        System.out.println("哈希表的大小为: " + hashmap.size()); 
        // 8. 遍历哈希表
        for (Map.Entry<Integer, Integer> entry : hashmap.entrySet()) {
            System.out.print("(" + entry.getKey() + "," + entry.getValue() + ") ");
        }
        System.out.println("在哈希表中");
        // 9. 清空哈希表
        hashmap.clear();
        // 10. 检查哈希表是否为空
        if (hashmap.isEmpty()) {
            System.out.println("哈希表为空！");
        }
    }
}

Hexo

Java集合框架

HashMap

方法

简介

特点：

数据结构

继承关系

成员

成员变量

遍历方式

容量的初始化

集合概述

Collection

Collection父接口

Collection子接口

LinkedList

ArrayList

Queue

PriorityQueue

HashSet

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

Hexo

HashMap

方法

简介

特点：

数据结构

继承关系

成员

成员变量

遍历方式

容量的初始化

集合概述

Collection

Collection父接口

Collection子接口

LinkedList

ArrayList

Queue

PriorityQueue

HashSet

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可