在这里提供了一个公共的抽象内部类, 去实现 Iterable接口的方法, 但本身并不 implements Iterable, 通过这个内部类的 nextNode 遍历整个 table的所有node.
if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); }而其中这段代码是核心代码, 判断并赋值当前节点的next节点是否为空, 为空进入下一个index节点. 倒不是说实现非常困难, 而是这段代码相当简洁.
如果要遍历 key, value, node 这三者, 事实上都是通过这个 HashIterator实现的.
在我原来的理解中, KeySet本身应该是遍历Map然后将所有的 key值放入一个Set中. 我们遍历也是遍历这个Set.
而事实上, 代码巧妙的多:
public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } final class KeySet extends AbstractSet<K> { public final Iterator<K> iterator() { return new KeyIterator(); } ...通过这种方式就能获取到对应的集合.
forEach()
public void forEach(BiConsumer<? super K, ? super V> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.key, e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } void accept(T t, U u);当然, 其遍历方式并没有太大区别, 有趣的是 Java1.8以后所带来的新特性, lamda函数式.
map.forEach((k, v) { System.out.println("key : " + k + "; value : " + v) })
总结
漫长的HashMap之旅总算结束:
hashCode() 的实现方式与 map的性能息息相关, 因此最好能够在实现hashCode() 的时候, 自主测试一下, 是否能够达到均匀分布.
hashCode()的实现要点之一则是务必要使用到 对象中的每一个区分属性.
equals()方法也要一并实现, 在 keys 判断两个键是否相等时, 需要用到equals()方法.
如果可以的话, 最好同时实现comparable接口, 这样当你的 hashCode()实现比较糟糕时, 不至于使得性能一塌糊涂.
在使用大多数方法的时候, 最好谨慎小心的使用, 因为有很多方法的性能并不是那么高, 但是不得不体现出来. 比如 containsValue() 方法.
补充
在HashMap的实现中, 采取的是拉链法实现的散列表, 这里还有另一种方式, 叫做 线性探测法:
在拉链法中, 恰如其名, 数组中的每一个元素都是一个桶, 用来存储 hash值冲突的元素. 通过链表的存储方式来进行存储.
但是存在一点, 我们之前看过 Node 的结构, 包含有key value next hash 四个属性, 又由于Node本身就要占据一个开销, 所以事实上是加大了开销, 这当然不是太大的缺点. 但同时又由于 糟糕的 hashCode() 计算方法会导致速度变慢也是不可避免的问题.
线性探测法, 空间开销上稍好一些, 在这里最好需要两个数组, 一个存储 values 一个存储 keys, 那他怎么解决冲突呢?
答案是: 当当前index已经存在元素, 就向下移动一格看下一个元素是否为空, 同时对比 key是否 equals(). 如果都不是, 则再向下移动一格位置, 直到为空, 或找到 key相同的元素. 查找的时候遵循同样的原则.
对于线性探测法而言, 除了hashCode()的实现以外, 数组的阈值也是尤为重要的一点, 如果设置不合理, 可以想象, 数组已经满了 会陷入无限循环中.
HashSetHashSet是要比HashMap简单许多的, 但又由于它的底层就是HashMap, 因此放到这里. 事实上, 在我看源码之前, 并不知道HashSet的底层就是 Map.不多说, 继续看吧.
Set s = Collections.synchronizedSet(new HashSet(...));
构造方法
public HashSet() { map = new HashMap<>(); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }在这里又会有一个新发现: LinkedHashMap, 之后再来大概看一下.
add()
public boolean add(E e) { return map.put(e, PRESENT)==null; } private static final Object PRESENT = new Object();可以看到在存入的时候, 会同步存入一个新创建的空对象.直接引用HashMap对应的存入方法, 如果不在乎内存的话, 一个对象的开销并不是太大的影响.
当然更优化的方式, 是自己实现一个HashSet.
iterator()
public Iterator<E> iterator() { return map.keySet().iterator(); }
总结
在看过HashMap 的实现方式之后, HashSet实在是一件极为简单的事, 我也就不一一列举, 没有必要.
在HashMap中的注意事项, 在这里同样通用, 不再赘述.
TreeMap
注意事项
TreeMap是基于红黑树实现的集合. 因此同样的需要实现 Comparable接口, 或在创建Map的时候传递 Comparator比较器.
为线程不安全的, 若果要使用的话:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));通常来说, equals方法和 比较方法的一致性需要多多注意, equals()返回为true的, compareTo一般来说相等, 当然也有其他情况存在.
属性
private final Comparator<? super K> comparator; private transient Entry<K,V> root; private transient int size = 0; private transient int modCount = 0;从这里就不难看出来, TreeMap的底层是红黑树, 红黑树的节点数据类型为:
Entry
构造器
public TreeMap() { comparator = null; }在这个构造器中, 将comparator赋值为null, 因此要求key必须实现Comparable接口.
public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }