HashMap：
- 由数组+链表组成的，基于哈希表的Map实现，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。
- 不是线程安全的，HashMap可以接受为null的键(key)和值(value)。
- HashMap重新计算hash值
Hashtable：
- Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。
- Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。
- HashTable直接使用对象的hashCode。
HashMap是Hashtable的轻量级实现（非线程安全的实现）都完成了Map接口，主要区别在于能否键对值<K,V>能为null。
同时其内部方法有区别：HashMap中将Hashtable的contains方法去掉了，改为containsvalue和containsKey,避免混淆。Hashtable继承于Dictionary类，而HashMap是java 1.2 引进的Map接口一个实现。HashMap就效率而言高于Hashtable。
TreeMap则是基于红黑树的一种提供顺序访问的Map，它的get、put、remove之类的操作都是o(logn)的时间复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断。
区别
1、继承和实现方式不同
- HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
- Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
2、线程安全不同
- Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。
- HashMap的函数则是非同步的，它不是线程安全的。(所以hashMap的效率也会高于Hashtable)
3、对null值的处理不同
- HashMap的key、value都可以为null。
- Hashtable的key、value都不可以为null。
4、支持的遍历种类不同
- HashMap只支持Iterator(迭代器)遍历。
- Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历
5、通过Iterator迭代器遍历时，遍历的顺序不同
- HashMap是“从前向后”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。
- Hashtabl是“从后往前”的遍历数组；再对数组具体某一项对应的链表，从表头开始进行遍历。
6、容量的初始值 和 增加方式都不一样
- HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。
- Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。
7、添加key-value时的hash值算法不同
- HashMap添加元素时，是使用自定义的哈希算法。
- Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。
hashMap：自定义的哈希算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashTable：直接采用的key的hashCode()
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
