`
brandNewUser
  • 浏览: 456226 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

hadoop Partiton中的字符串Hash函数改进

阅读更多

 

最近的MapReduce端的Partition根据map生成的Key来进行哈希,导致哈希出来的Reduce端处理任务数量非常不均匀,有些Reduce端处理的数据量非常小(几分钟就执行完成,而最后的part-结果显示其输出文件为0,没有处理任何任务),而有些Reduce端需要执行大量的任务(大概1个多小时)

 

根据下面的这篇大牛所写的文章,字符串hash算法也有很多种:

https://www.byvoid.com/en/blog/string-hash-compare

 

这些算法使用位运算使得每个字符都对最后的结果产生影响,作者对其展开了一系列评测,最终BKDR函数无论是在实际效果还是编码实现中,效果都是非常突出的,因此本重构也采用这种算法。

 

文中给出这种算法的C语言实现:

 

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;

    while (*str)
    {
        hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
}

 

 

下面需要做的就是将其转换为Java实现,Java中使用long类型作为C语言中无符号整数的替代(避免int*计算的溢出),后面强制转换为int,去掉高位,并纠正“+/-”号

 

public static int bkdrHash(String hashString) {
        long seed = 131L;
        long hash = 0L;
        for (int i = 0; i < hashString.length(); i++) {
            char element = hashString.charAt(i);
            hash = hash * seed + element;
        }
        int hashInt = (int) hash;
        return hashInt & 0x7FFFFFFF;
    }

 

 

算法修改完成后,我们需要根据实际的结果来判断是否已经hash均匀。

 

为了确保实际情况中的数据能够有效地哈希均匀,我们直接修改Reduce端,让其直接在reduce函数中仅将key值输出,并将所有输出合并到一个文件以便进行分析。(未设置OutputFormat,直接输出Key文本作为一行)

collector.collect(new Text(iReportKey.getPartitionKey()), new Text(""))

 

 

进行均匀的简单分析程序如下:

 

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(is));
        String line;
        int totalCount = 0;
        while ((line = bufferedReader.readLine()) != null) {
            int index = Util.hashCode(line, numberPartition);
            result[index]++;
            totalCount++;
        }
        bufferedReader.close();

        System.out.println("---------------------");
        System.out.println("Total Count: " + totalCount);
        for (int i = 0; i < numberPartition; i++) {
            System.out.println(
                    String.format("partition=%s, count=%s, percentage=%s%%", i, result[i],
                            (double) result[i] * 100d / (double) totalCount));
        }
        System.out.println("---------------------");

 

 

默认设置10个Reduce,分别对生成的Key文件的结果进行处理:

当Map生成的Key数据总量为4390398:

 

 

Total Count: 4390398
partition=0, count=632297, percentage=14.401815051847235%
partition=1, count=410196, percentage=9.343025393142034%
partition=2, count=406882, percentage=9.267542487036483%
partition=3, count=531126, percentage=12.097445379667173%
partition=4, count=569099, percentage=12.962355576874808%
partition=5, count=324720, percentage=7.396140395472119%
partition=6, count=394503, percentage=8.985586272588499%
partition=7, count=343889, percentage=7.832752292616751%
partition=8, count=384954, percentage=8.76808890674604%
partition=9, count=392732, percentage=8.945248244008857%

 

 

 

数据量提高一个等级,当Map生成的Key数据总量为40976446时:

 

 

Total Count: 40976446
partition=0, count=4905825, percentage=11.972304772356294%
partition=1, count=5172735, percentage=12.623678978894363%
partition=2, count=3850931, percentage=9.397913620912853%
partition=3, count=3595419, percentage=8.774355394316043%
partition=4, count=3432017, percentage=8.375584842082205%
partition=5, count=3625976, percentage=8.848927503375965%
partition=6, count=3829224, percentage=9.344939285364084%
partition=7, count=3844329, percentage=9.381801925916172%
partition=8, count=4410943, percentage=10.76458168187646%
partition=9, count=4309047, percentage=10.515911994905561%

 

 

可以看出数据量比较符合预期,最终的实际Reduce(设置为5)效果也比较好,Reduce的执行时间变得非常均匀了:



 

但是经过分析后,直接将long值截取一下并不是一个好的方案,有些暴力:

int hashInt = (int) hash;

 

考虑将算法中的每一步局部变量都设置成int,这样就不会有截取的麻烦,将&操作放到循环内:

public static int bkdrHash(String hashString) {
        int seed = 131;
        int hash = 0;
        for (int i = 0; i < hashString.length(); i++) {
            char element = hashString.charAt(i);
            hash = (hash * seed + element) & 0x7FFFFFFF;
        }
        return hash;
    }

 

但是我们知道,如果int值执行乘法操作时,是有可能溢出的,表现为结果直接返回一个负数。由于我们每次循环都需要*seed,必须保证hash出来的值*seed要小于Integer.MAX_VALUE。

 

Integer.MAX_VALUE=2147483647
(Integer.MAX_VALUE  & 0x1FFFFFFF) * 131=1610612605

 

1610612605会加一个char值,不可能超出最大值,于是选择0x1FFFFFFF替代0x7FFFFFFF。

于是,我们最终的hash方法更改为下面的版本:

public static int bkdrHash(String hashString) {
        int seed = 131;
        int hash = 0;
        for (int i = 0; i < hashString.length(); i++) {
            char element = hashString.charAt(i);
            hash = (hash * seed + element) & 0x1FFFFFFF;
        }
        return hash;
    }

 

经过hash均匀测试,也同样满足要求。

  • 大小: 179.5 KB
分享到:
评论

相关推荐

    写自定义函数stringLower()实现将一个字符串中所有大写字母变为小写字母。在主函数中输入一含有大写字母的字符串,调用该函数并输出改变后的字符串。

    在C++编程语言中,创建自定义函数来处理字符串是很常见的任务。本例中的目标是编写一个名为`stringLower()`的函数,它接受一个包含大写字母的字符串,并将其所有大写字母转换为小写字母。这个功能在处理用户输入、...

    高级软件人才培训专家-Hadoop课程资料-Hive函数

    本篇将详细介绍Hive中的一些关键函数,特别是数学函数和字符串函数,这些函数对于数据预处理和分析至关重要。 #### 二、Hive函数分类 Hive中的函数主要可以分为三类: 1. **聚合函数**:用于执行汇总操作,如求和...

    MapReduce模型在Hadoop实现中的性能分析及改进优化

    MapReduce模型在Hadoop实现中的性能分析及改进优化

    hadoop中文乱码问题

    可以查看与字符编码相关的类,如`Text`、`Charsets`等,了解Hadoop如何处理字符编码。 解决Hadoop中文乱码问题的关键在于识别和匹配数据的正确编码,并在Hadoop组件和工具中设置相应的编码选项。在实际操作中,可能...

    基于Hadoop的文本相似度计算

    在“Similarity”这个项目中,开发者提供了一套代码示例,演示了如何在Hadoop环境下运用TF-IDF和向量空间模型计算文本相似度。虽然这只是一个简单的示例,但对于理解Hadoop处理大规模文本数据的流程以及相关算法的...

    如何高效地进行远程大规模字符串比较问题

    在计算机科学中,字符串比较通常通过逐字符匹配来实现,如简单的“顺序比较”或使用“哈希函数”进行快速预判。然而,当比较的字符串数量巨大时,这些基础方法会变得低效。因此,我们需要更高级的算法和技术来应对大...

    在文件中查询特定字符串

    在IT领域,尤其是在软件开发和数据处理中,查询文件中的特定字符串是一项常见的任务。这个任务可能涉及到文本编辑、日志分析、代码搜索等场景。在本文中,我们将深入探讨如何在文件中有效地查询特定字符串,以及相关...

    string-matching-hadoop:Hadoop 中的超长字符串匹配

    Hadoop 中的超长字符串匹配 Hadoop 中的超长字符串匹配。 给定一个没有 '\n' 或任何仅包含 4 个字符的分隔符的超长字符串,包括多个 1 GB 文件中的 a、b、c 和 d。 目标是使用 Hadoop 在多个 1 GB 文件中找到给定...

    Hadoop中Partition深度解析

    旧版API中Partitioner的类图如图所示。它继承了JobConfigurable,可通过configure方法初始化。它本身只包含一个待实现的方法getPartition。该方法包含三个参数,均由框架自动传入,前面两个参数是key/value,第三个...

    Oracle PL-SQL 对应 hadoop hive 、 phoenix中常用的对应函数

    3. **字符串函数**: - Oracle PL-SQL有`SUBSTR`、`INSTR`、`UPPER`、`LOWER`等处理字符串的函数。Hive中对应的函数为`substring`、`indexOf`、`upper`和`lower`。Phoenix的字符串处理函数如`substr`、`instr`、`...

    Hadoop2.7.1中文文档

    Hadoop2.7.1是Hadoop发展中的一个重要版本,它在前一个版本的基础上进行了一系列的优化和改进,增强了系统的稳定性和性能。这个压缩包文件包含的是Hadoop2.7.1的中文文档,对于学习和理解Hadoop的运作机制、配置以及...

    hive函数大全(中文版)

    16. 空格字符串函数:space 27 17. 重复字符串函数:repeat 27 18. 首字符ascii函数:ascii 28 19. 左补足函数:lpad 28 20. 右补足函数:rpad 28 21. 分割字符串函数: split 28 22. 集合查找函数: find_in_set 29 ...

    Hadoop 2.7.1 中文文档

    8. **编程接口**:对于开发人员,文档会讲解如何编写MapReduce程序,包括Java API的使用以及Hadoop Streaming,允许使用其他语言(如Python或Perl)编写Map和Reduce函数。 9. **性能优化**:文档还会涵盖如何优化...

    hadoophive函数.pdf

    7. 字符串函数: - length():计算字符串长度。 - reverse():反转字符串。 - concat() 和 concat_ws():连接字符串,后者可以指定分隔符。 - substr() 或 substring():截取字符串。 - upper() 和 lower():将...

    hive函数大全 函数参考

    本文档将详细介绍Hive中各种常用的函数,包括关系运算、数学运算、逻辑运算、数值计算、日期函数、条件函数、字符串函数以及集合统计函数。 #### 一、关系运算 这些运算符用于进行基本的关系比较。 1. **等值比较...

    hive函数大全

    由于文本中未提供完整的第七部分“字符串函数”和第八部分“集合统计函数”的内容,以上知识点仅包括文档中给出的部分函数。实际Hive函数库更丰富,包含更多细节和用法。在使用Hive进行数据处理时,需要根据具体场景...

    08.hive内置函数--时间-日期-字符串--函数.mp4

    08.hive内置函数--时间-日期-字符串--函数.mp4

    hadoop2.7中文文档

    hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文...

    hadoop2.6.5中winutils+hadoop

    在Hadoop生态系统中,Windows平台上的开发和运行通常比Linux环境更为复杂,因为Hadoop主要设计为在Linux上运行。然而,随着Hadoop的普及,开发者们也找到了在Windows上搭建和测试Hadoop环境的方法。标题提到的"hadop...

    Hadoop官方中文文档

    在文档描述中提到,文档是一本中文手册,内容包括Hadoop的快速入门指南、集群搭建步骤、Hadoop分布式文件系统(HDFS)的架构设计、使用方法、权限管理以及配额管理等。由此,我们可以知道文档内容非常丰富,覆盖了从...

Global site tag (gtag.js) - Google Analytics