Java自学-集合框架 hashCode原理
Java hashCode原理
步骤 1 : List查找的低效率
假设在List中存放着无重复名称,没有顺序的2000000个Hero
要把名字叫做“hero 1000000”的对象找出来
List的做法是对每一个进行挨个遍历,直到找到名字叫做“hero 1000000”的英雄。
最差的情况下,需要遍历和比较2000000次,才能找到对应的英雄。
测试逻辑:
- 初始化2000000个对象到ArrayList中
- 打乱容器中的数据顺序
- 进行10次查询,统计每一次消耗的时间
不同计算机的配置情况下,所花的时间是有区别的。 在本机上,花掉的时间大概是600毫秒左右
package collection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import charactor.Hero;
public class TestCollection {
public static void main(String[] args) {
List<Hero> heros = new ArrayList<Hero>();
for (int j = 0; j < 2000000; j++) {
Hero h = new Hero("Hero " + j);
heros.add(h);
}
// 进行10次查找,观察大体的平均值
for (int i = 0; i < 10; i++) {
// 打乱heros中元素的顺序
Collections.shuffle(heros);
long start = System.currentTimeMillis();
String target = "Hero 1000000";
for (Hero hero : heros) {
if (hero.name.equals(target)) {
System.out.println("找到了 hero!" );
break;
}
}
long end = System.currentTimeMillis();
long elapsed = end - start;
System.out.println("一共花了:" + elapsed + " 毫秒");
}
}
}
步骤 2 : HashMap的性能表现
使用HashMap 做同样的查找
- 初始化2000000个对象到HashMap中。
- 进行10次查询
- 统计每一次的查询消耗的时间
可以观察到,几乎不花时间,花费的时间在1毫秒以内
package collection;
import java.util.HashMap;
import charactor.Hero;
public class TestCollection {
public static void main(String[] args) {
HashMap<String,Hero> heroMap = new HashMap<String,Hero>();
for (int j = 0; j < 2000000; j++) {
Hero h = new Hero("Hero " + j);
heroMap.put(h.name, h);
}
System.out.println("数据准备完成");
for (int i = 0; i < 10; i++) {
long start = System.currentTimeMillis();
//查找名字是Hero 1000000的对象
Hero target = heroMap.get("Hero 1000000");
System.out.println("找到了 hero!" + target.name);
long end = System.currentTimeMillis();
long elapsed = end - start;
System.out.println("一共花了:" + elapsed + " 毫秒");
}
}
}
步骤 3 : HashMap原理与字典
在展开HashMap原理的讲解之前,首先回忆一下大家初中和高中使用的汉英字典。
比如要找一个单词对应的中文意思,假设单词是Lengendary,首先在目录找到Lengendary在第 555页。
然后,翻到第555页,这页不只一个单词,但是量已经很少了,逐一比较,很快就定位目标单词Lengendary。
555相当于就是Lengendary对应的hashcode
步骤 4 : 分析HashMap性能卓越的原因
-----hashcode概念-----
所有的对象,都有一个对应的hashcode(散列值)
比如字符串“gareen”对应的是1001 (实际上不是,这里是方便理解,假设的值)
比如字符串“temoo”对应的是1004
比如字符串“db”对应的是1008
比如字符串“annie”对应的也是1008
-----保存数据-----
准备一个数组,其长度是2000,并且设定特殊的hashcode算法,使得所有字符串对应的hashcode,都会落在0-1999之间
要存放名字是"gareen"的英雄,就把该英雄和名称组成一个键值对,存放在数组的1001这个位置上
要存放名字是"temoo"的英雄,就把该英雄存放在数组的1004这个位置上
要存放名字是"db"的英雄,就把该英雄存放在数组的1008这个位置上
要存放名字是"annie"的英雄,然而 "annie"的hashcode 1008对应的位置已经有db英雄了,那么就在这里创建一个链表,接在db英雄后面存放annie
-----查找数据-----
比如要查找gareen,首先计算"gareen"的hashcode是1001,根据1001这个下标,到数组中进行定位,(根据数组下标进行定位,是非常快速的) 发现1001这个位置就只有一个英雄,那么该英雄就是gareen.
比如要查找annie,首先计算"annie"的hashcode是1008,根据1008这个下标,到数组中进行定位,发现1008这个位置有两个英雄,那么就对两个英雄的名字进行逐一比较(equals),因为此时需要比较的量就已经少很多了,很快也就可以找出目标英雄
这就是使用hashmap进行查询,非常快原理。
这是一种用空间换时间的思维方式
步骤 5 : HashSet判断是否重复
HashSet的数据是不能重复的,相同数据不能保存在一起,到底如何判断是否是重复的呢?
根据HashSet和HashMap的关系,我们了解到因为HashSet没有自身的实现,而是里面封装了一个HashMap,所以本质上就是判断HashMap的key是否重复。
再通过上一步的学习,key是否重复,是由两个步骤判断的:
hashcode是否一样
如果hashcode不一样,就是在不同的坑里,一定是不重复的
如果hashcode一样,就是在同一个坑里,还需要进行equals比较
如果equals一样,则是重复数据
如果equals不一样,则是不同数据。
练习: 自定义字符串的hashcode
如下是Java API提供的String的hashcode生成办法;
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
s[0] 表示第一位字符
n表示字符串的长度
本练习并不是要求去理解这个算法,而是自定义一个简单的hashcode算法,计算任意字符串的hashcode
因为String类不能被重写,所以我们通过一个静态方法来返回一个String的hashcode
public static int hashcode(String)
如果字符串长度是0,则返回0。
否则: 获取每一位字符,转换成数字后,相加,最后乘以23
(s[0]+ s[1] + s[2] + s[3]+ s[n-1])*23.
如果值超过了1999,则取2000的余数,保证落在0-1999之间。
如果是负数,则取绝对值。
随机生成长度是2-10的不等的100个字符串,打印用本hashcode获取的值分别是多少
答案:
package collection;
public class TestCollection {
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
int length = (int) (Math.random()*8+2);
String str = randomString(length);
int hashcode = hashcode(str);
System.out.printf("%-11s的自定义hashcode是:%d%n",str,hashcode);
}
}
private static int hashcode(String str) {
// TODO Auto-generated method stub
if(0==str.length())
return 0;
int hashcode = 0;
char[]cs= str.toCharArray();
for (int i = 0; i < cs.length; i++) {
hashcode +=cs[i];
}
hashcode*=23;
//取绝对值
hashcode = hashcode<0?0-hashcode:hashcode;
//落在0-1999之间
hashcode %=2000;
return hashcode;
}
private static String randomString(int length) {
String pool = "";
for (short i = '0'; i <= '9'; i++) {
pool += (char) i;
}
for (short i = 'a'; i <= 'z'; i++) {
pool += (char) i;
}
for (short i = 'A'; i <= 'Z'; i++) {
pool += (char) i;
}
char cs[] = new char[length];
for (int i = 0; i < cs.length; i++) {
int index = (int) (Math.random() * pool.length());
cs[i] = pool.charAt(index);
}
String result = new String(cs);
return result;
}
}
最新文章
- iOS阶段学习第18天笔记(Plist-Archiver-归档与解归档操作)
- div mouseenter 事件在IE下无效
- undefined function mysql_connect()解决方法
- NSMutableArray 存放BOOL
- DirectDraw打造极速图形引擎(Alpha混合)
- 给table中某一列的文字右对齐
- 我的jquery之路
- 关于自定义adapter使用getApplicationContext()影响主题
- 如何使用SecureCRT连接vmware下ubuntu
- POJ2100 Graveyard Design(尺取法)
- ubuntu系统下设置静态IP
- 一次thinkphp框架 success跳转卡顿问题的解决
- word自动备份,word误删内容恢复
- 【深度学习篇】---CNN和RNN结合与对比,实例讲解
- MongoDB数据库发展历程及商业模式
- jdbcTemplete(转)
- tomcat+nginx实现均衡负载
- Codeforces914G Sum the Fibonacci(FWT)
- AssociatedObject关联对象原理实现
- jq循环方法
热门文章
- Do You Know These Plastic Bottle Processing Terms?
- spark实验(一)--linux系统常见命令及其文件互传(2)
- Spring SpringMVC 和 Springboot 的关系(转载)
- Servlet读取xml文件的配置参数
- W - Prime Time 素数判断+前缀和
- Webshell免杀研究
- Java并发编程:Java内存模型JMM
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 辅助类:";text-info"; 类的文本样式
- java并发(二):初探syncronized
- Android 隐藏手机号中间四位和隐藏邮箱地址中间四位