答题小助手_个人页

本期答案 1、现在假设参与人数为：n=8；指定出列数：m=4； 那么第一个出列的数为：4 . . . 2、数组结构示意图： 3、设出列元素的下标为t，初始值为：t=0，可以得到一个规律： t=(t+m-1)%n=(0+4-1)%8=3; 那么数组下标为3的人出列。出列一个元素之后，数组的规模：n-1；然后出列位置后面的元素向前移动。 import java.util.Scanner; public class Tree1 { int[] a=new int[20]; //定义成员编号数组 int n; //定义参与人数的属性 public static void main(String[] args) { Scanner input=new Scanner(System.in); Tree1 l=new Tree1(); System.out.println('请输入参与人数的整数值：'); l.n=input.nextInt(); int m=0; System.out.println('请输入出列的整数值：'); m=input.nextInt(); for(int i=0;i0) { //利用循环将所有人员出列 t=(t+m-1)%l.n; //得到出列人员的下标 System.out.print('\t'+l.a[t]); for(int j=t+1;j

本期答案： 通过这道题目，想跟大家聊聊【如何有效做Code Review】。 这是8行代码提出的21个问题，具体回答请点击此处详细查看。 提示：这个问题的答案有4000+字，建议先收藏，找一个合适阅读的时间仔细看看。

本期答案： 这道题没有一个统一的答案。哈希表常见的实现可以按照解决冲突的方式分为 Chaining 和 Open-addressing 两种。Chaining 实现将 Hash 到同一个桶的元素使用链表串联起来（也可以是其他更高效的方式），相应的，查找的时候需要查看桶中的所有元素。Open-addressing 译为开地址法，插入时一旦发现对应的桶已经被占用，则会根据某种特定方式继续寻找另一个桶，直到找到一个空的桶为止，相应地查找时也要做相同的操作。 下面给出一个 Chaining 的实现： public class MyHashTableImpl { private final Node[] buckets; public MyHashTableImpl(int expectedSize) { this.buckets = new Node[expectedSize * 4]; } public void put(K key, V value) { int h = key.hashCode() % buckets.length; Node node = new Node<>(key, value); node.next = buckets[h]; buckets[h] = node; } public V get(K key) { int h = key.hashCode() % buckets.length; Node node = buckets[h]; while (node != null) { if (node.key.equals(key)) { return node.value; } node = node.next; } return null; } private static class Node { final K key; final V value; Node next = null; Node(K key, V value) { this.key = key; this.value = value; } } } 并发情况下，如果直接使用上述代码， buckets 上会产生数据竞争，可能导致数据结构损害。为了防止这一点，我们可以通过分段加锁来保护（类似于 JDK7 的 ConcurrentHashMap 实现）。但是，对于上面的代码来说，由于少了 rehash 的负担，我们还可以利用 CAS 实现乐观锁。这也是 JDK8+ 的 ConcurrentHashMap 使用的方案。 public class MyLockFreeHashTableImpl { private final AtomicReferenceArray> buckets; public MyLockFreeHashTableImpl(int expectedSize) { this.buckets = new AtomicReferenceArray<>(expectedSize * 4); } public void put(K key, V value) { int h = key.hashCode() % buckets.length(); while (true) { Node node = new Node<>(key, value); node.next = buckets.get(h); if (buckets.compareAndSet(h, node.next, node)) { // 如果失败，则重试 return; } } } public V get(K key) { int h = key.hashCode() % buckets.length(); Node node = buckets.get(h); while (node != null) { if (node.key.equals(key)) { return node.value; } node = node.next; } return null; } static class Node { /* 略 */ } } 上面的代码都是对于 Chaining 来说的，Open-addressing 也可以用类似的方式实现乐观锁，有兴趣的读者可以自己试试 ：） 最后一个问题，如果考虑 rehash，并发的实现就复杂了许多。我们依然有很多选项。最简单的一种实现，参考 JDK7 的分段加锁方案，我们可以为各个 Segment 独立加锁，这样即时某个 Segment 发生了 rehash 操作，也不会影响其他 Segment 的并发访问。多数情况下，这种实现已经能较好的满足要求。 JDK8 的 ConcurrentHashMap 实现更复杂，当需要 rehash 时，线程会逐个将 bin (bucket) 的数据复制到新的位置。此时若有其他线程并发写入时，它们也会参与到复制中来，共同协作完成哈希表的扩容。其中，每个 bin 的复制过程都通过加锁保证互斥。 而对于 Open-addressing 的哈希表，还有一些更为精妙的解决方案，有兴趣的读者可自行阅读相关论文，这里不再讨论。

本期答案： 基本：使用双向链表记录 map entry，读写时把访问的 entry 从链表中间删除插入 head, 如果 map 满了从链表 tail 淘汰数据。/ 进阶：提到 map 和双向链表的并发访问保护机制。/ 骨灰：提到 LRU 的几类优化，提到 Redis 的优化。

本期答案：请参考阿里云分布式数据库服务 DRDS 官方文档中的 SQL 闪回功能。 参考链接： SQL闪回