spark hashPartitioner与rangePartitioner的实现

HashPartitioner分区原理很简单，对于给定的key计算hashcode，并除以分区的个数取余，最后返回的值就是这个key所属的分区ID。
从HashPartitioner分区的实现原理可以看出，其结果可能导致每个分区中数据量的不均匀，极端情况下回导致某些分区拥有RDD的全部数据，这显然不是我们想要的。而RangePartitioner分区则尽量保证每个分区中数据量的均匀，而且分区和分区之间是有序的，即一个分区中的元素坑定都是比另一个分区内的元素小或者大，但是分区内的元素是不能保证顺序的，就是将一定范围内的数映射到某一个分区内。
首先了解蓄水池抽样(Reservoir Sampling)，它能够在O(n)时间内对n个数据进行等概率随机抽取，例如：从1000个数据中等概率随机抽取100个。另外，如果数据集合的量特别大或者还在增长，该算法依然可以等概率抽样。
首先构建一个可放k个元素的蓄水池，将序列的前k个元素放入蓄水池中。
然后从第k+1个元素开始，以k/n的概率来替换掉蓄水池中国的某个元素即可。当遍历完所有元素之后，就可以得到随机挑选出的k个元素，复杂度为O(n).
RangePartitioner分区器的主要作用就是将一定范围内的数映射到某一个分区内。该分区器的实现方式主要是通过两个步骤来实现的，第一步，先从整个RDD中抽取出样本数据，将样本数据排序，计算出每个分区的最大key值，形成一个Array[KEY]类型的数组变量rangeBounds；第二步，判断key在rangeBounds中所处的范围，给出该key值在下一个RDD中的分区ID下标；该分区器要求RDD中的KEY类型必须是可以排序的。