http://lukuijun.iteye.com/blog/340756
题目:请说出hashCode方法,equals方法,HashSet,HasMap之间的关系?
解答:策略,分析jdk的源代码:
- public HashSet() {
- ap = new HashMap<E,Object>();
- }
1、HashSet底层是采用HashMap实现的。
private transient HashMap<E,Object>
map;是HashSet类里面定义的一个私有的成员变量。并且是transient类型的,在序列化的时候是不会序列化到文件里面去的,信息会丢失。
HashMap<E,Object>里面的key为E,是HashSet<E>里面放置的对象E(对象的引用,为了简单方便起见
我说成是对象,一定要搞清楚,在集合里面放置的永远都是对象的引用,而不是对象,对象是在堆里面的,这个一定要注
意),HashMap<E,Object>的value是Object类型的。
2、这个HashMap的key就是放进HashSet中对象,value是Object类型的。当我去使用一个默认的构造方法的时候,执行
public HashSet() {map = new
HashMap<E,Object>();},会将HashMap实例化,将集合能容纳的内型作为key,Object作为它的value。
当我们去往HashSet里面放值的时候,这个HashMap<E,Object>里面的Object类型的value到底取什么值呢?这个
时候我们就需要看HashSet的add方法,因为add方法可以往里面增加对象,通过往里面增加对象,会导致底层的HashMap增加一个key和
value。这个时候我们看一下add方法: public boolean add(E e) {return map.put(e,
PRESENT)==null;},add方法接受一个E类型的参数,这个E类型就是我们在HashSet里面能容纳的类型,当我们往HashSet里面
add对象的时候,HashMap是往里面put(E,PRESET),增加E为key,PRESET为value,PRESET是这样定义
的:private static final Object PRESENT = new
Object();从这里我们知道PRESET是private static final
Object的常量并且已经实例化好了。HashMap<E,Object>()中的key为HashSet中add的对象,不能重
复,value为PRESET,这是jdk为了方便将value设为常量PRESET,因为value是可以重复的。
3、当调用HashSet的add方法时,实际上是向HashMap中增加了一行(key-value对),该行的key就是向HashSet增加的那个对象,该行的value就是一个Object类型的常量。
接着,我们看看HashMap的源码,流程讲到map.put(e, PRESENT)==null,我们往HashSet里面add一个对象,那么HashMap就往里面put(key,value)。HashMap的put方法源码如下:
- public V put(K key, V value) {
- if (key == null )
- return putForNullKey(value);
- int hash = hash(key.hashCode());
- int i = indexFor(hash, table.length);
- for (Entry<K,V> e = table[i]; e != null ; e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this );
- return oldValue;
- }
- }
- modCount++;
- addEntry(hash, key, value, i);
- return null ;
- }
首先,如果key == null,这个key是往HashSet里面add的那个对象,它返回一个putForNullKey(value),它是一个方法,源码如下:
- private V putForNullKey(V value) {
- for (Entry<K,V> e = table[ 0 ]; e != null ; e = e.next) {
- if (e.key == null ) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this );
- return oldValue;
- }
- }
- modCount++;
- addEntry(0 , null , value, 0 );
- return null ;
- }
这里面有一个Entry,我们看看它的源码:
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- final int hash;
- /**
- * Creates new entry.
- */
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
- public final K getKey() {
- return key;
- }
- public final V getValue() {
- return value;
- }
- public final V setValue(V newValue) {
- V oldValue = value;
- value = newValue;
- return oldValue;
- }
- public final boolean equals(Object o) {
- if (!(o instanceof Map.Entry))
- return false ;
- Map.Entry e = (Map.Entry)o;
- Object k1 = getKey();
- Object k2 = e.getKey();
- if (k1 == k2 || (k1 != null && k1.equals(k2))) {
- Object v1 = getValue();
- Object v2 = e.getValue();
- if (v1 == v2 || (v1 != null && v1.equals(v2)))
- return true ;
- }
- return false ;
- }
- public final int hashCode() {
- return (key== null ? 0 : key.hashCode()) ^
- (value==null ? 0 : value.hashCode());
- }
- public final String toString() {
- return getKey() + "=" + getValue();
- }
- /**
- * This method is invoked whenever the value in an entry is
- * overwritten by an invocation of put(k,v) for a key k that's already
- * in the HashMap.
- */
- void recordAccess(HashMap<K,V> m) {
- }
- /**
- * This method is invoked whenever the entry is
- * removed from the table.
- */
- void recordRemoval(HashMap<K,V> m) {
- }
- }
static class Entry表示它是一个静态的内部类,注意,外部类是不能用static的,对类来说,只有内部类能用static来修饰。这个Entry它实现了一个 Map.Entry<K,V>接口,我看看Map.Entry<K,V>的源码:
- interface Entry<K,V> {
- K getKey();
- V getValue();
- V setValue(V value);
- boolean equals(Object o);
- int hashCode();
- }
Map.Entry<K,V>
它是一个接口,里面定义了几个方法,Map.Entry<K,V>它实际上是一个内部的接口(inner
interface),Map.Entry干什么用的呢?我看看Map接口有一个 Set<Map.Entry<K, V>>
entrySet();方法,它返回一个Set集合,它里面是Map.Entry<K,
V>类型的,这个方法用得非常多。表示你在调用一个Map的entrySet()方法,它会返回一个Set集合,这个集合里面放置的就是你的Map
的key和value这两个对象所共同组成的Map.Entry类型的那样的对象,Map.Entry类型对象里面放置的就是你的HashMap里面的
key和value,所以说当你去调用一个Map(不管是HashMap还是Treemap)的entrySet()方法,会返回一个Set集合,个集合
里面放置的就是你的Map的key和value这两个对象所共同组成的Map.Entry类型的那样的对象。
HashMap的底层是怎样维护的呢?我们看一下源码:
- /**
- * The table, resized as necessary. Length MUST Always be a power of two.
- */
- transient Entry[] table;
它是一个Entry类型的数组,table数组里面放Entry类型的,Entry的源码有:
- final K key;
- V value;
这里的K表示HashMap的key,V表示HashMap的value,所以我们可以大胆的断定,HashMap的底层是用数组来维护的。理解这一点非常重要,因为java的集合,底层大部分都是用数组来维护的,顶层之所以有那么高级,是因为底层对其进行了封装。
4、HashMap底层采用数组来维护。数组里面的每一个元素都是Entry,而这个Entry里面是Key和value组成的内容。
我们看HashMap的put方法,如果key == null,返回putForNullKey(value),看putForNullKey方法:
- private V putForNullKey(V value) {
- for (Entry<K,V> e = table[ 0 ]; e != null ; e = e.next) {
- if (e.key == null ) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this );
- return oldValue;
- }
- }
- modCount++;
- addEntry(0 , null , value, 0 );
- return null ;
- }
首
先做一个for循环,从Entry数组的第一个元素开始,e.next是static class Entry<K,V>
implements Map.Entry<K,V>的一个成员属性 Entry<K,V>
next;next也是Entry<K,V>类型的,next也可以指向Entry类型的对象,当我知道一个Entry类型的对象,就可以通
过它的next属性知道这个Entry类型的对象的后面一个Entry类型的对象,通过这个next变量来寻找下一个。next指向的Entry类型的对
象不在数组中。
接着判断e.key == null,如果e.key 为null,说明HashMap里面没有这个对象,这个时就会将我们add到Set里面的对象真真正正的放置到Entry数组里面去。
我们在看HashMap的put方法里面:int hash =
hash(key.hashCode());如果key不为null,这个key就是我们往HashSet里面放置的那个对象。它就会调用
key.hashCode()方法,这是流程转到hashCode方法里面去了,调用hashCode()方法返回hash码,接着调用hash方法,我
们看看hash方法源码:
- static int hash( int h) {
- // This function ensures that hashCodes that differ only by
- // constant multiples at each bit position have a bounded
- // number of collisions (approximately 8 at default load factor).
- h ^= (h >>> 20 ) ^ (h >>> 12 );
- return h ^ (h >>> 7 ) ^ (h >>> 4 );
- }
这个hash方法异常复杂。并且jdk5.0和jdk6.0对这个方法的实现方式也是不一样的。hash方法就是我们在数据结构中讲的散列函数。它是经过放进HashSet里面的对象作为key得到hashCode码,在进行散列得到的一个整数。
接着执行put方法里面的int i = indexFor(hash, table.length);语句,我们看看indexFor方法的源码:
- * Returns index for hash code h.
- */
- static int indexFor( int h, int length) {
- return h & (length- 1 );
- }
indexFor方法也返回一个整型值,将上面通过hash方法得到的int值和数组的长度进行与运算,然后返回。他是往HashSet里面放置
对象位置的索引值,它的值永远在0到数组长度减1之间,它是不会超过数组长度的。它是有hash方法和indexFor方法来保证不会超过的。
所以对于put方法,如果indexFor返回2,那么就在数组的第2个位置,然后执行for循环,如果第2个位置没有元素,则跳出for循
环,调用addEntry方法将这个元素添加到数组中第2个位置,addEntry(hash, key, value,
i);这是比较简单的情况。比较复杂的情况,数组的第2个位置已经有元素了,不为null,那么它是怎么做的呢?我们看一下:
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this );
- return oldValue;
- }
它
用这种方式方式进行比较,(e.hash == hash && ((k = e.key) == key ||
key.equals(k))它会医用k的equals方法来个第2个位置上的元素进行比较,如果这个equals方法返回true,表示这个对象确实是
一个对象,这个时候还没有完,如果e.hash ==
hash并且key.equals(k)表示真的是相同的,这个时候就会用新的相同的对象的值替换就的那个值,同时它把旧的那个被替换的值给返回。如果不
相同呢,它会根据next指向的对象再去比较,如果又不成功又会根据它的next链去寻找比较,一直到最后一个,当为null的时候下一个就不存在了。这
就是put方法的for过程。我们往HashMap里面放值的时候,两种情况,要么放进去了增加(key-value)要么替换掉(将旧的值替换掉了,其
实是一样的)了。如果都不成功,表示在链上不存在,这个时候就直接添加到数组,同时将添加的这个Entry的next执行往外替换的那个Entry,这样
做的好处就是减少索引时间。不管你链接有多长,每次查找时间固定(用hash方法)。
5、调用增加的那个对象的hashCode方法,来得到一个hashCode值,然后根据该值来计算出一个数组的下表索引(计算出数组中的一个位置)
6、将准备增加到map中的对象与该位置上的对象进行比较(equals方法),如果相同,那么就将该位置上的那个对象(Entry类型)的
value值替换掉,否则沿着该Entry的链接继承重复上述过程,如果到链的最后仍然没有找到与此对象相同的对象,那么这个时候就会将该对象增加到数组
中,将数组中该位置上的那个Entry对象链到该对象的后面。
7、对于HashSet,HashMap来说,这样做就是为了提高查找的效率,使得查找时间不随着Set或者Map的大小而改变。
发表评论
-
深入分析 Java 中的中文编码问题
2011-11-16 07:45 0几种常见的编码格式 ... -
Java 编码
2011-11-16 07:44 0http://zhidao.baidu.com/quest ... -
java字符编码原理解析
2011-11-16 07:43 0可以理解为计算机没 ... -
HttpClient
2011-11-03 11:07 824From http://www.blogjava.net/Al ... -
ECLIPSE ANT OutOfMemoryError
2011-08-04 17:23 1011ANT BUILD MEMORY ERROR: [cl ... -
JDBC BATCH
2011-07-05 14:58 0PreparedStatement ps = conn.pre ... -
OUT OF MEMORY WHEN BUILD
2011-02-22 17:47 01, ANT BUILD: In Eclipse op ... -
spring weblogic jndi
2011-02-16 09:18 1837weblogic:weblogic8.1 数据库:MySql ... -
log4j 邮件
2011-01-24 15:54 0<!-- 设置上下文参数 --> ... -
tomcat weblogic
2010-12-01 11:25 1862EJB 层基本搞定,以前测试 EJB 也都是写一个 appli ... -
ant weblogic “local class incompatible: stream classdesc serialVersionUI”
2010-11-29 12:41 2227weblogic.management.Management ... -
Debugging with the Maven Jetty Plugin in Eclipse
2010-11-15 17:42 1035debug: http://docs.codehaus.or ... -
maven tomcat eclipse debug
2010-11-15 17:36 1946from: http://bandaidprogrammin ... -
maven app tomcat 部署
2010-11-11 15:56 1307修改pom.xml,添加如下配置: <build ... -
Maven Cargo Tomcat 部署
2010-11-11 15:49 1769pom.xml中<build>下添加如下代码: ... -
java中读取配置文件各种方法
2010-09-07 12:31 01。使用Java.util.Properties类的load( ... -
ThreadGroup
2010-05-25 08:47 0在Java中每个线程都属于某个线程组(ThreadGroup) ... -
java Excel 导出
2010-03-28 20:06 0public void createExcel(OutputS ... -
java小数保留两位小数
2009-11-19 16:49 2337方式一: 四舍五入 double f = ... -
java中实现xml schema 验证文件
2009-11-16 20:05 3877XML 是可扩展标记语言,也就是说其中的标记我们可以按照我们 ...
相关推荐
功能说明: 环境说明: 开发软件:VS 2017 (版本2017以上即可,不能低于2017) 数据库:SqlServer2008r2(数据库版本无限制,都可以导入) 开发模式:mvc。。。
labview程序代码参考学习使用,希望对你有所帮助。
大米外贸商城系统 简称damishop 完全开源版,只需做一种语言一键开启全球133中语言自动翻译功能,价格实现自动汇率转换,集成微信支付宝 paypal以及国外主流支付方式,自带文章博客系统。 软件架构 基于MVC+语言包模式,增加控制台,API导入产品方便对接其他系统(带json示例数据)。 使用要求 PHP7.4+ MYSQL5.6+ REDIS(可选) 安装方法 composer install 打开安装向导安装 http://您的域名/install 特色 1、缓存层增加时间与批量like删除 2、API产品导入方便对接其他系统 3、增加控制台命令行,命令行生成语言翻译包 4、后台一键开启自动翻译模式,支持全球133中语言,由于google代理翻译需要收费,这个功能需要付费。 5、可选购物车与ajax修改购物车产品 6、一键结算checkout 7、增加网站前台自定义路由 方便seo 更新日志 v3.9.7 集成鱼码支付接口,方便个人站长即使收款到账使用 v3.9.3 更新内容 1:增加ueditor与旧编辑器切换 2:增加可视化布局插
labview程序代码参考学习使用,希望对你有所帮助。
labview程序代码参考学习使用,希望对你有所帮助。
毕设和企业适用springboot人工智能客服系统类及旅游规划平台源码+论文+视频