• Java面试题中关于HashMap的小小总结
    时间:2012-03-25?? 作者:佚名?? 出处:互联网

    面试过程中往往会被问关于HashMap的问题,比如:说说Hashpmap的原理,HashMap怎样保证key的唯一性。下面小编给大家简单介绍一下关于HashMap的小小总结。

    1.??? HashMap概述

    ?? HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
    ?
    2.??? HashMap的数据结构

    ?? 在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

    3.?? HashMap的存取

    ??? HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程:
    ??? 1、 当调用put(key,value)时,首先获取key的hashcode,int hash = key.hashCode();
    ??? 2、 再把hash通过一下运算得到一个int h.
    hash ^= (hash >>> 20) ^ (hash >>> 12);
    int h = hash ^ (hash >>> 7) ^ (hash >>> 4);
    为什么要经过这样的运算呢?这就是HashMap的高明之处。先看个例子,一个十进制数32768(二进制1000 0000 0000 0000),经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗?或许这样还看不出什么,再举个数字61440(二进制1111 0000 0000 0000),运算结果是65263(二进制1111 1110 1110 1111),现在应该很明显了,它的目的是让“1”变的均匀一点,散列的本意就是要尽量均匀分布。那这样有什么意义呢?看第3步。
    ??? 3、 得到h之后,把h与HashMap的承载量(HashMap的默认承载量length是16,可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。)进行逻辑与运算,即 h & (length-1),这样得到的结果就是一个比length小的正数,我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index,这是HashTable的改进,HashTable中的算法只是把key的 hashcode与length相除取余,即hash % length,这样有可能会造成index分布不均匀。还有一点需要说明,HashMap的键可以为null,它的值是放在数组的第一个位置。
    ??? 4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素(这个元素是HashMap内部定义的一个类Entity, 基本结构它包含三个类,key,value和指向下一个Entity的next),没有的话就创建一个Entity对象,在 table[index]位置上插入,这样插入结束;如果有的话,通过链表的遍历方式去逐个遍历,看看有没有已经存在的key,有的话用新的value替 换老的value;如果没有,则在table[index]插入该Entity,把原来在table[index]位置上的Entity赋值给新的 Entity的next,这样插入结束。
    总结:keyàhashcodeàhàindexà遍历链表à插入

    4. ? 扩展问题

    要同时复写equals方法和hashCode方法。
    按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同。
    如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
    如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),
    再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法,很简单,比如,String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话,那么a和b的hashCode就会不同,把这两个类当做key存到HashMap中的话就 会出现问题,就会和key的唯一性相矛盾。

    网友留言/评论

    我要留言/评论

    相关文章

    JAVA正则表达式:Pattern类与Matcher类详解:java.util.regex是一个用正则表达式所订制的模式来对字符串进行匹配工作的类库包。它包括两个类:Pattern和Matcher Pattern 一个Pattern是一个正则表达式经编译后的表现模式。 Matcher 一个Matcher对象是一个状态机器,它依据Pattern对象做为匹配模式对字符串展开匹配检查。 首先一个Pattern实例订制了一个所用语法与PERL的类似的正则表达式经编译后的模式,然后一个Matcher实例在这个给定的Pattern实例的模式控制下进行字符串的匹配工作。
    线上解决Resin服务响应过慢的几个方法:最近Web服务访问量过大,由于服务器配置比较差,数量也较少,导致服务响应过慢。为了优化服务和提高响应,下面总结出几条查询Resin问题的方法。
    Java 中 Listener 模式示例:Listener模式在Java中很常见,并且很有用,下面例举一下Java的Listener模式,希望对大家有所帮助。
    Java Annotation手册(详解):在上篇文章《Java Annotation入门》中概要性的介绍了Annotation的定义、使用,范围涵盖较广,但是深度不够。所以作者在《Java Annotation入门》后,继续整理了Annotation的概念和知识点,与喜欢research的朋友们共享。
    利用 Java 6 javax.script 包直接处理 JSON:以往我们在Java中处理 JSON 数据时,经常会引用到各种 json 的第三方 jar 包。有时很简单的功能,而引用比较臃肿的包,是比较难以容忍的。很高兴我们可以使用Java 6 提供的 javax.script 包来处理。 Java 有了支持其他脚本语言的特性,例如 JavaScript。而 JavaScript 对 JSON 的支持是天生具备的。让我们来看一些实例。
    (DOM解析xml )Android中的XML解析与生成:DOM解析XML文件时,会将XML文件的所有内容以对象树方式存放在内存中,然后允许您使用DOM API遍历XML树、检索所需的数据。使用DOM操作XML的代码看起来比较直观,并且,在某些方面比基于SAX的实现更加简单。但是,因为DOM需要将XML文件的所有内容以对象树方式存放在内存中,所以内存的消耗比较大,特别对于运行Android的移动设备来说,因为设备的资源比较宝贵,所以建议还是采用SAX来解析XML文件,当然,如果XML文件的内容比较小采用DOM是可行的。
    JRockit读书笔记I — Java代码的高效执行:《Oracle JRockit: The Definitive Guide》一书是由Oracle JRockit的两位资深开发人员写的,其中的Marcus Hirt更是JRockit Mission Control的leader,这本书详细的对Oracle JRockit进行了介绍,最突出的特点非常系统化的介绍了一个JVM通常是如何实现的,而JRockit这样一个极为优秀的JVM又是做了哪些优化,为什么做这些优化,这本书对于对JVM感兴趣的同学而言应该是必读的一本书,其实即使对于JVM兴趣不强的同学,里面的优化思路的介绍也是值得学习,本系列的blog主要是总结看这本书得到的一些收获,由于书中知识量巨大,因此得分成多篇blog来总结了。
    JSTL教程大全 - core篇和sql篇:最近又开始搞WEB部分开发,使用了JTSL,虽然知道这玩意很简单,但是真正做起来还是需要查询相关资料,搜了半天都没找到合适的,最后终于找到了一份较全的文档,给大家分享一下。JSTL标签、
    JSTL教程大全 - fn函数篇:最近又开始搞WEB部分开发,使用了JTSL,虽然知道这玩意很简单,但是真正做起来还是需要查询相关资料,搜了半天都没找到合适的,最后终于找到了一份较全的文档,给大家分享一下。
    有关Mina基础技术知识介绍:Apache MINA 是一个网络应用框架,有助于用户非常方便地开发高性能、高伸缩性的网络应用。初学MINA的同学开始可能会感觉迷茫,为了让初学者更快的入门,qq运动的红包存在哪里吧给大家准备一篇Mina入门介绍,希望对大家有所帮助。