- 浏览: 7847440 次
- 性别:
- 来自: 广州
文章分类
- 全部博客 (2425)
- 软件工程 (75)
- JAVA相关 (662)
- ajax/web相关 (351)
- 数据库相关/oracle (218)
- PHP (147)
- UNIX/LINUX/FREEBSD/solaris (118)
- 音乐探讨 (1)
- 闲话 (11)
- 网络安全等 (21)
- .NET (153)
- ROR和GOG (10)
- [网站分类]4.其他技术区 (181)
- 算法等 (7)
- [随笔分类]SOA (8)
- 收藏区 (71)
- 金融证券 (4)
- [网站分类]5.企业信息化 (3)
- c&c++学习 (1)
- 读书区 (11)
- 其它 (10)
- 收藏夹 (1)
- 设计模式 (1)
- FLEX (14)
- Android (98)
- 软件工程心理学系列 (4)
- HTML5 (6)
- C/C++ (0)
- 数据结构 (0)
- 书评 (3)
- python (17)
- NOSQL (10)
- MYSQL (85)
- java之各类测试 (18)
- nodejs (1)
- JAVA (1)
- neo4j (3)
- VUE (4)
- docker相关 (1)
最新评论
-
xiaobadi:
jacky~~~~~~~~~
推荐两个不错的mybatis GUI生成工具 -
masuweng:
(转)JAVA获得机器码的实现 -
albert0707:
有些扩展名为null
java 7中可以判断文件的contenttype了 -
albert0707:
非常感谢!!!!!!!!!
java 7中可以判断文件的contenttype了 -
zhangle:
https://zhuban.me竹板共享 - 高效便捷的文档 ...
一个不错的网络白板工具
http://donlianli.iteye.com/blog/1979674
首先简单复习一下哈希表知识(大学课本定义)。
根据设定的哈希函数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);
}
}
}
首先简单复习一下哈希表知识(大学课本定义)。
根据设定的哈希函数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);
}
}
}
发表评论
-
复习:强迫线程顺序执行方式
2019-01-03 23:42 1473方法1: 三个线程,t1,t2,t3,如果一定要按顺序执行, ... -
(转)不错的前后端处理异常的方法
2019-01-02 23:16 1962前言 在 Web 开发中, 我们经常会需要处理各种异常, 这是 ... -
info q的极客时间大咖说等资料下载
2018-08-15 08:40 3408info q的极客时间大咖说等资料下载,还有不少思维导图 链 ... -
CXF 客户端超时时间设置(非Spring配置方式)
2018-07-03 22:38 2175import org.apache.cxf.endpoint. ... -
(转)synchronized关键字画像:正确打开方式
2018-06-14 09:25 443https://mp.weixin.qq.com/s/b3Sx ... -
CountDownLatch的例子
2018-06-13 14:10 627public class StatsDemo { ... -
两道面试题,带你解析Java类加载机制
2018-06-12 16:29 549https://mp.weixin.qq.com/s/YTa0 ... -
Spring中获取request的几种方法,及其线程安全性分析
2018-06-11 09:03 621https://mp.weixin.qq.com/s/KeFJ ... -
内部类小结
2018-06-06 10:25 393https://mp.weixin.qq.com/s/hErv ... -
JVM虚拟机小结1
2018-06-04 20:43 4611 jps -l //列出详细的类名和进程ID 2)jps ... -
windows下自带命令行工具查看CPU资源情况等
2018-06-04 12:53 3037微软提供了不少命令行 ... -
(收藏)深入分析Java的序列化与反序列化
2018-05-30 15:21 552https://mp.weixin.qq.com/s/T2Bn ... -
apache common包中的序列化工具
2018-05-30 09:10 1772什么是序列化 我们的 ... -
JAVA8 JVM的变化: 元空间(Metaspace)
2018-05-24 22:30 903本文将会分享至今为至我收集的关于永久代(Permanent G ... -
(转)服务器性能指标(一)——负载(Load)分析及问题排查
2018-05-21 21:03 1259原创: Hollis Hollis 负载 ... -
(转)对象复用
2018-05-20 15:27 802public class Student { priv ... -
mapreduce中入门中要注意的几点
2018-05-06 08:59 615在 mapreduce中,比如有如下的词: I love b ... -
HDFS的基本操作
2018-05-02 21:47 874-mkdir 在HDFS创建目录 ... -
一个不错的开源工具类,专门用来解析日志头部的,好用
2018-05-02 20:00 704一个不错的开源工具类,专门用来解析日志头部的,好用。 http ... -
介绍个不错的RESTFUL MOCK的工具wiremock
2018-04-27 21:02 1850介绍个不错的RESTFUL MOCK的工具wiremock,地 ...
相关推荐
12.如果使用Object作为HashMap的Key,应该怎么办呢? 13.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标? 14.HashMap 的长度为什么是2的幂次方? 15.HashMap 与 HashTable 有什么区别? 16....
查找key使用containskey方法, 3 hashtable查询的的时间复杂度为O(1)可以使用put和get方法存储查询数据。List类使用add和get。 4 new HashMap<String>>(); 定义的这个数据结构中,如果每次都hashMap.put(string, ...
Java HashMap Java 集合框架 HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。 ...HashMap 的 key 与 value 类型可以相同也可以不同,可以是字符串(String)类型的 key 和 value
public synchronized static Object getCache(String key) { return cacheMap.get(key); } /** * 判断是否存在一个缓存 * * @param key * @return */ public synchronized static boolean ...
Map<String, String> map = new HashMap<String, String>(); while(enu.hasMoreElements()) { String key = enu.nextElement(); if(!key.equals("id")) { map.put(key, request.getParameter(key)); } Db....
HashMap LinkedList ArrayList HashSet SortedSet Socket Thread OutputStream InputStream 指令支持 通用指令 keys pattern 支持正则匹配 expire key mill del key [key...] string set key value get key list ...
public static boolean hasVal(PageData pd,String key){ return pd!=null&&pd;.containsKey(key)&&!pd.getString(key).isEmpty(); } public String getString(Object key) { return (String)get(key); } ...
1、注释尽可能全面,2、多次使用的相同变量最好归纳成常量,3、尽量...8、尽早的将不再使用的变量引用赋给null,9、在finally块中对资源进行释放,10、在HashMap中使用一个Object作为key时要注意如何区分Object是否相同
key=(String)it.next(); logger.info("email-" + key + ":" + emails.get(key)); } Iterator it = emails.keySet().iterator(); while (it.hasNext()){ String key; key=(String)it.next(); ...
SimpleCacheA Cache framework for java and android application, objects are store in key-value pair in memory,value can be...使用HashMap进行存储,键为String,值可以为任意对象类型,如String,List,Map等。当
final HashMap<String, String> map = new HashMap<String, String>(); for (int i = 0; i ; i++) { new Thread(new Runnable() { @Override public void run() { map.put(UUID.randomUUID().toString(), ""); ...
class Demo { public static String calcAuthorization(String source, String secretId, String secretKey, String datetime) throws NoSuchAlgorithmException, UnsupportedEncodingException, ...
Map<String,Object> map = new HashMap(); // String objectStr="{\\\\"username\":\"老李\",\"nickname\":\"李刚\",\"remark\":\"肚痛\"}"; // String basestr = Base64.getBase64(objectStr); String javabean...
// 将数据的英文字段作为key,对映值转换为相应类型 datamap.put(e.getColumn(), obj); } } list.add(datamap); } } return list; } /** 将参数转换为数据库数据 */ public Object convertDataType...
Map<String, String> header = new HashMap<String, String>(); header.put("Content-Type", "application/x-www-form-urlencoded; charset=utf-8"); header.put("X-Param", paramBase64); header.put("X-...
一. 理论准备 ...HashMap的值是没有顺序的,它是按照key的HashCode来实现的,对于这个无序的HashMap我们要怎么来实现排序呢?参照TreeMap的value排序。 Map.Entry返回Collections视图。 二. key排序 Tr
轮选择器WheelPicker 是一个库,提供一个对话框片段来选择两个......// second picker data is HashMap<String>// HashMap key value is mapping to first picker string// List is mapping success second picker st
new HashMap[],ImmutableBytesWritable>(); @SuppressWarnings("deprecation") @Override protected void map(ImmutableBytesWritable key, Result value, Context context) throws IOException, ...
25、当一个对象被当作参数传递到一个方法后,此方法可改变这个对象的属性,并可返回变化后的结果,那么这里到底是值传递还是引用传递 ...值:只有HashMap可以让你将空值作为一个表的条目的key或value
Map对象使用花括号包括,Map中的key-value对之间以英文冒号":"分隔,多组key-value对之间以英文逗号","分隔.下面是一个例子: {"语文":78, "数学":80} Map对象的key和value都是表达式,但是key必须是字符串 3.2 输出...