|
|
|
本视频是解读性视频，所以希望您已经看过了本知识点的内容，并且编写了相应的代码之后，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
20分40秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 步骤 1 : List查找的低效率 步骤 2 : HashMap的性能表现 步骤 3 : HashMap原理与字典 步骤 4 : 分析HashMap性能卓越的原因 步骤 5 : HashSet判断是否重复 步骤 6 : 练习-自定义字符串的hashcode 步骤 7 : 答案-自定义字符串的hashcode 步骤 8 : 练习-自定义MyHashMap 步骤 9 : 答案-自定义MyHashMap 步骤 10 : 练习-内容查找性能比较 步骤 11 : 答案-内容查找性能比较
假设在List中存放着无重复名称，没有顺序的2000000个Hero
要把名字叫做“hero 1000000”的对象找出来 List的做法是对每一个进行挨个遍历，直到找到名字叫做“hero 1000000”的英雄。 最差的情况下，需要遍历和比较2000000次，才能找到对应的英雄。 测试逻辑： 1. 初始化2000000个对象到ArrayList中 2. 打乱容器中的数据顺序 3. 进行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 + " 毫秒");
}
}
}
使用HashMap 做同样的查找
1. 初始化2000000个对象到HashMap中。 2. 进行10次查询 3. 统计每一次的查询消耗的时间 可以观察到，几乎不花时间，花费的时间在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 + " 毫秒");
}
}
}
在展开HashMap原理的讲解之前，首先回忆一下大家初中和高中使用的汉英字典。
比如要找一个单词对应的中文意思，假设单词是Lengendary,首先在目录找到Lengendary在第 555页。 然后，翻到第555页，这页不只一个单词，但是量已经很少了，逐一比较，很快就定位目标单词Lengendary。 555相当于就是Lengendary对应的hashcode
-----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进行查询，非常快原理。 这是一种用空间换时间的思维方式
HashSet的数据是不能重复的，相同数据不能保存在一起，到底如何判断是否是重复的呢？
根据HashSet和HashMap的关系，我们了解到因为HashSet没有自身的实现，而是里面封装了一个HashMap，所以本质上就是判断HashMap的key是否重复。 再通过上一步的学习，key是否重复，是由两个步骤判断的： hashcode是否一样 如果hashcode不一样，就是在不同的坑里，一定是不重复的 如果hashcode一样，就是在同一个坑里，还需要进行equals比较 如果equals一样，则是重复数据 如果equals不一样，则是不同数据。
如下是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获取的值分别是多少
在查看答案前，尽量先自己完成，碰到问题再来查看答案，收获会更多
本视频是解读性视频，所以希望您已经看过了本答案的内容，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
8分57秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 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;
}
}
根据前面学习的hashcode的原理和自定义hashcode, 设计一个MyHashMap，实现接口IHashMap
MyHashMap内部由一个长度是2000的对象数组实现。 设计put(String key,Object value)方法 首先通过上一个自定义字符串的hashcode练习获取到该字符串的hashcode,然后把这个hashcode作为下标，定位到数组的指定位置。 如果该位置没有数据，则把字符串和对象组合成键值对Entry，再创建一个LinkedList，把键值对，放进LinkedList中，最后把LinkedList 保存在这个位置。 如果该位置有数据，一定是一个LinkedList,则把字符串和对象组合成键值对Entry，插入到LinkedList后面。 设计 Object get(String key) 方法 首先通过上一个自定义字符串的hashcode练习获取到该字符串的hashcode,然后把这个hashcode作为下标，定位到数组的指定位置。 如果这个位置没有数据，则返回空 如果这个位置有数据，则挨个比较其中键值对的键-字符串，是否equals，找到匹配的，把键值对的值，返回出去。找不到匹配的，就返回空 package collection;
public interface IHashMap {
public void put(String key,Object object);
public Object get(String key);
}
package collection;
//键值对
package collection;
//键值对
public class Entry {
public Entry(Object key, Object value) {
super();
this.key = key;
this.value = value;
}
public Object key;
public Object value;
@Override
public String toString() {
return "[key=" + key + ", value=" + value + "]";
}
}
在查看答案前，尽量先自己完成，碰到问题再来查看答案，收获会更多
本视频是解读性视频，所以希望您已经看过了本答案的内容，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
11分24秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 package collection;
import java.util.LinkedList;
public class MyHashMap implements IHashMap {
LinkedList<Entry>[] values = new LinkedList[2000];
@Override
public void put(String key, Object object) {
// 拿到hashcode
int hashcode = hashcode(key);
// 找到对应的LinkedList
LinkedList<Entry> list = values[hashcode];
// 如果LinkedList是null，则创建一个LinkedList
if (null == list) {
list = new LinkedList<>();
values[hashcode] = list;
}
// 判断该key是否已经有对应的键值对
boolean found = false;
for (Entry entry : list) {
// 如果已经有了，则替换掉
if (key.equals(entry.key)) {
entry.value = object;
found = true;
break;
}
}
// 如果没有已经存在的键值对，则创建新的键值对
if (!found) {
Entry entry = new Entry(key, object);
list.add(entry);
}
}
@Override
public Object get(String key) {
// 获取hashcode
int hashcode = hashcode(key);
// 找到hashcode对应的LinkedList
LinkedList<Entry> list = values[hashcode];
if (null == list)
return null;
Object result = null;
// 挨个比较每个键值对的key，找到匹配的，返回其value
for (Entry entry : list) {
if (entry.key.equals(key)) {
result = entry.value;
break;
}
}
return result;
}
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;
}
public static void main(String[] args) {
MyHashMap map =new MyHashMap();
//
// map.put("t", "坦克");
// map.put("adc", "物理");
// map.put("apc", "魔法");
// map.put("t", "坦克2");
//
// System.out.println(map.get("adc"));
//
// System.out.println(map);
System.out.println(map.hashcode("name=hero-2387"));
System.out.println(map.hashcode("name=hero-5555"));
}
public String toString() {
LinkedList<Entry> result = new LinkedList();
for (LinkedList<Entry> linkedList : values) {
if (null == linkedList)
continue;
result.addAll(linkedList);
}
return result.toString();
}
}
重复前面的 练习-查找内容性能比较 ，不过不使用HashMap,而是使用上个练习中自定义的MyHashMap.
准备一个ArrayList其中存放100000(十万个)Hero对象，其名称是随机的,格式是hero-[4位随机数] hero-3229 hero-6232 hero-9365 ... 因为总数很大，所以几乎每种都有重复，把名字叫做 hero-5555的所有对象找出来 要求使用两种办法来寻找 1. 不使用MyHashMap，直接使用for循环找出来，并统计花费的时间 2. 借助MyHashMap，找出结果，并统计花费的时间
在查看答案前，尽量先自己完成，碰到问题再来查看答案，收获会更多
本视频是解读性视频，所以希望您已经看过了本答案的内容，带着疑问来观看，这样收获才多。 不建议一开始就观看视频
3分3秒 本视频采用html5方式播放，如无法正常播放，请将浏览器升级至最新版本，推荐火狐，chrome，360浏览器。 如果装有迅雷，播放视频呈现直接下载状态，请调整 迅雷系统设置-基本设置-启动-监视全部浏览器 (去掉这个选项)。 chrome 的 视频下载插件会影响播放，如 IDM 等，请关闭或者切换其他浏览器 package collection;
import java.util.ArrayList;
import java.util.List;
import charactor.Hero;
public class TestCollection {
public static void main(String[] args) {
List<Hero> hs =new ArrayList<>();
System.out.println("初始化开始");
for (int i = 0; i < 100000; i++) {
Hero h = new Hero( "hero-" + random());
hs.add(h);
}
//名字作为key
//名字相同的hero，放在一个List中，作为value
MyHashMap heroMap =new MyHashMap();
for (Hero h : hs) {
List<Hero> list= (List<Hero>) heroMap.get( h.name);
if(list==null){
list = new ArrayList<>();
heroMap.put(h.name, list);
}
list.add(h);
}
System.out.println("初始化结束");
System.out.println("开始查找");
findByIteration(hs);
findByMap(heroMap);
}
private static List<Hero> findByMap(MyHashMap m) {
long start =System.currentTimeMillis();
List <Hero>result= (List<Hero>) m.get("hero-5555");
long end =System.currentTimeMillis();
System.out.printf("通过map查找，一共找到%d个英雄，耗时%d 毫秒%n",result.size(),end-start);
return result;
}
private static List<Hero> findByIteration (List<Hero> hs) {
long start =System.currentTimeMillis();
List<Hero> result =new ArrayList<>();
for (Hero h : hs) {
if(h.name.equals("hero-5555")){
result.add(h);
}
}
long end =System.currentTimeMillis();
System.out.printf("通过for查找，一共找到%d个英雄，耗时%d 毫秒%n", result.size(),end-start);
return result;
}
public static int random(){
return ((int)(Math.random()*9000)+1000);
}
}
HOW2J公众号，关注后实时获知最新的教程和优惠活动，谢谢。
问答区域
2024-07-11
MyHashMap实现
回答已经提交成功，正在审核。 请于 我的回答 处查看回答记录，谢谢
2023-10-02
练习-内容查找性能比较之另解
回答已经提交成功，正在审核。 请于 我的回答 处查看回答记录，谢谢
2023-04-07
Integer.parseInt(String.valueOf(c))，char转int报错
2022-06-01
6
2021-07-13
练习-内容查找性能比较
提问太多，页面渲染太慢，为了加快渲染速度，本页最多只显示几条提问。还有 46 条以前的提问，请 点击查看
提问之前请登陆
提问已经提交成功，正在审核。 请于 我的提问 处查看提问记录，谢谢
|
