Java集合分析 (5)

从下面这句代码就能够看出来, 首先, 在HashMap中采取的存储方式是拉链法, 在之前已经提到过数据的存储方式, 但是当数据量越来越多, 无论如何hash值都会重复, 这个时候该怎么存储数据呢?

将数组的每一个元素都定义为一个链表, 将hash值相同的元素存入链表中即可, 存在负载因子的限制, 因此整个链表的长度也不会很长, 就保证了查找效率. 同时, 这里存储的时候, 并没有采取 hash%M 的方式, 而是采取了 table.length & hash 值来求取索引. 而这种方式的效率当然远远高于通过求余的方式, 然后插入对应的数组.

毕竟我们的根本性目的还是根据不同的散列值, 如果按照之前的方式来看, 高位不相关的这种现象很容易在这里出现. 所以事实上,其解决方式为通过HashCode() 的计算,保证散列分布的特性. 下面就是String的 hashCode() 实现方式. 并且也是大多实现方式的模板.

public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

table.length的初始值通过 resize() 给定. 让我们继续往下看.

if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

下面的处理方式需要重点关注, put delete get 是整个集合的核心.
在当前位置已经存在元素的情况下:

第一种处理方式是深入当前链表, 也就是桶, 如果找到key就更新 value值,此时并不会修改 modCount, 在目前提到过的容器中, 修改操作,都不会导致modCount值发生变化. 如果当前元素已经被转换成 TreeNode类型, 则采取TreeNode的方式进行添加(稍后再看), 否则的话向链表的末尾添加一个节点, 同时这个时候就需要提到另一个 属性:

static final int TREEIFY_THRESHOLD = 8;

这个是将链表转换为二叉树的阈值, 当hash值的取值, 也就是 hashCode()方法设置的不够合理时,就会出现这种情况, 在这样的情况下 随着链表越来越长就会严重影响性能. 因此在这里就做了这种处理方式, 将其转换为二叉树的实现方式, 兼顾了各种性能, 不得不说是一种很好的处理方式.

同时也不难想象, 在二叉树的实现过程中, 需要 key 实现 Comparable接口, 如果恰好没有实现这个接口, 而hashCode() 又实现的很差, 就不要怨天尤人啦, 我的Map为什么这么慢.

同时, 让我们来看看为什么. 当add element的时候, 都会导致 size++, 如果size到达阈值的时候, 还会扩充数组容量, 假设当前数组容量为100, 在小于阈值的情况下, 也就是最多填充了75个元素, 而此时, 这个节点的长度最大为7, 这意味着什么, 也就是可能 70个元素仅仅占据了数组的的10个空间, 剩余90个位置, 是没有值填充的. 大量的空间浪费, 同时时间性能上也大大降低, 也就不难理解为什么会 转换为 TreeNode进行处理.

else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

好, 再来看看在put方法中调用的几个非公开方法, 对这个函数的补充理解.
为什么要先看下面这个方法呢? 这个方法的调用时机是在 当当前元素非TreeNode的同时, 链表长度又已经到达八个时候转而将链表转换为树.

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

在这个方法里, 并非简简单单的直接转换, 又进行了一次判定, 数组长度是否小于 MIN_TREEIFY_CAPACITY,64, 不难理解,如果数组长度本身就过小, 这件事发生的概率可能就会提高, 至于提高多少, 就不在我目前的考虑范围内了.将数组再度扩容.