【Java 集合框架】帮你搞通哈希表，掌握 Map 和 Set 的使用（内含哈希表源码解读及面试常考题）

转x33g5p2x  于2021-12-15 转载在 Java  
字(14.3k)|赞(0)|评价(0)|浏览(760)

1. 搜索

1.1 场景引入

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

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

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

本章将会介绍 Map 和 Set，它们是一种适合动态查找的集合容器或者数据结构。

1.2 模型

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

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

  1. 纯 Key 模型： Set 的存储模式，比如：
  2. Key-Value 模型： Map 的存储模式，比如：

2. Map

2.1 关于 Map 的介绍

简单介绍：

注意：

文档信息：

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

简单介绍：

常用方法：

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

注意：

文档信息：

2.3 Map 的常用方法说明

方法说明
V get(Object key)返回 key 的对应 value
V getOrDefault(Object key, V defaultValue)返回 key 对应的 value，若 key 不存在，则返回默认值 defaultValue
V put(K key, V value)设置 key 的对应值为 value
V remove(Object key)删除 key 对应的映射关系
Set<K> keySet()返回所有 key 的不重复集合
Collection<V> values()返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 keys
boolean containsValue(Object value)判断是否包含 value

注意：

2.4 关于 HashMap 的介绍

简单介绍：

注意：

文档信息：

2.5 关于 TreeMap 的介绍

简单介绍：

注意：

文档信息：

2.6 HashMap 和 TreeMap 的区别

Map 底层结构TreeMapHashMap
底层结构红黑树哈希桶（链表+数组+红黑树）
插入/删除/查找时间复杂度O(logN)O(1)
是否有序关于 Key 有序无序
线程安全不安全安全
插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址
比较覆写Key 必须能够比较，否则会抛出 ClassCastException 异常自定义类型需要覆写 equals 和 hashCode 方法
应用场景需要 Key 有序不关心 Key 是否有序，满足于需要更高的时间性能

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=惠城 Value=法师 Key=晓 Value=刺客 Key=喵班长 Value=盗剑客 */

示例七： 判断是否包含 key

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

3. Set

3.1 关于 Set 的介绍

简单介绍：

注意：

文档信息：

3.1 Set 的常用方法说明

方法说明
boolean add(E e)添加元素，但重复元素不会被添加成功
void clear()清空集合
boolean contains(Object o)判断 o 是否在集合中
Iterator<E> iterator()返回迭代器
boolean remove(Object o)删除集合中的 o
int size()返回 set 中元素的个数
boolean isEmpty()检测 set 是否为空，空返回 true，否则返回 false
Object[] toArray()将 set 中的元素转换为数组返回
boolean addAll(Collection<? extends E> c)将集合 c 中的元素添加到 set 中，可以达到去重效果
boolean containsAll(Collection<?> c)集合 c 中的元素是否在 set 中全部存在，是返回 true，否则返回 false

注意：

3.3 关于 TreeSet 的介绍

简单介绍：

注意：

文档信息：

3.4 关于 HashSet 的介绍

简单介绍：

注意：

文档信息：

3.5 TreeSet 和 HashSet 的区别

Set 底层结构TreeSetHashSet
底层结构红黑树哈希桶
插入/删除/查找时间复杂度O(log(N))O(1)
是否有序关于 Key 有序不一定有序
线程安全不安全不安全
插入/删除/查找区别按照红黑树的特性来进行插入和删除先计算 key 哈希地址，再进行插入和删除
比较与覆写key 必须能够比较，否则会抛出 ClassCastException 异常自定义类型需要覆写 equals 和 hashCode 方法
应用场景需要 Key 有序场景Key 是否有序不关心，需要更高的时间性能

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

示例八： 清空集合

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 链接）：

代码：

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 链接）：

代码：

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 链接）：

代码：

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 概念

简单介绍：

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

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

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

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

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

5.2 哈希冲突——概念

简单介绍：

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

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

5.3 哈希冲突——避免

5.3.1 哈希函数设计

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

哈希函数的设计原则：

常见哈希函数：

  1. 直接定制法（常用）
  2. 除留余数法（常用）
  3. 平方取中法（了解）
  4. 折叠法（了解）
  5. 随机数法（了解）
  6. 数学分析法（了解）

5.3.2 负载因子调节

负载因子定义：

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

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

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

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

5.4 哈希冲突——解决

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

5.4.1 闭散列

简单介绍：

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

  1. 线性探测
  2. 二次探测

缺点：

5.4.2 开散列/哈希桶

简单介绍：

补充：

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

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

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

冲突严重时的解决办法：

5.5 相关习题

补充： Hash表的平均查找长度（ASL）包括查找成功时的平均查找长度和查找失败时的平均查找长度

题目：

  • 查找成功的平均查找长度为：20/9

  • 查找不成功的平均查找长度为：58/11

5.6 性能分析

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

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

6. 手动实现 HashMap（提及 hashCode 和 equals 的作用）

  1. HashMap 底层是：数组+单链表
  2. 我们可以先定义一个最基础的哈希表，让他可以实现整形的存值、取值等（哈希函数设定为：Hash(Key) = Key % capacity)
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;
            }
        }
    }
}
  1. 当我们实现了对整形的部分哈希表的实现后，如果要实现其它类型是有问题的，因为我们设计的哈希函数为：Hash(Key) = Key % capacity，而其它类型都不能取模，因此我们需要能够对 Key 进行数字转换的方法。而在 Object 类有一个 hashCode() 方法，它能将传过来的对象，转换成一个合法的数字，以此来找到合适的位置，因此使用它就能解决我们上述的麻烦。除此之外，上述代码中的一些==需要修改为 equals() 方法，因为 equals 它能够判断传入的对象的实例是否相等
  2. 通过上面一部分的分析，最终可以得到如下代码
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 类集的关系

  • HashMap 和 HashSet 即 Java 中利用哈希表实现的 Map 和 Set
  • Java 中会使用哈希桶解决哈希冲突
  • Java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）。具体数值为当前链表的长度超过8且当前桶的个数大于等于64时，就会将当前长度超过8的链表变为红黑树
  • Java 中计算哈希值实际上是调用 Object 类的 hashCode 方法，进行 Key 的相等性比较是调用的 equals 方法
  • 自定义类如果需要作为 HashMap 的 Key 或者 HashSet 的值，必须重写 hashCode 和 equals 方法

9. HashMap 部分源码解读

  • HashMap 的默认容量是：16

  • HashMap 的最大容量为：1 << 30（必须为2的倍数）

  • HashMap 默认负载因子为：0.75

  • HashMap 中的单链表变为红黑树的条件，该值将在 putVal 方法中出现

  • HashMap 有四种构造方法

  • 方法一： 没有参数，则哈希表容量为：0，负载因子为：0.75

  • 方法二： 传入一个 Map 参数，则哈希表负载因子为：0.75

  • 方法三： 传一个容量参数 initialCapacity，则哈希表容量为：initialCapacity，负载因子为：0.75

  • 方法四： 传两个参数，容量参数 initialCapacity，负载因子参数 loadFactor，则哈希表负载因子为：loadFactor

但是哈希表容量在这里不能确定，它有一个 tableSizeFor 的方法，为此我们转到它的源码

这个方法的意思是返回一个最近接传入的 initialCapacity 参数的向上取整的2的次方的数字，例如传入的参数为18，那么哈希表的容量就为32，传入的参数为1000，那么哈希表的容量就为1024

  • put 方法的实现

  • hash 方法的实现，由于 hashCode 被 native 修饰，故无法看到具体源码

  • putVal 方法的实现（代码太长，就直接复制代码了，个人在下面代码中做了注释）

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 数组有多大？
  • 问题二：HashMap 什么时候开辟 bucket 数组占用内存？
  • 问题三：HashMap 何时扩容？
  • 问题四：当两个对象的 hashCode 相同时会发生什么？
  • 问题五：如果两个键的 hashCode 相同，你如何获取值对象？
  • 问题六：你了解重新调整 HashMap 大小存在什么问题吗？

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_51367845/article/details/121943746

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构面试javase散列表

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多

    目录

    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com