二本26届大三Java实习准备 Day3

2025 年 2 月 26 日 Day 3

今天把集合的内容基本看完了, 但是有很多比较深入的部分我觉得目前可以不了解太深入比如 concurrentHashMap 的底层源码; 看了好几个视频发现确实设计地很巧妙而且如果要面试的话挺多方面都能问的但是 Java 并发部分还没复习到看起来还是比较吃力;
接下来计划学习 java 并发和 JVM 的内容计划 3 天完成; 然后这几天可能敲一下 SpringAI 的项目用来丰富一下项目经历

今日算法题

• 最长回文子串

都是之前写过题, 但是写 DP 版都费劲; 和第一次写没区别; 推荐左程云老师的算法课非常通俗易懂; manacer 版本看了挺久原理还是很好理解画一画图; 但是代码抠细节比较花时间

• 相关视频

• DP 版

class Solution {
    public String longestPalindrome(String s) {
        int l = s.length();
        if (l == 1) return s;

        int[][] map = new int[l][l];
        int maxLenght = -1;
        int resLeft = 0, resRight = 0;

        for (int i = 0; i < l; i++) {
            map[i][i] = 1;
        }
        for (int j = 0; j < l; j++) {
            for (int i = 0; i < j; i++) {
                if(s.charAt(i) == s.charAt(j)){
                    map[i][j] = map[i + 1][j - 1] != -1 ? 2 + map[i + 1][j - 1] : -1;
                    if(map[i][j] > 0 && maxLenght < map[i][j]){
                        maxLenght = map[i][j];
                        resLeft = i;
                        resRight = j;
                    }
                }else{
                    map[i][j] = -1;
                }
            }
        }
        return s.substring(resLeft, resRight + 1);
    }
}

• manacher 算法

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 1) return s;
//        获取处理串
        StringBuilder str = new StringBuilder();
        str.append("@");
        for (int i = 0; i < s.length(); i++) {
            str.append(s.charAt(i));
            str.append("@");
        }

//        计算回文半径数组
        int R = -1; // 到达过的最右边界
        int C = -1; // 最右边界中心

        int max = -1; // 最长回文子串长度
        int maxC = -1; // 最长回文子串中心下标

        int[] arr = new int[str.length()];

        for (int i = 0; i < arr.length; i++) {

            if (i > R) {
//                当前位置i在[R', R]外
//                暴力
                arr[i] = 0;
                for (int j = 0; i - j >= 0 && i + j < str.length(); j++) {
                    if (str.charAt(i - j) == str.charAt(i + j)) {
                        arr[i]++;
                        if (i + j > R) {
//                            更新最右边界
                            R = i + j;
                            C = i;
                        }
                    } else {
                        break;
                    }
                }
            } else {
//                在[R',R]内  分为一下三种情况
                int il = 2 * C - i; // 获取i的对称点 i'
                int Rl = 2 * C - R; // 货如R的右边界

                if (il - arr[il] + 1> Rl) {
//                  1.  i'的回文左边界在R'内部
                    arr[i] = arr[il];
                } else if (il - arr[il] + 1 < Rl) {
//                  2.  i'的回文左边界在R' 外部
                    arr[i] = R - i + 1;
                } else {
//                    3.  i'的回文左边界在R' 边界上
//                    从R+1处开始暴力
                    arr[i] = arr[il];
                    for (int j = R - i + 1; i - j >= 0 && i + j < str.length(); j++) {
                        if (str.charAt(i - j) == str.charAt(i + j)) {
                            arr[i]++;
                            if (i + j > R) {
//                            更新最右边界
                                R = i + j;
                                C = i;
                            }
                        } else {
                            break;
                        }
                    }
                }
            }
            
            //            更新最优解
            if (arr[i] > max) {
                max = arr[i];
                maxC = i;
            }
        }

//        System.out.println(Arrays.toString(arr));
//        System.out.println(str);
//        System.out.println(maxC - max + 1);
//        System.out.println(maxC + max);
//        System.out.println(str.substring(maxC - max + 1, maxC + max));
        return str.substring(maxC - max + 1, maxC + max).replace("@", "");
    }
}

集合

HashMap、TreeMap、TreeMapHashtable 和 ConcurrentHashMap 的区别？

HashMap 的底层是数组+链表+红黑树

• 非线程安全 TreeMap 的底层是红黑树
• 非线程安全 HashTable 的底层是数组+链表
• 线程安全但是锁的是全表, 性能很低
• 扩容到原大小 2 倍+1 ConcurrentHashMap 底层是分段数组+链表+红黑树
• 线程安全, 锁的不再是全表而是锁的某部分数据; 1.8 之前锁的是数据段 1.8 之后锁的是单个数组节点

HashMap 用在并发场景中有什么问题? 如何解决的?

在 jdk 1.8 之前会出现在并发扩容环境下可能让链表变成环的情况; 虽然在后续版本中修复了成环的问题但是 HashMap 依然不是线程安全的; 推荐使用 HashTable 或者是并发性能更高的 ConcurrentHashMap

HashMap 的扩容成环问题的最主要原因就是因为 1.8 之前才用的头插法来重新排列链表在新节点中的位置; 这会让节点之间的顺序发生变化, 如果一个线程在挂起之前恰好记录下了两个节点的相对关系, 但是其他现在在获取到制空权之后进行了扩容操作, 那么当原先的线程被唤醒时会用之前记录的节点关系进行再次扩容, 这就会出现循环依赖导致成环; 后续版本中将头插法改成了尾插法, 这样不会破坏两个链表节点之间的相对位置, 就算在多线程竞争的环境在也不会出现成环的问题

HashMap 的 put get remove 流程

put

• 方法传入 key 和 value 键值对; 然后调用 hash 方法, 方法中会调用 key 的 hashCode 方法获取 key 对于的 hash 值, 然后对 hashCode 高位和低位进行异化扰动, 这一步是为了降低重复率; 然后在对得到的值和 map 中数组的长度-1 进行逻辑与操作得到键值对应该存储的数组下标; (因为数组长度固定是 2 的幂, n - 1 则会得到全为 1 的掩码在和 hashCode 与运算就相当于对数组长度取余) 找到键值对应该存储的位置后就需要判断位置上是否已经有元素了, 如果位置上为 null 那么就直接存储即可; 如果位置上已经有元素了说明发生 hash 冲突了, JDK 中采用的上链地址法, 所以判断位置上的结构是链表还是红黑树, 在根据结构不同把元素存储即可; get
• 步骤和 put 前面都相同在计算完成元素应该在的下标后, 就带指定位置上一次查询是否存在, 如果是链表和红黑树结构就调用对应结构的查询方法 remove
• 前面步骤依旧相同, 查询到删除 key 应该存储的下标位置, 然后根据结构太不同进行查找, 如果查找到了就进行删除, 如果是链表结构删除中间节点后要保持其他元素的前后结构依然正确, 红黑树中删除元素后要进行调整 在插入和删除元素时可能会自动触发扩缩容机制; 当一个链表的元素大于等于 8 时就会将链表升级为红黑树, 删除红黑树的元素当元素小于等于 6 时就退化成链表; 如果数组中的容量操过了负载因子 (加载因子 laod factor)阈值就会触发自动扩容机制; 还有一种情况会触发就是当一个链表要升级为红黑树的过程中发现数组的长度不足 64 也会触发扩容

一致性 Hash

一致性 hash 算法可以实现在分布式场景下通过 hash 算法实现的不在均衡策略和提高分布式场景在数据迁移扩缩容效率; 先说一下一致性 hash , 一致性 hash 规定一个很大的环形带下是 2 的 32 次方; 这个大环上可以通过 hash 算法分布部署我们的服务器节点; 资源需要存储缓存的时候会通过 hash 计算出在环上的位置, 然后查找且在他前面的离他最近的节点进行存储； 说了他的实现基本实现再说说他是如何实现负载均衡和数据迁移扩缩容加速 对于负载均衡显而易见, 借助于 hash 的散列性, 我们可以均匀地将数据分布在环上, 这样对于每个服务器节点来说要处理的负载就是均衡的; 当然如果服务器节点较少的情况下可能出现倾斜的问题, 就说一部分服务器节点没有均匀分布导致大量的数据打向一个节点; 解决这个问题只需要通过物理节点虚拟出多个虚拟节点, 然后通过 hash 将这个虚拟节点分布在环上; 对于动态扩缩容的加速就可以对比常规的做法; 常规比如我们有 10. 太服务器我们会对资源的 hashCode 对 10 取模计算这个资源应该存储的服务器编号, 这种方案的问题就在于如果添加或者减少服务器节点那么就无法通过 hash 定位到之前的资源; 而一致性 hash 相当于一开始就给出了足够大的空间供提升和删除节点; 当环上新增一个节点时该节点会逆时针地寻找最近节点进行数据分担; 如果一个节点下线那么信息可以迁移到顺时针最近下个节点; 这样一来节点的变化引发的数据变化会很小, 就算一个节点上出现奔溃数据丢失也不影响其他节点数据的使用

介绍一下 HashTable

HashTable 是 HashMap 的多线程版本, 为了应付并发场景； 他实现线程安全的思想是对全表进行加锁

介绍一下 ConcurrentHashMap ,并说明上如何解决线程安全的

ConcurrentHashMap 可以看作 HashMap 的多线程并发版本; 为了解决 HashMap 在多线程场景下出现链表成环和其他并发问题而出现 map; 底层的结构和 HashMap 相同数组+链表+红黑树, 通过 CAS 和 Syschronize 组合实现更精细的锁粒度控制来实现高性能; 在 jdk 1.8 之前是通过分段锁实现的, 分段锁简单来说就是将 map 数组进行分段然后存储在一个 segments 数组中, 只有获取到每个 segments 数组中每个元素锁的线程才能进行操作, 并且还对的锁的竞争进行了优化, 一个 n 段的分段锁理论性能会比 HashTable 锁全表的方式提高 n 被以上的并发性能; 但是分段锁的性能在大并发的场景在还是很容易出现性能瓶颈所以在 jdk 1.8 开始采用 cas+syschronize 的方式实现将锁的颗粒度控制在每个桶节点上

除了线程安全外, 对于扩容操作也做出了优化, 在扩容的时候会采用多线程协同的方式每个线程负责一部分迁移数据来实现加速