《java的案例7》由会员分享，可在线阅读，更多相关《java的案例7（6页珍藏版）》请在金锄头文库上搜索。
1、javajava 的案例的案例 7 7JDK 中 HashMap 的分析 2009-04-11 19:00:58| 分类： 面试旅程 | 标签： |字号大中小 订阅 .JDK 中 HashMap 的分析关键字: hashmap 分析 J2SDK 中提供了大量的通用类，供我们在开发的时候使用。其中，HashMap 类是我们经常使用的。下面简单的分析了 HashMap 类的一些主要代码。 概述 HashMap 类位于 java.util 包中。主要作用是提供了一个 Map 的实现，可以比较方便的进行 关键字(key) 值(value)的存取。其主要方法为： public Object put(Ob
2、ject key, Object value) 加入一个对象。 public Object get(Object key) 获得一个对象。如果没找到对应于 key 的对象，返回 null. 下面着重分析这两个方法。 put 方法 put 方法的作用是将一个对象(value)加入到 map 中，它的 key 为(key)。如果 key 重复了，将替换掉旧的值，并将旧值返回。如果key 没有重复，将新的值插入。该部分代码如下（有删节）： Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length
3、); for (Entry e = tablei; e != null; e = e.next) if (e.hash = hash e.value = value; e.recordAccess(this); return oldValue; addEntry(hash, k, value, i); return null;首先，程序执行了 maskNull 函数。该函数很简单，仅仅判断如果 key 非空，直接返回，否则返回一个 new Object(). 接下来，使用 HashMap 类中函数 hash(k)来计算 key 的 hash 值（这应该就是这个类被命名为 HashMap 的原因
4、） 。比较有意思的是，hash函数中，并没有直接返回 k.hashCode()，而是在 hashCode()之上进行了额外的计算。按照该函数的 javadoc，这是为了抵御“某些不良设计的 hashCode 函数“。 再往下，是计算 hash 值在列表中的起始位置。table 就是实际保存值的列表，indexFor 这个函数返回的是 hash 值的在 table 中的位置。具体含义为，一些 key 的 hash 值很可能是相同的（冲突） ，这些 key 冲突的 key-value 所在的项组成一个链表，indexFor 函数返回的就是这个链表的首项。而这个 indexFor 函数极其简单: s
5、tatic int indexFor(int h, int length) return h 很明显，因为传入的 hash 值(h)可能为很大的数，所以通过与table 的长度做 AND 运算，保证得到的位置在0, table.length-1的区间内。 这就带来一个问题:如果 table 的长度增加了，那么 indexFor 函数返回的位置可能就变化了，这就产生了错误。实际上，HashMap 是能够避免这个问题的，后文分析。 继续查看 put 函数的代码。在得到了起始的位置之后，是一个while 循环。该循环很简单，依次遍历相同 hash 值的 Entry，如果key 也相等，那么将 val
6、ue 赋入，同时返回旧的值。否则的话，while 执行完毕，还没有找到 key，那么，执行 addEntry 函数，将key-value 加入到 table 中。在加入后，进行判断: if (size+ = threshold) resize(2 * table.length);即如果新的容量大于限制值，那么会进行容量扩充的操作，也就是扩充 table 的大小。新容量是旧容量的 2 倍。在 resize 函数中，要生成新的 table 并设置成新的容量，同时，进行比较重要的操作，即将旧的 table 中的内容拷贝到新的table 中去。在拷贝的过程中，Entry 在新的 table 中的位置是
7、经过重新计算的，所以上文提到的问题不会出现。 get 方法 get 方法相对 put 方法很简单，代码如下： public Object get(Object key) Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e = tablei; while (true) if (e = null) return e; if (e.hash = hash e = e.next; 首先计算 hash 值，然后调用 indexFor 函数得到起始的位置，获取该位置上的项，改
8、项即为具有相同 hash 值的链表的首项。最后使用while 循环来遍历这个链表。在循环中，逐个比较如果 key 也相等了，说明找到了，返回，否则继续找下去。如果没有 hash 值相等的项了，可以判断为没找到，返回空。 table 详细内容 见下图. 每个 key-value 对放在 Entry 对象中。由 key 计算出的 hash 值相等的 Entry 组成一个链表，链表的元素之间使用 Entry.next 相连，链表的首位置由 indexOf 计算得到。遍历这个链表即可以得到某个key 可能存在的 Entry，HashMap 也通过这种方式来解决冲突。 一些值得注意的问题 在上文中，我们
9、注意到，如果 table 容量大于某个限制，那么将要进行扩充。扩充的操作，实际上是新建 table，进行拷贝，并且重建 Entry 链表的过程。这个过程自然是极其耗时的，我们也应该尽量避免这个操作。避免的方法也很简单，就是初始化 HashMap 的时候，指定一个比较大的容量即可（默认是 16）. HashMap 提供了构造函数 public HashMap(int initialCapacity) 来解决这个问题。 可以看出，无论是在添加的 put 函数，和获取的 get 函数，均要遍历冲突的链表，也就是说，如果在 HashMap 中存在大量的冲突（因为某种原因，key 计算出来的 hash 值重复） ，那么，HashMap 将近似退化为链表的线性查找。这就会比较大的影响性能。这就要求我们仔细设计 key 对象的 hashCode()函数，尽量少的减少不同的 key 得多相同的 hash 值的情况（自然，完全不同的 hashCode 的值是不可能的）
