文档章节

谨慎使用String作为HashMap的Key

猴亮屏
 猴亮屏
发布于 2017/05/08 21:55
字数 1400
阅读 23
收藏 0
点赞 0
评论 0

首先简单复习一下哈希表知识(大学课本定义)。 
        根据设定的哈希函数f(key)和处理冲突的方法将一组关键字映像到一个有限的连续地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为哈希表。 
         哈希函数f(key)是一个映像,使得任何关键字由此所得到的哈希函数值都落在表允许范围之内。 
         对不同的关键字可能得到同一哈希地址,即key!=key2,但是f(key1)=f(key2),这种现象称为冲突。一般情况下,冲突只能减少,而不能完全避免。 

还不清楚?请百科普及一下吧。 


通过上面的复习,我们知道,决定一个哈希表的性能主要是哈希表的键值的冲突概率。如果哈希后的冲突很低,性能就高,相反,性能则低。使用一个好的哈希算法,可以降低哈希冲突的概率,提高命中率。 

但是,如果被哈希的Key本身就是重复的,那么哈希算法再好,也无法避免哈希值的冲突。 

我们都知道,在Java中,HashMap一般是使用对象的hashcode作为哈希的Key的。那么使用String作为HashMap的Key,好不好呢?或者,你在不知情的情况一下,已经干过很多次了。 

String的hashCode方法。 

Java代码  收藏代码 
public int hashCode() {  
    int h = hash;  
        int len = count;  
    if (h == 0 && len > 0) {  
        int off = offset;  
        char val[] = value;  
  
            for (int i = 0; i < len; i++) {  
                h = 31*h + val[off++];  
            }  
            hash = h;  
        }  
        return h;  
    }  


核心的代码就一行。就是 

Java代码  收藏代码 
h = 31*h + val[off++];  
他的意思就是一个字符串的hashcode,就是逐个按照字符的utf-16的编码值求和。 

我个人觉得,像这样的计算hashcode的话,各个字符串很容易重复(虽然我数学不好)。比如:"C9"和“Aw” 
的hashcode都是2134。这样的长度为2位的字符串,我用程序统计了一下,重复的概率大概是0.6665928。 

当字符长度为3个字符时,重复的概率成上升趋势,达到0.8911293,4位时为0.9739272。当然,5位长度的概率我不知道,因为我的机器上跑不出来结果。 
测试代码见附1。 

这么高的重复率,如果你使用它作为hashcode的话,势必会造成很大的哈希冲突,从而降低哈希表最初的设计初衷,性能降低。 

但是,那String设计的时候,为啥这样设计hashcode呢?我经过测试,当字符串仅为数字时,多长的字符串,hashcode都不会重复。这是为什么呢? 

从他计算的公式的31的系数看,应该是31为一个跨度,即只要字符串中的字符串的跨度在31个之内,hash值就不会重复,经过测试,确实如此。也就是说,如果你使用纯英文大写或纯英文小写字母拼接起来的字符串,其hashcode一般不会重复的。不知道这个31最初是怎么算出来的,但是,毋庸置疑,我们可以通过重新String的hashcode方法,将31改为128,那么冲突就会大大降低。 

看看可能会作为Key的情况。 
1、MD5,一般是字母加数字,字符跨度为75. 
2、oracle的sys_guid()产生的逐渐,字符跨度为43. 
3、java的UUID,跨度为75. 
4、其他唯一主键情况。 

建议,如果你的对象主键是上述类型,则尽量少的使用HashMap作为进行运算的工具类。 

因此,当你打算使用String作为HashMap的Key时,我建议两点: 
1、如果你不知道你的Key的可能的取值范围是否超过31,并且不知数量是多大时,尽量不要使用。 
2、如果你对性能要求很高,请尽量不要将字符串作为主键。 


附1:计算字符串重复概率的代码 
Java代码  收藏代码 
import java.util.HashMap;  
/** 
* 测试字符串的hashcode重复几率 
* @author donlianli@126.com 
*/  
public class StringHashCode {  
      
    static HashMap<Integer,Object> map = new HashMap<Integer,Object>();   
    /** 
     * 第一个可见字符 
     */  
    private static char startChar = ' ';   
    /** 
     * 最后一个可见字符 
     */  
    private static char endChar = '~';   
    private static int offset = endChar - startChar + 1;   
    /** 
     * 重复次数 
     */  
    private static int dupCount = 0;   
      
    public static void main(String[] args) {   
        for(int len=1;len<5;len++){  
             char[] chars = new char[len];   
             tryBit(chars, len);   
             int total=(int)Math.pow(offset, len);  
             System.out.println(len+":"+total + ":" + dupCount+":"+map.size()+":"+(float)dupCount/total);  
        }  
          
    }   
   
    private static void tryBit(char[] chars, int i) {   
        for (char j = startChar; j <= endChar; j++) {   
            chars[i - 1] = j;   
            if (i > 1)   
                tryBit(chars, i - 1);   
            else   
                test(chars);   
        }   
    }   
   
    private static void test(char[] chars) {   
        Integer key = new String(chars).hashCode();  
        if (map.containsKey(key)) {   
            dupCount++;   
        } else {   
            map.put(key, null);   
        }   
    }   
}  

附2:计算字符串为长度为2的重复hashcode的代码 


Java代码  收藏代码 
import java.util.HashMap;  
/** 
* 测试字符串的hashcode重复几率 
* @author donlianli@126.com 
* 求长度为2的hashcode重复的字符串 
*/  
public class PrintStringHashCode {  
      
    static HashMap<Integer,Object> map = new HashMap<Integer,Object>();   
    /** 
     * 第一个可见字符 
     */  
    private static char startChar = ' ';   
    /** 
     * 最后一个可见字符 
     */  
    private static char endChar = 'z';   
    private static int offset = endChar - startChar + 1;   
    /** 
     * 重复次数 
     */  
    private static int dupCount = 0;   
      
    public static void main(String[] args) {   
        int len =2;  
         char[] chars = new char[len];   
         tryBit(chars, len);   
         int total=(int)Math.pow(offset, len);  
         System.out.println(len+":"+total + ":" + dupCount+":"+map.size()+":"+(float)dupCount/total);  
    }   
   
    private static void tryBit(char[] chars, int i) {   
        for (char j = startChar; j <= endChar; j++) {   
            chars[i - 1] = j;   
            if (i > 1)   
                tryBit(chars, i - 1);   
            else   
                test(chars);   
        }   
    }   
   
    private static void test(char[] chars) {   
        String s = new String(chars);  
        Integer key = s.hashCode();  
        if (map.containsKey(key)) {   
            dupCount++;   
            System.out.println(map.get(key)+" same :"+s+" hashcode:"+key);  
        } else {   
            map.put(key, s);   
        }   
    }   

本文转载自:http://jackyrong.iteye.com/blog/1979686

共有 人打赏支持
猴亮屏

猴亮屏

粉丝 30
博文 513
码字总数 54284
作品 2
北京
Android工程师
[转]为什么Java中的String不可变

笔主前言: 众所周知,String是Java的JDK中最重要的基础类之一,在笔主心中的地位已经等同于int、boolean等基础数据类型,是超越了一般Object引用类型的高端大气上档次的存在。 但是稍有研究...

gagabear
2014/09/23
0
0
对anagrams分组 Group Anagrams

问题: Given an array of strings, group anagrams together. For example, given: , Return: [["ate", "eat","tea"],["nat","tan"],["bat"]] Note: For the return value, each inner list......

叶枫啦啦
2017/09/05
0
0
5.Java基础复习----Map

1.Map java.util.Map<K,V> interface 实现Map接口的类用来存储键-值 对; 可以存储null键 Map类中存储的键 -- 值 对通过键来标识,所以键值不能重复 public int size();集合大小 public boo...

baibuxiha
2016/01/24
14
0
Map集合以及Collections集合工具类

一、Collection集合主要特点与Map集合的区别 Collection: 单列集合;有两个子接口 List集合元素是有序的,可以重复的 Set集合元素是无序的,不可以重复 List:元素可重复,有序 ArrayList:底层...

走了丶
2017/08/07
0
0
Java你可能不知道的事(3)HashMap

概述 HashMap对于做Java的小伙伴来说太熟悉了。估计你们每天都在使用它。它为什么叫做HashMap?它的内部是怎么实现的呢?为什么我们使用的时候很多情况都是用String作为它的key呢?带着这些疑...

passion9527
2016/03/15
176
0
-Java forEach中 Lambda Expr中的 final变量要求

本文是关于 -Java Lambda Expression在forEach方法的应用讨论。对比其他编程语言的foreach 操作(文末附带7种主要编程语言的Loop HashMap by forEach的程序片段),Java 8引入的运用 Lambda E...

wadelau
07/19
0
0
集合——HashMap的工作原理

http://www.importnew.com/16301.html 好的链接 HashMap的工作原理? 1.HashMap的底层结构是数组加链表; a.HashMap包含一个Entry(key,value,next,hash)的内部类,key/value放入HashMap的时候...

亚特兰缇斯
2015/03/03
0
0
Java的HashMap和HashTable

HashMap 1) hashmap的数据结构 Hashmap是一个数组和链表的结合体(在数据结构称“链表散列“),如下图示: 当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(...

Leaomato
2014/09/23
0
0
HashMap的非线程安全性和ConcurrentHasMap

在平时开发中,我们经常采用HashMap来作为本地缓存的一种实现方式,将一些如系统变量等数据量比较少的参数保存在HashMap中,并将其作为单例类的一个属性。在系统运行中,使用到这些缓存数据,...

小样
2011/10/24
0
0
Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。首先我们从一个例子...

leon_rock
2014/04/19
0
3

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Application Express安装

Application Express安装文档 数据库选择和安装 数据库选择 Oracle建议直接12.2.0.1.0及以上的版本,12.1存在20618595bug(具体可参见官方文档) Oracle 12c 中安装oracle application expr...

youfen
15分钟前
0
0
OpenMessaging概览

序 本文主要研究一下OpenMessaging 架构图 namespace,类似cgroup的namespace,用来进行安全隔离,每个namespace有自己的producer、consumer、topic、queue等 producer,消息生产者有两类,一...

go4it
19分钟前
0
0
MySQL索引类型

MySQL目前主要有以下几种索引类型: 1.普通索引 2.唯一索引 3.主键索引 4.组合索引 5.全文索引 https://www.cnblogs.com/luyucheng/p/6289714.html...

灯下草虫鸣_
20分钟前
0
0
spring boot2.x设置quartz对一个job顺序执行

背景 使用quartz时,如果一个job的是1分钟,但是执行却要2分钟,quartz默认的是不会等job执行结束后,再执行下一次job,默认是会再开启一个线程执行该次job,这就可能导致一些重复执行的BUG...

EasyProgramming
25分钟前
0
0
iOS定向阴影的探讨

view.layer.shadowColor = [UIColor blackColor].CGColor; view.layer.shadowOpacity = 0.8f; view.layer.shadowRadius = 4.f; view.layer.shadowOffset = CGSizeMake(0,0); ......

RainOrz
37分钟前
0
0
oracle使用jdbc报错Locale not recognized解决方法

在开启数据库连接之前和之后添加时区参数:

源哥L
41分钟前
0
0
django2.0正则表达

re_path("userdetail-(?P<nid>\d+)/",views.user_detail), 解析时用re_path 否则出现not find page

南桥北木
44分钟前
0
0
Mac 安装jd-gui

安装brew 命令行输入 /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" 回车 安装jd-gui brew cask install jd-gui......

张欢19933
51分钟前
0
0
占坑

00000000000000000000000000000000000000000000000

钟元OSS
51分钟前
0
0
编程学习读书笔记之jQuery函数应用学习心得(图)

编程学习读书笔记之jQuery函数应用学习心得(图) jQuery.extend() 函数 用于将一个或多个对象的内容合并到目标对象。 1.当提供两个或多个对象给.extend(),对象的所有属性都添加到目标对象(...

原创小博客
53分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部