【达内java培训】Java中HashMap的工作机制.doc

1、http:/【 达内 java 培训】Java 中 HashMap 的工作机制现在很多的 Java 程序员都会把 HashMap 当作一个热门话题，今天我也来说一说 Hashmap。我假设你对 HashMap 感兴趣，另外我认为你已经了解了 HashMap 的基础，这里我就不再赘述 HashMap是个什么东东，如果对于你来讲 HashMap 还是一个新概念的话，你可以去看看官方的javadoc.http:/目录： 1、一句话回答2、什么是哈希3、关于 Entry 类的一点介绍4、put()方法实际上做了什么5、get()方法内部工作机制6、注意点一句话回答 如果任何人让我描述一下 HashMa

2、p 的工作机制的话，我就简单的回答： “基于 Hash 的规则”。这句话非常简单，但是要理解这句话之前，首先我们得了解什么是哈希，不是么？什么是哈希 哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串，用这个串来确定变量/对象的唯一性。一个正确的哈希函数必须遵守这个准则。当哈希函数应用在相同的对象或者 equal 的对象的时候，每次执行都应该返回相同的值。换句话说，两个相等的对象应该有相同的 hashcode。注：所有 Java 对象都从 Object 类继承了一个默认的 hashCode()方法。这个方法将对象在内存中的地址作为整数返回，这是一个很好的 hash 实现，他确保

3、了不同的对象拥有不同的 hashcode。关于 Entry 类的一点介绍 一个 map 的定义是：一个映射键（key ）到值（value ）的对象。非常简单对吧。http:/所以，在 HashMap 中一定有一定的机制来存储这些键值对。使得， HashMap 有一个内部类 Entry，看起来像这样。static class Entry implements Map.Entry final K key; V value; Entry next; final int hash; ./More code goes here 当然，Entry 类有属性用来存储键值对映射。key 被 final 标记，

4、除了 key 和 value，我们还能看到两个变量next 和 hash。接下来我们试着理解这些变量的含义。put()方法实际上做了什么 再进一步看 put 方法的实现之前，我们有必要看一看 Entry 实例在数组中的存储，HashMap 中是这样定义的：/* * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry table; 现在再来看 put 方法的实现。/* * Associates the specified value with the specified

5、 key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * param key key with which the specified value is to be associated * param value value to be associated with the specified key http:/* return the previous value associated with key, or * null if

6、 there was no mapping for key. * (A null return can also indicate that the map * previously associated null with key.) */ 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 e = tablei; e != null;

7、e = e.next) Object k; if (e.hash = hash e.value = value; e.recordAccess(this); return oldValue; modCount+; addEntry(hash, key, value, i); return null; 让我们一步一步的看 首先，检查 key 是否为 null，如果 key 是 null 值被存在 table0的位置，因为 null 的 hashcode 始终为 0 接下来，通过 key 的 hashCode()方法计算了这个 key 的 hash 值，这个 hash 值被用来计算存储 Entry

8、 对象的数组中的位置。JDK 的设计者假设会有一些人可能写出非常差的 hashCode()方法，会出现一些非常大或者非常小的 hash 值。为了解决这个问题，他们引入了另外一个 hash 函数，接受对象的 hashCode()，并转换到适合数组的容量大小。http:/接着是 indexFor(hash,table,length)方法，这个方法计算了 entry 对象存储的准确位置。接下来就是主要的部分，我们都知道两个不相等的对象可能拥有过相同的 hashCode 值，两个不同的对象是怎么存储在相同的位置叫做 bucket呢？答案是 LinkedList。如果你记得，Entry 类有一个 nex

9、t 变量，这个变量总是指向链中的下一个变量，这完全符合链表的特点。所以，在发生碰撞的时候，entry 对象会被以链表的形式存储起来，当一个 Entry 对象需要被存储的时候，hashmap 检查该位置是否已近有了一个 entry 对象，如果没有就存在那里，如果有了就检查她的 next 属性，如果是空，当前的 entry 对象就作为已经存储的 entry 对象的下一个节点，依次类推。如果我们给已经存在的 key 存入另一个 value 会怎么样的？逻辑上，旧的值将被替换掉。在检测了 Entry对象的存储位置后，hashmap 将会遍历那个位置的 entry 链表，对每一个 entry 调用 eq

10、uals 方法，这个链表中的所有对象都具有相同的 hashCode()而 equals 方法都不等。如果发现 equals 方法有相等的就执行替换。在这种方式下 HashMap 就能保证 key 的唯一性。get 方法的工作机制 现在我们已经了解了 HashMap 中存储键值对的机制。下一个问题是：怎样从一个 HashMap 中查询结果。其实逻辑跟 put 是一样的，如果传入的 key 有匹配就将该位置的 value 返回，如果没有就返回 null./* * Returns the value to which the specified key is mapped, * or code nu

11、ll if this map contains no mapping for the key. * * More formally, if this map contains a mapping from a key * code k to a value code v such that code (key=null ? k=null : * key.equals(k), then this method returns code v; otherwise * it returns code null. (There can be at most one such mapping.) * *

12、 A return value of code null does not necessarily * indicate that the map contains no mapping for the key; its also * possible that the map explicitly maps the key to code null. * The link #containsKey containsKey operation may be used to * distinguish these two cases. * * see #put(Object, Object) *

13、/ public V get(Object key) http:/if (key = null) return getForNullKey(); int hash = hash(key.hashCode(); for (Entry e = tableindexFor(hash, table.length); e != null; e = e.next) Object k; if (e.hash = hash return null; 上面的代码看起来跟 put()方法很像，除了 if (e.hash = hash & (k = e.key) = key | key.equals(k)。注意点

14、存储 Entry 对象的数据结构是一个叫做 Entry 类型的 table 数组。数组中一个特定的索引位置称为 bucket,因为它可以容纳一个 LinkedList 的第一个元素的对象。Key 对象的 hashCode()需要用来计算 Entry 对象的存储位置。Key 对象的 equals()方法需要用来维持 Map 中对象的唯一性。get()和 put()方法跟 Value 对象的 hashCode 和 equals 方法无关。null 的 hashCode 总是 0，这样的 Entry 对象总是被存储在数组的第一个位置成都 java 培训后 成都 java 就业怎么样？选择 达内 java 培训开启企业定制就业直通车，达内科技满足你高薪就业梦想！找 成都 IT 培训 100%推荐就业的 java 培训机构，请咨询达内在 成都 java 培训学校的老师！达内培训费用？达内好不好？达内怎么样？达内就业？这些问题都可以在达内的网站上找到答案。在达内科技学习可以申请先就业后付款的方式让刚毕业大学生免除在达内培训费用上的担忧。100%推荐就业更是解决学员培训后的就业问题！达内咨询官网：