康熙几个儿子的下场,八路军129师386旅,模范情书吉他谱
步骤 1 : list查找的低效率
假设在list中存放着无重复名称，没有顺序的2000000个hero
要把名字叫做“hero 1000000”的对象找出来
list的做法是对每一个进行挨个遍历，直到找到名字叫做“hero 1000000”的英雄。
最差的情况下，需要遍历和比较2000000次，才能找到对应的英雄。
测试逻辑：
我要评论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 做同样的查找
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不一样，则是不同数据。
练习：
如下是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;
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论