文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java 集合框架掌握 Map 和 Set 的使用(内含哈希表源码解读及面试常考题)

2024-04-02 19:55

关注

1. 搜索

1.1 场景引入

在学习编程时,我们常见的搜索方式有:

但是上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作。

而现实中的查找如:

可能在查找时需要进行一些插入和删除操作,即动态查找。因此上述排序的方式就不太适合。

1.2 模型

一般会把要搜索的数据称为关键字(Key),和关键字对应的称为值(Value),这两者又能组合成为 Key-Value 的键值对。

因此动态查找的模型有下面两种:

纯 Key 模型: Set 的存储模式,比如:

Key-Value 模型: Map 的存储模式,比如:

2. Map

2.1 关于 Map 的介绍

简单介绍:

Map 是一个接口类,没有继承自 Collection。该类中存储的是 <K, V> 结构的键值对,并且 K 一定是唯一的,不能重复

注意:

  • Map 接口位于 java.util 包中,使用前需要引入它
  • Map 是一个接口类,故不能直接实例化对象。如果要实例化对象只能实例化其实现类 TreeMap 或 HashMap
  • Map 中存放的键值对的 Key 是唯一的,Value 是可以重复的

文档信息:

2.2 关于 Map.Entry<K, V> 的介绍

简单介绍:

Map.Entry<K, V> 是 Map 内部实现的用来存放 <Key, Value> 键值对映射关系的内部类。该内部类中主要提供了 <Key, Value> 的获取,Value 的设置以及 Key 的比较方式

常用方法:

方法说明
K getKey()返回 entry 中的 key
V getValue()返回 entry 中的 value
V setValue(V value)将键值对中的 value 替换为指定的 value

注意:

Map.Entry<K, V> 并没有提供设置 Key 的方法

文档信息:

2.3 Map 的常用方法说明

注意:

2.4 关于 HashMap 的介绍

简单介绍:

注意:

HashMap 类位于 java.util 包中,使用前需要引入它

文档信息:

2.5 关于 TreeMap 的介绍

简单介绍:

注意:

TreeMap 类位于 java.util 包中,使用前需要引入它

文档信息:

2.6 HashMap 和 TreeMap 的区别

2.7 Map 使用示例代码

注意:Map 是一个接口类,故不能直接实例化对象,以下以 HashMap 作为实现类为例

示例一: 创建一个 Map 实例


Map<String,String> map=new HashMap<>();

示例二: 插入 key 及其对应值为 value


map.put("惠城","法师");
map.put("晓","刺客");
map.put("喵班长","盗剑客");
System.out.println(map);
// 结果为:{惠城=法师, 晓=刺客, 喵班长=盗剑客}

示例三: 返回 key 的对应 value


String str1=map.get("晓");
System.out.println(str1);
// 结果为:刺客

示例四: 返回 key 对应的 value,若 key 不存在,则返回默认值 defaultValue


String str2=map.getOrDefault("弥惠","冒险者");
System.out.println(str2);
// 结果为:冒险者

示例五: 删除 key 对应的映射关系


String str3=map.remove("喵班长");
System.out.println(str3);
System.out.println(map);
// 结果为:盗剑客 和 {惠城=法师, 晓=刺客}

示例六: 除了上述直接打印 map,也可以通过 Set<Map.Entry<K, V>> entrySet() 这个方法进行遍历打印


Set<Map.Entry<String,String>> set=map.entrySet();
for(Map.Entry<String,String> str: set){
    System.out.println("Key="+str.getKey()+" Value="+str.getValue());
}

 


示例七: 判断是否包含 key


System.out.println(map.containsKey("惠城"));
// 结果为:true
 


3. Set

3.1 关于 Set 的介绍

简单介绍:

Set 是一个继承于 Collection 的接口,是一个不允许出现重复元素,并且无序的集合,主要有 HashSet 和 TreeSet 两大实现类。

注意:

Set 接口位于 java.util 包中,使用前需要引入它

文档信息:

3.1 Set 的常用方法说明

注意:

Set 中只继承了 Key,并且要求 Key 唯一
Set 的底层是使用 Map 来实现的,其使用 Key 与 Object 的一个默认对象作为键值对插入插入到 Map 中
Set 的最大功能就是对集合中的元素进行去重
实现 Set 接口的常用类有 TreeSet HashSet,还有一个 LinkedHashSetLinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序
Set 中的 Key 不能修改,如果修改,要先将原来的删除
Set 中可以插入 null

3.3 关于 TreeSet 的介绍

简单介绍:

TreeSet 实现类 Set 接口,基于 Map 实现,其底层结构为红黑树

注意:

TreeSet 类位于 java.util 包中,使用前需要引入它

文档信息:

3.4 关于 HashSet 的介绍

简单介绍:

注意:

HashSet 类位于 java.util 包中,使用前需要引入它

文档信息:

3.5 TreeSet 和 HashSet 的区别

3.6 Set 使用示例代码

注意:Set 是一个接口类,故不能直接实例化对象,以下以 HashSet 作为实现类为例

示例一: 创建一个 Set 实例


Set<Integer> set=new HashSet<>();


示例二: 添加元素(重复元素无法添加成功)


set.add(1);
set.add(2);
set.add(3);
set.add(4);
set.add(5);
System.out.println(set);
// 结果为:[1, 2, 3, 4, 5]
 

示例三: 判断 1 是否在集合中


System.out.println(set.contains(1));
// 结果为:true


示例四: 删除集合中的元素


System.out.println(set.remove(3));
// 结果为:true


示例五: 返回 set 中集合的个数


System.out.println(set.size());
// 结果为:4
 

示例六: 检测 set 是否为空


System.out.println(set.isEmpty());
// 结果为:false


示例七: 返回迭代器,进行遍历


Iterator<Integer> it=set.iterator();
while(it.hasNext()){
    System.out.println(it.next());
}
// 结果为:1 2 4 5 


hashNext() 方法是判断当前元素是否还有下一个元素,next() 是获取当前元素,并且指向下一个元素

示例八: 清空集合


set.clear();
System.out.println(set);
// 结果为:[]



4. 编程练习题

4.1 找出第一个重复数据

题目:

从一些数据中,打印出第一个重复数据

代码:


public static void findNum(int[] array){
    Set<Integer> set=new HashSet<>();
    for(int i=0;i<array.length;i++){
        if(set.contains(array[i])){
            System.out.println(array[i]);
            break;
        }
        set.add(array[i]);
    }
}
 

4.2 去除重复数据

题目:

去除一些数据当中重复的数据

代码:


public static int[] removeSample(int[] array){
    Set<Integer> set=new HashSet<>();
    for(int i=0;i<array.length;i++){
        set.add(array[i]);
    }
    Object[] arr=set.toArray();
    return array;
}
 

4.3 统计重复数据的出现次数

题目:

统计重复的数据出现的次数

代码:


public static Map count(int[] array){
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<array.length;i++){
        if(map.containsKey(array[i])){
            int val=map.get(array[i]);
            map.remove(array[i]);
            map.put(array[i],val+1);
        }else {
            map.put(array[i], 1);
        }
    }
    return map;
}
 

4.4 只出现一次的数字

题目(OJ 链接):

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素

代码1: 异或法


public int singleNumber(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++){
        sum=sum^nums[i];
    }
    return sum;
}
 

代码2: 使用 HashSet


public int singleNumber(int[] nums) {
    Set<Integer> set=new HashSet<>();
    for(int val: nums){
        if(set.contains(val)){
            set.remove(val);
        }else{
            set.add(val);
        }
    }
    for(int val: nums){
        if(set.contains(val)){
            return val;
        }
    }
    return -1;
}


4.5 复制带随机指针的链表

题目(OJ 链接):

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

代码:


public static Node copyRandomList(Node head) {
    Map<Node,Node> map=new HashMap<>();
    Node cur=head;
    while(cur!=null){
        Node node=new Node(cur.val);
        map.put(cur,node);
        cur=cur.next;
    }
    cur=head;
    while(cur!=null){
        Node node=map.get(cur);
        node.next=map.get(cur.next);
        node.random=map.get(cur.random);
        cur=cur.next;
    }
    return map.get(head);
}


4.6 宝石与石头

题目(OJ 链接):

给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

字母区分大小写,因此 “a” 和 “A” 是不同类型的石头。

代码:


    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set=new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            set.add(jewels.charAt(i));
        }
        int count=0;
        for(int i=0;i<stones.length();i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }


4.7 旧键盘

题目(OJ 链接):

旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字,请你列出
肯定坏掉的那些键。

代码:


import java.util.*;

public class Main{
    public static void main(String[] args){
        Set<Character> set=new HashSet<>();
        List<Character> list=new ArrayList<>();
        Scanner scanner=new Scanner(System.in);
        String str1=scanner.next();
        String str2=scanner.next();
        char[] s1=str1.toUpperCase().toCharArray();
        char[] s2=str2.toUpperCase().toCharArray();
        for(int i=0;i<s2.length;i++){
            set.add(s2[i]);
        }
        for(int i=0;i<s1.length;i++){
            if(!set.contains(s1[i])){
                set.add(s1[i]);
                System.out.print(s1[i]);
            }
        }
    }
}


4.8 前 K 个高频单词

题目(OJ 链接):

给一非空的单词列表,返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。

代码:


public List<String> topKFrequent(String[] words, int k) {
    Map<String,Integer> map=new HashMap<>();
    for(String s: words){
        if(map.containsKey(s)){
            map.put(s,map.get(s)+1);
        }else{
            map.put(s,1);
        }
    }
    PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
        @Override
        public int compare(Map.Entry<String,Integer> s1, Map.Entry<String,Integer> s2){
            if(s1.getValue().compareTo(s2.getValue())==0){
                return s2.getKey().compareTo(s1.getKey());
            }
            return s1.getValue()-s2.getValue();
        }
    });
    for(Map.Entry<String,Integer> entry: map.entrySet()){
        if(minHeap.size()<k){
            minHeap.add(entry);
        }else{
            if(entry.getValue().compareTo(minHeap.peek().getValue())>0){
                minHeap.poll();
                minHeap.offer(entry);
            }else if(entry.getValue().compareTo(minHeap.peek().getValue())==0){
                if(entry.getKey().compareTo(minHeap.peek().getKey())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }
    }
    List<String> list=new ArrayList<>();
    for(int i=0;i<k;i++){
        Map.Entry<String,Integer> top=minHeap.poll();
        list.add(top.getKey());
    }
    Collections.reverse(list);
    return list;
}
 


5. 哈希表

5.1 概念

简单介绍:

哈希表(也叫做散列表),是根据关键码(Key Value)而直接进行访问的数据结构。它通过把关键码映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数叫做哈希函数(也叫做散列函数),存放记录的数组叫做哈希表(也叫散列表)

在之前讲解的数据结构中,元素关键码及其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较,搜索的效率取决于搜索过程中元素的比较次数。例如:

我们希望有一种理想的搜索方法,它可以不经过任何比较,能直接从表中得到要搜索的元素。因此就有了哈希表,它的原理就是:通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,例如:

插入元素:

根据待插入元素的关键码,以某个函数计算出该元素的存储位置,并按此位置进行存放

搜索元素:

用该函数对元素的关键码进行计算,把求得的函数值当作元素的存储位置,在此结构中按此位置取元素与要搜索的元素进行比较,若关键码相等,则搜索成功

上述的方法就叫做哈希方法(也叫散列方法),其中哈希方法中使用的转换函数称为哈希函数(也叫做散列函数),构造出来的结构称为哈希表(也叫散列表)

示例: 当我们将哈希函数设置为:hash(key) = key % capacity 时,我们往一个数组中存放以下几个元素,存放形式如下

但是使用哈希方法会出现一个问题:哈希冲突

5.2 哈希冲突——概念

简单介绍:

哈希冲突(也叫做哈希碰撞),是指对于两个数据元素的关键字 ki 和 kj (i != j),虽然 ki != kj,但是存在:Hash(ki) == Hash(kj),即不同关键字通过相同哈希函数,可能会计算出相同的哈希地址

示例: 当我们将哈希函数设置为:hash(key) = key % capacity 时,元素 3 和 13 通过该哈希函数计算出的存放位置是一样的

由于哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致,哈希冲突的发生是必然的。并且哈希冲突不能根本上消除,为此我们就要

5.3 哈希冲突——避免

5.3.1 哈希函数设计

引起哈希冲突的一个原因可能是:哈希函数设计不合理

哈希函数的设计原则:

常见哈希函数:

直接定制法(常用)

除留余数法(常用)

平方取中法(了解)

折叠法(了解)

随机数法(了解)

数学分析法(了解)

5.3.2 负载因子调节

负载因子定义:

散列表的载荷因子定义为:α = 填入表中的元素个数 / 散列表的长度

α 是散列表装满程度的标志因子。由于表长是定值,α 与填入表中的元素个数成正比,所以 α 越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之 α 越小,表名填入表中的元素越少,产生冲突的可能性就越小

一些采用开放定址法的 hash 库,如 Java 的系统库限制了载荷因子为0.75,超过此值将 resize 散列表

负载因子和冲突率的关系粗略演示图:

通过演示图我们可以很直观的了解,当冲突率越大时,我们需要通过降低负载因子来变相降低冲突率。而填入表中的元素个数已成定局,我们不能够修改,因此需要调整哈希表中的数组大小,即调整散列表长度

5.4 哈希冲突——解决

解决哈希冲突两种常见的方法:

5.4.1 闭散列

简单介绍:

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明哈希表中必然还有空位置,那么可以把 Key 存放到冲突位置的下一个空位置中去

寻找冲突位置下一个空位置的方法:

线性探测

二次探测

5.4.2 开散列/哈希桶

简单介绍:

开散列:也叫做链地址法或开链法或哈希桶,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶的元素通过一个单链表连接起来,各个链表的头节点存储在哈希表中

补充:

HashMap 的底层就是一个开散列

可以认为开散列是把一个在大集合中的搜索问题转化为在小集合中做搜索

由于会尽量避免冲突,所以冲突率其实会有保障,因此当在单链表中做搜索时,其实很快,时间复杂度接近:O(1)

但是当冲突很严重时,那么在单链表这个小集合中做搜索其实性能就会大大降低,因此单链表就不太适合做小集合的结构

冲突严重时的解决办法:

5.5 相关习题

补充: Hash表的平均查找长度(ASL)包括查找成功时的平均查找长度和查找失败时的平均查找长度

题目:

设哈希表长度为11,哈希函数 H(K) = (K的第一个字母在字母表中的序号) % 11,若输入顺序为(D、BA、TN、M、CI、I、K、X、TA),采用闭散列处理冲突方法为线性探测,要求构造哈希表,在等概率的情况下查找成功的平均查找长度为( ),查找不成功的平均查找长度为( )

5.6 性能分析

虽然哈希表一直在和冲突做斗争,但在实际使用过程中,哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数。

因此,通常意义下我们认为哈希表的插入、删除、查找时间复杂度为:O(1)

6. 手动实现 HashMap(提及 hashCode 和 equals 的作用)


class HashBuck{
    static class Node{
        public int key;
        public int value;
        public Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public Node[] array;
    public int usedSize;
    public HashBuck(){
        this.array=new Node[8];
    }
    // 获取 key 对应的 value
    public int get(int key){
        int index=key%this.array.length;
        Node cur=this.array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;  // 这里先用 -1 返回,也可以抛异常
    }
    // 新增元素
    public void put(int key, int val){
        int index=key%this.array.length;
        Node cur=this.array[index];
        Node node=new Node(key,val);
        if(cur==null){
            this.array[index]=node;
        }else{
            while(cur.next!=null){
                if(cur.key==key){
                    cur.value=val;
                    break;
                }
                cur=cur.next;
            }
            cur.next=node;
        }
        this.usedSize++;
        if(loadFactor()>=0.75){
            resize();
        }
    }
    // 计算负载因子
    public double loadFactor(){
        return this.usedSize*1.0/this.array.length;
    }
    // 扩容后,重新构造哈希
    public void resize(){
        Node[] oldArray=this.array;
        this.array=new Node[2*oldArray.length];
        this.usedSize=0;
        for(int i=0;i<oldArray.length;i++){
            Node cur=oldArray[i];
            while(cur!=null){
                put(cur.key,cur.value);
                cur=cur.next;
            }
        }
    }
}

 当我们实现了对整形的部分哈希表的实现后,如果要实现其它类型是有问题的,因为我们设计的哈希函数为:Hash(Key) = Key % capacity,而其它类型都不能取模,因此我们需要能够对 Key 进行数字转换的方法。而在 Object 类有一个 hashCode() 方法,它能将传过来的对象,转换成一个合法的数字,以此来找到合适的位置,因此使用它就能解决我们上述的麻烦。除此之外,上述代码中的一些==需要修改为 equals() 方法,因为 equals 它能够判断传入的对象的实例是否相等

通过上面一部分的分析,最终可以得到如下代码:


class HashBuck<K,V>{
    static class Node<K,V>{
        public K key;
        public V val;
        public Node<K,V> next;
        public Node(K key,V val){
            this.key=key;
            this.val=val;
        }
    }
    public Node<K,V>[] array=new Node[8];
    public int usedSize;

    public void put(K key,V val){
        int hash=key.hashCode();
        int index=hash%this.array.length;
        Node<K,V> cur=this.array[index];
        Node<K,V> node=new Node<K,V>(key,val);
        if(cur==null){
            this.array[index]=node;
        }else{
            while(cur.next!=null){
                if(cur.key.equals(key)){
                    cur.val=val;
                    break;
                }
                cur=cur.next;
            }
            cur.next=node;
        }
        this.usedSize++;
        if(loadFactor()>=0.75){
            resize();
        }
    }
    public V get(K key){
        int hash=key.hashCode();
        int index=hash%this.array.length;
        Node<K,V> cur=this.array[index];
        while(cur!=null){
            if(cur.key.equals(key)){
                return cur.val;
            }
            cur=cur.next;
        }
        return null;
    }
    // 计算负载因子
    public double loadFactor(){
        return this.usedSize*1.0/this.array.length;
    }
    // 重新哈希
    public void resize(){
        Node<K,V>[] oldArray=this.array;
        this.array=(Node<K, V>[]) new Node[2*oldArray.length];
        this.usedSize=0;
        for(int i=0;i<oldArray.length;i++){
            Node<K,V> cur=oldArray[i];
            while(cur!=null){
                put(cur.key,cur.val);
                cur=cur.next;
            }
        }
    }
}
 

7. hashCode 和 equals 的关系

如果 hashCode 一样,那么 equals 会一样吗?

如果 equals 一样,那么 hashCode 一样吗?

8. 哈希和 Java 类集的关系

9. HashMap 部分源码解读


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 当哈希表的大小为 0 时,进行 resize 调整
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // ((n - 1) & hash) 其实等价于 (n % 数组长度) 但是前提条件是,n是2的次幂
    // 如果为 null 就是第一次插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果不为 null,就进行尾插法
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 当单链表的长度大于8时,转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}


resize 方法的实现(以2倍的方式进行扩容)


final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
} 

10. HashMap 常考问题

问题一:如果 new HashMap(19),那么 bucket 数组有多大?

32,原因在第9大节的构造方法四中

问题二:HashMap 什么时候开辟 bucket 数组占用内存?

第一次 put 的时候

问题三:HashMap 何时扩容?

当填入的元素/容量大于负载因子的时候,进行扩容,jdk1.8 负载因子默认为0.75

问题四:当两个对象的 hashCode 相同时会发生什么?

会发生哈希冲突

问题五:如果两个键的 hashCode 相同,你如何获取值对象?

遍历当前位置的链表,通过 equals 返回和要查询的 Key 值一样的 Key 的 Value

问题六:你了解重新调整 HashMap 大小存在什么问题吗?

重新调整大小一定要进行重新哈希

到此这篇关于Java 集合框架掌握 Map 和 Set 的使用(内含哈希表源码解读及面试常考题)的文章就介绍到这了,更多相关Java 集合框架掌握 Map 和 Set 的使用内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯