首页 > 代码库 > (考研)散列表和hashcode和hashmap
(考研)散列表和hashcode和hashmap
package tt; import java.util.HashMap; import java.util.Map; public class a0 { public static void main(String[] args){ /** * 如果两个对象相同,那么这两个对象的hashCode一定要相同
String a1 ="abc" String a2 ="abc" 这a1和a2就是相同的对象 * * 两个对象的hashCode相同,并不一定表示两个对象就相同,他们“存放在同一个篮子里”
String s1 = new String("abc") String s2 = new String("abc") * * 验证:只要2个对象的内容是同的返回hashCode是相同的 * 那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。 */ Integer i1 = 100; Integer i2=Integer.valueOf(100); String s1="a"; String s2="a"; //实质会执行如下的代码 Integer i1 = Integer.valueOf(100),上面的2句话是等效的 //若int值在[-128,-127]之间的话,会返回缓冲池的数据,否的 return new Integer(i) System.out.println(i1==i2);//true System.out.println(s1==s2);//true System.out.println("code"+i1.hashCode()+","+i2.hashCode()+";"+s1.hashCode()+","+s2.hashCode()); //code100,100;97,97 //Integer 变量名; 若值在[-128,-127]之间,变量名都是指向同一对象 //String str="abc" 只要后面的值都相同,多个变量名指向同一个“abc”
Integer i3 = new Integer(100); String ss = new String("a"); System.out.println(i1==i3);//flase System.out.println(s2== ss);//false System.out.println("code"+i1.hashCode()+","+i3.hashCode()+";"+s2.hashCode()+","+ss.hashCode()); //code100,100;97,97 Integer in = new Integer(100); Integer in1 = new Integer(100); String abc = "abcd"; String abc1="abcd"; System.out.println("code"+in.hashCode()+","+in1.hashCode()+";"+abc.hashCode()+","+abc1.hashCode()); //code100,100;2987074,2987074 //对象肯定不同的,但是内容是同的 String str1 = "name"; String str2 = new String("name"); System.out.println(str1==str2);//false System.out.println(str1.hashCode() +" "+ str2.hashCode());//3373707 3373707 Map<String,String> map =new HashMap<String,String>(); /* 如果key在链表中已存在,则替换为新value*/ * 对象equals 是true的话,hashCode需要相同,但是hashCode相同的对象不一定equals,这就是所谓的冲突现象,但是有不同的冲突解决方法。你的hashCode()设计的好的话冲突也就小了。比如楼上给出的超出int范围之后这种hashCode()实现,对象肯定是无数的,但是hash实现是有限的呢,所以冲突了 */ map.put(str1,"Tom"); map.put(str2, "Lisa"); System.out.println(map); //输出 name = "Lisa" //你构造不出 key1 和 key2 对象不同,但是他们的hashcode相同 } }
HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
Put操作:
如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?
这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起
当我们往HashMap中put元素的时候,先根据key的重新计算元素的hashCode,根据hashCode得到这个元素在table数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上
get操作(先hashcode方法再equals方法)
有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。
(考研)散列表和hashcode和hashmap
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。