58同城 后端

栈实现队列，队列实现栈，网上挺多答案的，你可以搜一搜，这个算法题比较麻，它非常多，建议你刷够 leetcode 的前 200 道题。如果你有时间的话，没时间你就看看面经看要去的公司可能会有哪些常见的算法题，记下来思路就行。后面的项目我建议你自己列一个文档，里面说明自己项目用了哪些技术，以及遇到的难点/亮点是什么，怎么解决的。表设计为什么怎么设计等待和项目相关的。然后通读几遍记在脑子里，这样面试这种项目的时候你就得心应手了。分库分表的话我觉得以一个大学毕业生的角度最少要知道有几种分库分表的方式，要答出来垂直/水平 分库分表的做法，以及分库分表之后会发生什么问题以及如何解决的？-跨库 join 的问题啊、数据存放在哪个分库、分表以及如何存放？读取时怎么从不同数据库读取？另外还要知道一下常规分库分表的中间件比如 mycat、sharding-jdbc 等等，大致了解一下，问到你怎么用的时候你就说以你目前的数据量暂时不需要进行分库分表，但是个人对这方面还比较感兴趣，了解了一下怎么分库分表，说一下垂直分库分表、水平分库分表，在讲一讲可能会遇到的数据问题。差不多这个问题你拿个 80 没问题。好了，偶然刷到，给你解解惑，希望你下次面试有好结果，也希望我有好结果。😁共勉。（来自 4年老鸟的）

hashmap的实现原理可以分成两个版本，比如 1.7 怎么怎么样，1.8 怎么怎么样，这么说：hashmap 在 jdk1.8 以前底层数据结构采用数组+链表的方式，之后需要介绍插入的逻辑：在插入元素时，首先会计算key 的 hashcode 并且通过 hashcode&n-1 来计算出 key 在数组中的位置，如果当前数组位置为空，则直接进行赋值，如果当前位置有数据存储了，那就看当前的 key 与我要传入的 key 是否相同，如果相同则进行值覆盖，如果不相同，则表示当前出现了哈希冲突，那么就看当前节点是否有链表，如果有链表则遍历链表查看是否有相同的 key，如果有则进行值覆盖，如果没有就采用头插法的方式将数据写入到链表中。而在 jdk1.8 之后，hashmap 低层数据结构变成了数组+链表+红黑树的方式，在链表个数超过 8 个时就会发生树化。然后介绍一下 1.8 与 1.7 的区别，1.8采用尾插法解决多线程并发 put 时可能导致的环状结构，1.8 的扩容机制是先插入后进行判断数组是否需要进行扩容。这个问题说完了。面试官看你这么吊可能会继续深入问你：为什么 hashmap 的容量必须为 2 的 n 次方？为什么 hashmap 是非线程安全的？为什么 hashmap链表转红黑树的个数为 8 个不为其他个数？怎么解决 hashmap 的线程安全问题？

concurrentHashMap 跟 hashmap 也是一个套路，1.7 以前版本是什么样，1.8 版本是什么样。为什么能做到线程安全的？插入、读取元素时的过程（1.7、1.8 的优化）。 在 1.7 之前，ConcurrentHashMap 使用的是 segment数组+分段锁的方法，在插入元素时首先会计算这个 key 的 hashcode，然后找到 指定位置的segment数组，如果指定的数组为空，则进行初始化并插入元素，如果不为空，则先获取锁，然后计算 key 值存放的位置，再进行插入元素，获取不到锁的会进行自旋等待获取锁。 1.7 之后，concurrentHashMap 取消了 segment 数组，使用跟 hashMap 一致的结构，在插入元素时会采用 CAS尝试写入数据，失败之后再用synchronized 锁的方式来保证一定能写入，来实现线程安全。 那么如何做到其他线程可以知道当前线程的数据修改呢？通过利用 volatile 关键字修饰，保证修改可见性，并且写操作时会进行 cas+重试以及 synchronized写入数据，就能保证写操作的并发安全。这两个 点解决了 ConcurrentHashmap 的读写并发安全性。

synchronized 关键字就略微复杂了，也需要你回答不同版本下的实现原理（1.6与1.6 之后）1.6 之前采用重量级锁的方式，实际是利用操作系统的 mutex lock 指令，在对应代码块出入口位置添加monitor enter 和 monitor exit 来进行加锁解锁，而修饰方法时添加 ACC_synchronized 标志表明当前方法为同步方法。然后就说这个重量级锁可能引起的性能上面的问题，频繁的切换用户态和内核态会引起性能下降。所以 1.6 之后做了锁升级的优化。然后再介绍一下说一下锁的四种状态-无锁、偏向锁、轻量级锁、重量级锁，锁升级的流程。这个问题基本你就拿下了。

oc了么