找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】hashCode()的实现对应用程序的性能影响

2014-10-12 11:38| 发布者: zhouy | 查看: 957 | 收藏

摘要: hashCode()方法的主要目的就是使得一个对象能成为hashMap的key或者存储到hashset中。这种情况下对象还得实现equals(Object)方法,它的实现和hashCode()必须是一致的:1. 如果a.equals(b)那么a.hashCode == b.hashCod ...

hashCode()方法的主要目的就是使得一个对象能成为hashMap的key或者存储到hashset中。这种情况下对象还得实现equals(Object)方法,它的实现和hashCode()必须是一致的:

1. 如果a.equals(b)那么a.hashCode == b.hashCode()
2.如果hashCode()在同一个对象上被调用两次,它应该返回的是同一个值,这表明这个对象没有被修改过。

hashCode的性能
从性能的角度来看的话,hashCode()方法的最主要目标就是尽量让不同的对象拥有不同的hashCode。JDK中所有的基于hash的集合都是存储在数组中的。hashcode会用来计算数组中的初始的查找位置。然后调用equals方法将给定的值和数组中存储对象的值进行比较。如果所有的值都有不同的hashCode,这会减少hash的碰撞概率。换句话说,如果所有的值都共享一个hashCode的话,hashmap(或者hashset)会蜕化成一个列表,操作的时间复杂度会变成O(n2)。

更多细节可以看下hash map碰撞的解决方案。JDK用了一个叫开放寻址的方法,不过还有一种方法叫拉链法。所有hashcode一样的值存储在一个链表里。

我们来看下不同质量的hashcode的区别是什么。我们拿一个正常的String和一个String的包装类进行比较,它重写了hashCode方法,所有的对象返回的是同一个hashCode。

private static class SlowString  
    public final String m_str;  
    public SlowString( final String str ) {  
        this.m_str = str;  
    }  

    @Override  
    public int hashCode() {  
      return 37;  
    }  
   
    @Override  
    public boolean equals(Object o) {  
      if (this == o) return true;  
        if (o == null || getClass() != o.getClass()) return false;  
        final SlowString that = ( SlowString ) o;  
     return !(m_str != null ? !m_str.equals(that.m_str) : that.m_str != null);  
}  
}  

private static class SlowString
{
    public final String m_str;

    public SlowString( final String str ) {
        this.m_str = str;
    }

    @Override
    public int hashCode() {
        return 37;
    }

    @Override
    public boolean equals(Object o) {

        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        final SlowString that = ( SlowString ) o;

        return !(m_str != null ? !m_str.equals(that.m_str) : that.m_str != null);

    }
}


下面是一个测试方法。后面我们还会再用到它,所以这里还是简单介绍一下 。它接收一个对象列表,然后对列表中的每个元素依次调用Map.put(),
Map.containsKey()方法。

private static void testMapSpeed( final List lst, final String name )  
{  
    
  final Mapmap = new HashMap( lst.size() );  
    int cnt = 0;  
    final long start = System.currentTimeMillis();
  
    for ( final Object obj : lst )  
    {  
         map.put( obj, obj );  
          if ( map.containsKey( obj ) )  
            ++cnt;  
    }  
    
     final long time = System.currentTimeMillis() - start;  
    System.out.println( "Time for "  + name + " is " + time / 1000.0 + " sec, cnt = " + cnt );  
}  

private static void testMapSpeed( final List lst, final String name )
{
     final Mapmap = new HashMap( lst.size() );
    int cnt = 0;
    final long start = System.currentTimeMillis();

    for ( final Object obj : lst )
    {
        map.put( obj, obj );
        if ( map.containsKey( obj ) )
            ++cnt;
    }
    final long time = System.currentTimeMillis() - start;
    System.out.println( "Time for "  + name + " is " + time / 1000.0 + " sec, cnt = " + cnt );
}

String和SlowString对象都是通过一个"ABCD"+i的格式生成的。处理100000个String对象的话,需要的时间是0.041秒。而处理SlowString对象的话,则需要82.5秒。

结果表明,String类的hashCode()方法的质量明显胜出。我们再做另外一个测试。我们创建一个字符串列表,前半部分的格式是"ABCdef*&"+i,后半部分的是”ABCdef*&"+i+"ghi"(确保字符串的中间部分变化而结尾不变,不会影响hashCode的质量)。我们会创建1M,5M,10M,20M个字符串,来看下有多少个字符串是共享hashcode的,同一个hashcode又被多少个字符串共享。下面是测试的结果:

Number of duplicate hashCodes for 1000000 strings = 0  
  Number of duplicate hashCodes for 5000000 strings = 196  
Number of hashCode duplicates = 2 count = 196    
Number of duplicate hashCodes for 10000000 strings = 1914  
Number of hashCode duplicates = 2 count = 1914   
Number of duplicate hashCodes for 20000000 strings = 17103  
Number of hashCode duplicates = 2 count = 17103    
Number of duplicate hashCodes for 1000000 strings = 0
Number of duplicate hashCodes for 5000000 strings = 196
Number of hashCode duplicates = 2 count = 196
Number of duplicate hashCodes for 10000000 strings = 1914
Number of hashCode duplicates = 2 count = 1914
Number of duplicate hashCodes for 20000000 strings = 17103
Number of hashCode duplicates = 2 count = 17103


可以看到,很少有字符串是共享同一个hashCode的,而一个hashcode被两个以上的字符串共享的概率则非常之小。当然了,你的测试数据可能不太一样——用这个测试程序测试你给定的key的话。自动生成long字段的hashCode方法。值得一提的是,大多数IDE是如何自动生成long类型的hashcode方法的。下面是一个生成的hashCode方法,这个类有两个long字段。

public int hashCode() {  
   
    int result = (int) (val1 ^ (val1 >>> 32));  
    result = 31 * result + (int) (val2 ^ (val2 >>> 32));  
    return result;  
}  
  
public int hashCode() {

    int result = (int) (val1 ^ (val1 >>> 32));
    result = 31 * result + (int) (val2 ^ (val2 >>> 32));
    return result;

}


下面给只有两个int类型的类生成的方法:

public int hashCode() {  
    
   int result = val1;  
   result = 31 * result + val2;  
   return result;  
}  
public int hashCode() {
   
   int result = val1;
    result = 31 * result + val2;
    return result;
}

可以看到,long类型的处理是不一样的。java.util.Arrays.hashCode(long a[])用的也是同样的方法。事实上,如果你将long类型的高32位和低32位拆开当成int处理的话,生成的hashCode的分布会好很多。下面是两个long字段的类的改进后的hasCode方法(注意,这个方法运行起来比原来的方法要慢,不过新的hashCode的质量会高很多,这样的话hash集合的执行效率会得到提高,虽然hashCode本身变慢了)。

public int hashCode() {  
  
   int result = (int) val1;  
    result = 31 * result + (int) (val1 >>> 32);  
    result = 31 * result + (int) val2;  
    return 31 * result + (int) (val2 >>> 32);  
   
public int hashCode() {

    int result = (int) val1;
    result = 31 * result + (int) (val1 >>> 32);
    result = 31 * result + (int) val2;
    return 31 * result + (int) (val2 >>> 32);
}

下面是testMapSpeed 方法分别测试10M个这三种对象的结果。它们都是用同样的值进行初始化的。

Two longs with original hashCode 
Two longs with modified hashCode 
Two ints 
2.596 sec 
1.435 sec 
0.737 sec


可以看出,更新后的hashCode方法的效果是不太一样的。虽然不是很明显,但是对性能要求很高的地方可以考虑一下它。
高质量的String.hashCode()能做些什么

假设我们有一个map,它是由String标识符指向某个特定的值。map的key(String标识符)只会存储在这个map中(同一时间,最多有一部分是存储在别的地方)。假设我们已经收集了map的所有entry,比如说在某个两阶段算法中的第一个阶段。第二个阶段我们需要通过key来查找map。我们只会用已经map里存在的key进行查找。

我们如何能提升map的性能?前面你已经看到了,String.hashCode()返回的几乎都是不同的值,我们可以扫描所有的key,计算出它们的hashCode,找出不是唯一的那些hashcode:

Map cnt = new HashMap( max ); 

for ( final String s : dict.keySet() )  
{  
    final int hash = s.hashCode();  
    final Integer count = cnt.get( hash ); 

    if ( count != null )  
           cnt.put( hash, count + 1 );  
   else  
     cnt.put( hash, 1 );  
}

  
//keep only not unique hash codes   
final Map mult = new HashMap( 100 ); 

for ( final Map.Entry entry : cnt.entrySet() )  
{  
   if ( entry.getValue() > 1 )  
     mult.put( entry.getKey(), entry.getValue() );  
}  
  
Map cnt = new HashMap( max );

for ( final String s : dict.keySet() )
{
    final int hash = s.hashCode();
    final Integer count = cnt.get( hash );
    if ( count != null )
        cnt.put( hash, count + 1 );
    else
        cnt.put( hash, 1 );
}

//keep only not unique hash codes

final Map mult = new HashMap( 100 );
for ( final Map.Entry entry : cnt.entrySet() )
{
    if ( entry.getValue() > 1 )
        mult.put( entry.getKey(), entry.getValue() );
}

现在我们可以创建两个新的map。为了简单点,假设map里存的值就是Object。在这里,我们创建了Map 和Map(生产环境推荐使用TIntObjectHashMap)两个map。第一个map存的是那些唯一的hashcode以及对应的值,而第二个,存的是那些hashCode不唯一的字符串以及它们相应的值。

final Map unique = new HashMap( 1000 );  
final Map not_unique = new HashMap( 1000 );  

//dict - original map   
for ( final Map.Entry entry : dict.entrySet() )  
{  
      final int hashCode = entry.getKey().hashCode();  
     if ( mult.containsKey( hashCode ) )
  
            not_unique.put( entry.getKey(), entry.getValue() ); 

     else 

       unique.put( hashCode, entry.getValue() ); 

}  

//keep only not unique hash codes   
final Map mult = new HashMap( 100 );  
for ( final Map.Entry entry : cnt.entrySet() )  
{  
     if ( entry.getValue() > 1 )  
        mult.put( entry.getKey(), entry.getValue() );  
}  

final Map unique = new HashMap( 1000 );
final Map not_unique = new HashMap( 1000 );

//dict - original map
for ( final Map.Entry entry : dict.entrySet() )
{
    final int hashCode = entry.getKey().hashCode();
    if ( mult.containsKey( hashCode ) )
        not_unique.put( entry.getKey(), entry.getValue() );
    else
        unique.put( hashCode, entry.getValue() );
}

//keep only not unique hash codes
final Map mult = new HashMap( 100 );
for ( final Map.Entry entry : cnt.entrySet() )
{
    if ( entry.getValue() > 1 )
        mult.put( entry.getKey(), entry.getValue() );
}

现在,为了查找某个值,我们得先查找第一个hashcode唯一的map,如果没找到,再查找第二个不唯一的map:

public Object get( final String key )  
{  
    final int hashCode = key.hashCode();  
    Object value = m_unique.get( hashCode );  

   if ( value == null )
  
     value = m_not_unique.get( key );
  
    return value;  
  
public Object get( final String key )
{
    final int hashCode = key.hashCode();
    Object value = m_unique.get( hashCode );

    if ( value == null )
          
           value = m_not_unique.get( key );
    return value;
}


在一些不太常见的情况下,你的不唯一的map里的对象可能会很多。遇见这种情况的话,先尝试用java.util.zip.CRC32或者是java.util.zip.Adler32来替换掉hashCode的实现方法(Adler32比CRC32要快,不过它的分布较差些)。如果实在不行,尝试用两个不同的函数来计算hashcode:低32位和高32位分别用不同的函数生成。hash函数就用Object.hashCode, java.util.zip.CRC32或者java.util.zip.Adler32。
(译注:这么做的好处就是压缩了map的存储空间,比如你有一个map,它的KEY存100万个字符串的话,压缩了之后就只剩下long类型以及很少的字符串了)

set的压缩效果更明显

前面那个例子中,我们讨论了如何去除map中的key值。事实上,优化set的话效果会更加明显。set大概会有这么两个使用场景:一个是将原始的set拆分成多个子set,然后依次查询标识符是否属于某个子set;还有一个是写一个拼写检查器(spellchecker )——有些要查询的值是预想不到的值(比如拼写错误了),而就算出了些错误的话影响也不是很大(如果碰巧另一个单词也有同样的hashCode,你会认为这个单词是拼写正确的)。这两种场景set都非常适用。


如果我们延用前面的方法的话,我们会得到一个唯一的hashcode组成的Set,不唯一的hashCode得到的是一个Set。这里至少能优化掉不少字符串的空间。如果我们可以把hashCode的取值限制在一定的区间内(比如说2^20),那么我们可以用一个BitSet来代替Set,这个在BitSet一文中已经提到了。一般来说如果我们提前知道原始set的大小的话,hashcode的范围是有足够的优化空间的。


下一步就是确定有多少个标识符是共享相同的hashcode的。如果碰撞的hashcode比较多的话,改进你的hashCode方法,或者增加hashcode的取值范围。最完美的情况就是你的标记符全都有唯一的hashcode( 这其实不难实现)。优化完的好处就是,你只需要一个BitSet就够了,而不是存储一个大的字符串集合。

总结
改进你的hashCode算法的分布。优化它比优化这个方法的执行速度要重要多了。千万不要写一个返回常量的hashCode方法。
String.hashCode的实现已经相当完美了,因此很多时候你可以用String的hashCode来代替字符串本身了。如果你使用的是字符串的set,试着把它优化成BitSet。这将大大提升你程序的性能。


本文由守望者watchmen收集整理,部分内容源于网络(http://csdn.net)。本文仅代表作者个人观点,不代表守望者的本意。如有违法侵权内容,请提交到守望者管理员处,立即处理。

推荐阅读

【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved