数据结构 二叉树遍历 >HashMap、Hashtable实现原理(2)

3、remove(Object key)的实现

（1）HashMap的remove实现代码解析

代码分析很容易判断，这就是put的一个逆向过程，不过有一点是不可逆的，也就是二叉树不管后面remove到大小是多少（除非该数组项为null），都不会逆向转换为link的链表结构。

（2）Hashtable的remove实现代码解析

比较简单的直接计算获取数组项，然后进行链表遍历找到目标节点后进行节点删除操作

4、Iterator遍历实现

我们知道Map接口还有一个比较重要的功能就是iterator关于遍历的实现，主要有三种途径entrySet().iterator()、keySet().iterator()、values().iterator()的方式，下面我们来看下具体的实现

（1）HashMap的实现

entrySet部分代码

keySet部分代码

values部分代码

上面的三部分代码表明entrySet、keySet、values都返回了一个继承了AbstractCollection的抽象类（AbstractSet也是继承了AbstractCollection的抽象类）

iterator代码

获取iterator的过程都是通过共同的HashIterator.nextNode方法获取的，不同的是entrySet返回的是node节点，而另外的两个分别返回的是key以及value

HashInerator类

nextNode的操作基于对HashMap中数组链表的数据结构进行遍历实时获取的当前节点

（2）Hashtable的实现

entrySet部分代码实现

keySet部分代码实现

values部分代码实现

iterator代码

从Enumerator<>(type, true)可以看出这还是一种比较老的实现，目前还无法跟踪，大致的设计思路跟HashMap是一致的，因为Hashtable目前使用的并不多，多线程的一般使用ConcurrentHashMap（线程安全），在这里不深入研究，以后有机会找到资料再看。

小结：

通过以上各个常用功能的实现代码分析，我们对比了HashMap与HashTable得出如下结论

1、HashTable的对外相关的方法都有用synchronized进行修饰，是线程安全的，而HashMap不是，但是方法级别的synchronized必定导致HashTable在多线程运行时的性能问题。

2、HashMap的初始化数组大小是16，并且扩容是2n增长，Hashtable的初始化数组大小是11，扩容是2n+1的增长

3、key的hashCode方式两者也不一样，Hashtable直接去key的hashCode，而HashMap中对key进行了两次hash编码，这样做应该是在计算table数组下标位置的时候能够使存储位置分布的更均匀，可以提高HashMap的性能。

4、当一个数组项里面的链表数量超过8时，HashMap会将链表转换为二叉树的存储结构，但是Hashtable一致是链表结构

三、性能测试验证

不用质疑，在性能上面HashMap肯定比Hashtable要优越的多，不管是从数据存储结构或者是散列分布算法HashMap都有进行过优化，至于线程安全问题java api为我们提供了性能更优越的ConcurrentHashMap等类（后续也会对这些类进行分析），那么我们需要验证性能的方面就要从HashMap本身实现的功能使用上进行分析了，比如HashMap的遍历方式、初始容量以及阈值因子的设置对性能影响等。那么这块我们还是放在后面进行实例测试验证。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-74528-2.html