Java中高级面试题总览(一)（4）

先根据数据值/机器数后的商划分到不同的机器上，最好可以让数据划分后一次读入内存这样不同的机器负责处
理不同的数值范围。得到结果后，对最小的数据范围的机器进行堆排序(构建小顶堆)。

public class Test{
    public static void main(String[] args){
        long time=new Date().getTime();
        int[] arr=new int[100000000];//1亿长度
        for(int i=0;i<arr.length;i++){
            arr[i]=i+1;
        }
        arr[99999999]=2020;
        int min=arr[0];
        int max=arr[0];
        for(int i=0;i<arr.length;i++){
            if(arr[i]<min)
                min=arr[i];
            if(arr[i]>max)
                max=arr[i];
        }
        byte[] bucket=new byte[(max-min)/8+1];
        for(int i=0;i<arr.length;i++){
            int num=arr[i];
            int j=(num-min)/8;
            int k=(num-min)%8;
            if(((bucket[j]>>k)&1)>0){//重复了
                System.out.println("Number of repeats："+num);
                break;
            }else{
               bucket[j]|=(1<<k);
            }
        }
        long time2=new Date().getTime();
        System.out.println("millisecond:"+(time2-time));
    }
}

public void sortArray(int[] array){
    int temp;
    for(int i=0; i<array.length; i++){
        boolean isSorted = true;
        for(int j=0; j<array.length-i-1; j++){
            if(array[j] > array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }
    }
}

MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为
一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。

问题思考：
40亿个int占（40亿*4）/1024/1024/1024 大概为14.9G左右，很明显内存只有2G，放不下，因此不可能将这
40亿数据放到内存中计算。要快速的解决这个问题最好的方案就是将数据搁内存了，所以现在的问题就在如何
在2G内存空间以内存储着40亿整数。一个int整数在java中是占4个字节的即要32bit位，如果能够用一个bit
位来标识一个int整数那么存储空间将大大减少，算一下40亿个int需要的内存空间为40亿/8/1024/1024大概
为476.83 mb，这样的话我们完全可以将这40亿个int数放到内存中进行处理。
具体思路：
   1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些
数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得
到BitMap表:
tmp[0]:可表示0~31
tmp[1]:可表示32~63
tmp[2]:可表示64~95
.......
那么接下来就看看十进制数如何转换为对应的bit位：
假设这40亿int数据为：6,3,8,32,36,......，那么具体的BitMap表示为：
00000000000000000000000101001001
00000000000000000000000000010000
如何判断int数字在tmp数组的哪个下标，这个其实可以通过直接除以32取整数部分，例如：整数8除以32取整
等于0，那么8就在tmp[0]上。另外，我们如何知道了8在tmp[0]中的32个位中的哪个位，这种情况直接mod上
32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第9个bit位（从右边数
起）。
解法二：
Bloom Filter 原理
下面来分析下它的实现原理。
官方的说法是：它是一个保存了很长的二进制向量，同时结合 Hash 函数实现的。
对写入的数据做 H 次 hash 运算定位到数组中的位置，同时将数据改为 1 。当有数据查询时也是同样的方式定
位到数组中。 一旦其中的有一位为 0 则认为数据肯定不存在于集合，否则数据可能存在于集合中。
布隆过滤有以下几个特点：
只要返回数据不存在，则肯定不存在。
返回数据存在，但只能是大概率存在。
同时不能清除其中的数据。
它不适合那些"零误判"的应用场合.在能容忍低误判的应用场景下,布隆过滤器通过极少的误判换区了存储空间的极大节省.

解法一：将bit-map扩展一下，采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多
次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap
中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。
解法二：根据数字hash,划分小文件。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

每个 URL 占 64B，那么 50 亿个 URL 占用的空间大小约为 320GB。5, 000, 000, 000 _ 64B ≈ 5GB _ 64 
= 320GB 由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题
目，一般采用分治策略 ，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不
超过 4G，这样就可以把这个小文件读到内存中进行处理了。
首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000 ，根据计算结果把遍历到的 URL 存储到 a0, a1, 
a2, ..., a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文
件 b0, b1, b2, ..., b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 
b0, ..., a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对
小文件中相同的 URL 就好了。
接着遍历 ai( i∈[0,999] )，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 
HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

SELECT 姓名,
 max(CASE 课程 WHEN'语文' THEN 分数 ELSE 0 END) 语文,
 max(CASE 课程 WHEN'数学' THEN 分数 ELSE 0 END) 数学,
 max(CASE 课程 WHEN'物理' THEN 分数 ELSE 0 END) 物理
FROM tb
GROUP BY 姓名
姓名        语文        数学        物理
---------- ----------- ----------- -----------
李四        74          84          94
张三        74          83          93

第一个重大区别是:InnoDB的主索引的数据文件本身就是索引文件。从上文知道，MyISAM主索引的索引文件和数据
文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引
结(index=data)，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB
表数据文件本身就是主索引。
第二个重大区别是:MyISAM类型不支持事务处理等高级处理，而InnoDB类型支持事务处理与外键和行级锁。MyISAM
类型的表强调的是性能，其执行速度比InnoDB类型更快，但是不提供事务支持，而InnoDB提供事务支持以及外部
键等高级数据库功能。 所以MyISAM往往就容易被人认为只适合在小项目中使用
第三个区别是:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没
有多大区别

InnoDB使用多版本并发控制来获得高并发性，并且实现了sql标准的4种隔离级别，分别是：
1.未提交读：在未提交读级别，事务中的修改，即使没有提交，对其他事务也都是可见的
2.提交读（Read committed）：大多数数据库系统的默认隔离级别都是提交读（但Mysql不是）一个事务开始
时，只能“看见”已经提交的事务所做的修改",该隔离级别有时也叫"不可重复度"
3.可重复读：可重复读解决了脏读的问题。该级别保证了在同一个事务中多次读取同样记录的结果是一致的。但是
理论上，可重复读隔离级别还是无法解决当某个事务在读取某个范围内的记录时，另外一个事务中又在该范围插入
了新的记录，当之前的事务再次读取该范围的记录时，会产生幻行。可重复读是MySQL的默认事务隔离级别。
4.可串行化：可串行化是最高的隔离级别。它通过强制事务串行执行，避免了前面所说的幻读问题。简单来说，可
串行化会在读取的每一行数据上都加上锁，所以可能导致大量的超时和锁争用问题

InnoDB实现了以下两种类型的行锁。
共享锁（S）：允许一个事务去读一行，阻止同一Session其他事务获得相同数据集的排他锁。当事务同时增加共享锁时候，事务的更新必须等待先执行的事务 commit 后才行，如果同时并发太大可能很容易造成死锁
排他锁（X)：允许获得排他锁的事务更新数据，阻止同一Session其他事务取得相同数据集的共享读锁和排他写
锁。
共享锁（S）：SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE
排他锁（X)：SELECT * FROM table_name WHERE ... FOR UPDATE
另外，为了允许行锁和表锁共存，实现多粒度锁机制，InnoDB还有两种内部使用的意向锁（Intention 
Locks），这两种意向锁都是表锁。
意向共享锁（IS）：事务打算给数据行加行共享锁，事务在给一个数据行加共享锁前必须先取得该表的IS锁。
意向排他锁（IX）：事务打算给数据行加行排他锁，事务在给一个数据行加排他锁前必须先取得该表的IX锁
InnoDB行锁是通过给索引上的索引项加锁来实现的，这一点与Oracle不同，后者是通过在数据块中对相应数据行
加锁来实现的。InnoDB这种行锁实现特点意味着：只有通过索引条件检索数据，InnoDB才使用行级锁，否则，
InnoDB将使用表锁！
在实际应用中，要特别注意InnoDB行锁的这一特性，不然的话，可能导致大量的锁冲突，从而影响并发性能
锁的算法
Record Lock :单个记录上的锁。
Gap Lock：间隙锁，锁定一个范围，但不包含记录本身。
Next-key Lock： 锁定一个范围和本身 Record Lock + Gap Lock。
例如一个索引有10,11,13,20这4个值，那么索引可能被Next-key Locking的区间为：
（- ∞，10）, [10,11) , [11,13), [13,20), [20,+ ∞)
Next-key Lock为了解决幻读问题

事务A等待事务B，同时事务B等待事务A，会产生死锁。
Innodb有死锁检测进程，如果检测到死锁，会马上抛出异常并回滚一个事务（另一个继续执行）
死锁的关键在于：两个(或以上)的Session加锁的顺序不一致。
那么对应的解决死锁问题的关键就是：让不同的session加锁有次序

在讲B+树之前必须先了解二叉查找树、平衡二叉树（AVLTree）和多路平衡查找树（B-Tree），B+树即由这些
树逐步优化而来。
B+Tree相对于B-Tree有几点不同：
1.B+非叶节点不保存数据相关信息， 只保存关键字和子节点的引用
2.B+叶子节点是顺序排列的， 并且相邻节点具有顺序引用的关系（存在一个链指针）
3.B+关键字对应的数据保存在叶子节点中
4.B+节点关键字搜索采用左闭合区间（a<= x < b）
为什么使用B+Tree
红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-Tree作为索引结构，
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的
话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
根据B+Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。（Innodb的数据页是16K，1.2.x支持8K,4K压缩页）。
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
为什么使用B+Tree
B+树是B-树的变种(PLUS版)多路绝对平衡查找树， 他拥有B-树的优势
B+树扫库、 表能力更强(只需要扫描关键字和引用)
B+树的磁盘读写能力更强(B+树的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，保存的关键字要比B-树要多)
B+树的排序能力更强（叶子几点顺序排列）
B+树的查询效率更加稳定（和数据在叶子节点有关）

SELECT
  a.id,
  b.id,
  c.id
FROM
  student a,
  student b,
  student c
WHERE
  a.id - b.id = 1
AND b.id - c.id = 1
AND a.name= b.name
AND b.name= c.name

1、随机（缺省），按权重设置随机概率。
在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
2、轮循，按公约后的权重设置轮循比率。
存在慢的提供者累积请求问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。
3、最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。
使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
4、一致性Hash，相同参数的请求总是发到同一提供者。
当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。

1、失败自动切换，当出现失败，重试其它服务器。(缺省)
通常用于读操作，但重试会带来更长延迟。
可通过retries="2"来设置重试次数(不含第一次,默认就是2)
2、快速失败，只发起一次调用，失败立即报错。
通常用于非幂等性的写操作，比如新增记录。
3、失败安全，出现异常时，直接忽略。
通常用于写入审计日志等操作。
4、失败自动恢复，后台记录失败请求，定时重发。
通常用于消息通知操作。
5、并行调用多个服务器，只要一个成功即返回。
通常用于实时性要求较高的读操作，但需要浪费更多服务资源。
可通过forks="2"来设置最大并行数。
6、广播调用所有提供者，逐个调用，任意一台报错则报错。(2.1.0开始支持)
通常用于通知所有提供者更新缓存或日志等本地资源信息。
重试次数配置如：(failover集群模式生效)

zookeeper的优势：
1.当提供程序意外停止时，注册表服务器可以自动删除其信息。
2.注册表服务器重新启动时，可以自动恢复所有注册数据和订阅请求。
3.会话过期后，可以自动恢复所有注册数据和订阅请求。
redis存在的问题?
redis是通过发布订阅模式完成消息的通知 但是存在几个问题:
1.服务的非自然下线需要监护中心来维护
2.redis做注册中心服务器时间必需同步，否则出现时间不对被强制过期(删除key)!
3.zookeeper支持监听，redis不支持，因此需要客户端启动多个线程进行订阅监听，对服务器有一定压力!