- 浏览: 20826 次
- 性别:
- 来自: 上海
-
最新评论
本文转帖自http://lukuijun.iteye.com/blog/340756
题目:请说出hashCode方法,equals方法，HashSet，HasMap之间的关系？
解答:策略,分析jdk的源代码:
1、HashSet底层是采用HashMap实现的。
public HashSet() {
map = new HashMap<E,Object>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
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;
}
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;
}
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<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();
}
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的底层是怎样维护的呢?我们看一下源码:
transient Entry[] table;
/**
* 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;
}
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);
}
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);
}
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;
}
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的大小而改变。
发表评论
-
常用oracle语句备忘
2009-08-14 13:53 1336/*============================= ... -
排序算法
2009-08-11 15:15 740最近在学习算法的一些 ... -
关于SQL 数据库表中的聚集索引和非聚集索引等
2009-08-10 16:34 2327今天看SQL方面的书，看到关于 表索引方面的讲解不太 ... -
SQL Server 2005 自动备份
2009-07-31 14:03 4194今天配置了SQL Server 2005 ... -
Socket 字符集
2009-07-27 17:39 1468最近在将一个项目由MyEclipse迁移到NetBeans的时 ... -
NetBeans 字体设置
2009-07-26 16:09 1977最近下载了最新的NetBeans6.7玩玩，其实Net ... -
SQL Server数据库纵向转横向
2009-07-22 11:09 4534以一张薪资表为例，表结构如下： 表结构中，每 ... -
SQL Server 2005 分页SQL
2009-07-15 16:53 2287使用SQL Server 2005的 ...
相关推荐
之所以把HashSet和HashMap放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也是说HashSet里面有一个HashMap（适配器模式）。因此本文将重点分析HashMap。 HashMap实现了Map...
这篇集合总结一共包括十二节，介绍了一些接口和实现类的底层源码以及基本的增加、删除元素等的操作（包括List、Map、Set接口、ArrayList、Vector、LinkedList、HashSet、TreeSet、HashMap、TreeMap等实现类）。...
Collections 源码 java Java Java的ArrayList、LinkedList、HashMap、TreeMap、LinkedHashMap、HashSet、TreeSet相关源码分析，及相关问题和应用总结。
源码分析：ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap 线程状态、线程机制、线程通信、J.U.C 组件、JMM、线程安全、锁优化 磁盘操作、字节操作、字符...
集合源码分析 java基础复习 [TOC] 一、集合 1.Iterator 2.Collection 2.1 List--->有序、有索引、元素可重复 1.ArrayList: 底层是数组结构、查询快、增删慢、不同步 添加第一个元素的时候，创建默认个数是10个，...
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
源码分析：ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap Java 并发编程 > 线程机制、线程通信、J.U.C组件、JMM、线程安全、锁优化 Java I/O 磁盘...
3.3.2 经验之谈－常见错误的分析与处理40 3.3.3 Java标识符命名规则41 3.3.4 关键字42 3.3.5 常量42 3.4 运算符43 3.4.1 算术运算符43 3.4.2 赋值操作符45 3.4.3 关系操作符47 3.4.4 逻辑操作符48 3.4.5 位操作符49 ...
基于java tcp socket通信的拆包和装包源码 java-interview javac.exe&java.exe&javadoc.exe&PATH&CLASSPATH ...源码分析(集合&框架) 运行时数据区域 内存溢出 垃圾回收 垃圾收集器 类加载的过程 ComboBox（下拉列表框）
java内核源码 Java指南针 基础核心 基础知识 反射 泛型 动态代理 JDK8新特性 集合容器 多线程与并发 Spring SpringMVC SpringBoot Mybatis 数据结构与算法 入门基础 基础数据结构 数组&链表 数组&链表进阶 栈 队列 ...
java jdk1.8 源码 Java-source-reading 缓慢更新一些个人学习java相关源码过程中的笔记，在这里你将不可避免地看到以下情况： 个别不懂/没想好的地方留空待补全 限于个人水平出现的...HashMap HashSet LinkedHashMap
7.7 HashSet和HashMap的性能选项 282 7.8 操作集合的工具类：Collections 283 7.8.1 排序操作 283 7.8.2 查找，替换操作 287 7.8.3 同步控制 288 7.8.4 设置不可变集合 288 7.9 烦琐的接口：Enumeration 289 ...