data structure and algorithm
我希望每个人对算法和数据结构是什么有一个深刻的认识，所以我们会在每一篇的文章的开始给你灌输下面的这些知识点：
1、数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以让你写出更漂亮更高效的代码（时间复杂度和空间复杂度）；
2、算法其实就是解决我们生活中遇到的问题的计算方法；
3、程序=数据结构+算法；要学好数据结构和算法就要在日常生活中把遇到的问题尝试用程序去解决
4、数据结构是实现一个算法的基础，所以想要学好算法，需要把数据结构学到位；
5、数据结构分为线性结构和非线性结构；线性结构的特点是数据元素之间存在一对一的线性关系；
6、线性结构又有顺序存储结构和链式存储结构两种的存储结构，顺序存储结构中存储元素是连续的，而链式存储结构中存储元素不一定是连续的；
哈希
散列(hashing)是电脑科学中一种低资料的处理方法，通过某种特定的函数/算法(称为散列函数/算法)将要检索的项与用来检索的索引(称为散列或者散列值)关联起来，生成一种便于搜索的数据结构(称为散列表).
哈希函数
所有的哈希函数都具有的基本特征：如果两个散列值是不相同的(根据同一函数)，那么这两个散列值的原始输入也是不相同的、这一特性是散列函数具有确定性的结果。
哈希表
散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的底层数据结构可以是数组+链表和数组+二叉树；
构造散列函数的方法
1、直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）。
2、数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
3、平方取中法：取keyword平方后的中间几位作为散列地址。
4、折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。
5、随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。
6、除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，若p选的不好，容易产生同义词。
冲突和处理冲突的方法
对于不同的关键字可能得到同一散列地址，即k1!=k2，而f(k1)=f(k2)，这种现象称为冲突。
常用的处理冲突的方法有：
1、开放地址法：在产生冲突之后去寻找下一个空闲的空间。
函数定义为：hash=(hash(key)+di)mod m i=1,2,….k(k<=m-1)
其中，hash(key)是哈希函数，di是增量序列，i为已冲突的次数。
开放定址法里面根据增量序列策略不同分为线性探测法、平方探测法和伪随机探测法。
线性探测：di=1,2,3,…..(m-1);
平方探测：di=+-1^2,+-2^2,……+-k^2(k<=m/2);
伪随机探测：di是一个随机数序列；
2、链表法(拉链法)：当散列到同一位置时，不是继续往下探测，而是在这个位置添加一个链表，然后这些元素都放到这一链表上；
3、再散列：发生冲突之后，再次使用这一散列函数对上一次散列的散列值进行再次的散列，直到冲突不再发生；
4、建立公共溢出区：将哈希表分为基本表和溢出表两个部分，凡是和基本表发生冲突的元素，一律填入溢出表；
重哈希(rehash)
哈希表还有一个重要的属性：负载因子(load factor)，它用来衡量哈希表的空/满程度，一定程度上也可以体现查询的效率，计算公式为：负载因子=总键值对数/箱子个数；负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是1，或者0.75等)时，哈希表将自动扩容；
哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使key的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
rehash的过程非常地耗性能，所以一般建议设置较大的初始化容量，防止rehash，但也不能设置过大，初始化容量过大会造成空间的浪费。
哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有key的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能；
基于以上我们可以做出以下总结：
1、如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
2、如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低；
字典
这里的字典也称作“映射”，是一种数据结构，跟set集合很相似的一种数据结构，可以用来存储无序不重复的数据，不同的地方是集合以[value,value]的形式存储，而字典则是以[key,value]或者{key,value}的形式存储；字典的一种实现方式是使用散列表，另外一种常见方式是红黑树；
HashMap
我们本次源码阅读是观察JDK1.8版本的源码，因为JDK1.8之后HashMap有一些新的强大的、精妙的东西；
我们本次源码阅读主要解决下面的几个知识带你：resize、处理冲突的设计和jdk1.8后的红黑树和hash;
首先我们先来了解一下HashMap底层的数据结构，它底层依赖的是数组+链表+红黑树,默认的数组大小为16（一般设置为2的多次方，这样的设计巧妙地利用了二进制的运算特性，后面我们会详细解释其巧妙之处）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
首先因为数组需要存放所有的key、value,所有需要把key、value包装成一个类，结合后面的链表和红黑树结构，最终封装成上述的这么一个节点类，然后初始化工作就会创建对应的Node<K,V>[]数组：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
通过阅读上述的源码大家可能会疑惑，不是进行初始化工作吗，为什么是调用resize方法，resize方法里面的这么一堆代码究竟有什么作用，并且HashMap是在什么时候进行初始化的工作的呢，我们进行阅读源码：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
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;
}
我们首先想的是HashMap什么时候之前需要执行初始化，按这样子的想法我们自然会想到当需要添加元素之前就需要执行初始化，HashMap的添加元素的方法为Put方法，通过查看put方法的源码已经后续的调用，我们最终在putval这个方法中发现了resize方法的影子，而且还出现了两次；
第一次出现的时候我们发现其执行条件是table==null,通过查看成员变量的相关定义我们知道table就是用来存放节点的数组，所以我们判断这个resize方法的作用包括进行数组的初始化；再查看第二个resize方法，其执行的条件是++size>threshold，这个threshold的大小在数组初始化的时候就进行了赋值，我们查看resize方法的源码可以发现初始化的相关代码里面，有newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);这两行代码,通过查看成员变量的相关定义我们知道这两个变量分别是赋值默认初始数组大小为16，并且其在定义大小的时候不是直接赋值16而是赋值1»4，因为位运算的效率更高；以及通过负载因子计算数组容量的警戒值。通过查看成员变量的相关定义我们知道size是记录当前数组元素的个数，threshoold是记录一个数组容量的警戒值，所以我们判定这个resize的作用是进行扩容；扩容的相关操作如下：else if ((newCap = oldCap « 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr « 1; «1的作用是扩容一倍。通过上述分析我们成功弄清楚resize在hashmap中的作用；
我们在观察put方法的源码的时候，我们发现里面有一个参数调用了hash方法，我们去查看hash方法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们可以知道这个hash方法是通过key进行相关哈希函数的计算，然后通过计算得到的hash值进行寻址工作，但是这可能存在数组下标越界的情况，但HashMap有相关的巧妙处理来解决越界的问题；
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
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 {
我们观察putval方法中有这么一个数据处理，当我们添加元素的时候，其添加的下标是通过p = tab[i = (n - 1) & hash]) == null ====》 (n-1)&hash来避免下标越界的，我们前面有提到为什么默认的数组大小和扩容后的数组大小为2的次方，我们拿默认初始大小16来举例，n-1==>16-1=15，其对应的二进制位为01111，然后比如我们需要添加一个hash值为18的节点，这时候如果不进行处理就会出现下标越界，但通过处理之后是这样子的，18对应的二进制为010010,010010&001111之后的结果为000010==>2，我们知道与运算必须都为1的时候才等于1，所以任何数与01111相与之后的结果最大就是为01111==》15。这就是HashMap在设计上的巧妙之处；另外补充一点将数组大小设置为2的次方的原因，还是拿16举例，在最终计算hash地址的时候，任何数的二进制数的后四位与其进行与运算之后的结果还是本身，这也就保证了最终hash的均匀分布
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
通过这段代码我们知道HashMap处理冲突的方式是如果数组没有存放东西就存放到数组的对应位置上，如果位置上已经存在元素，则沿着该元素添加到对应的链表中，当链表达到一定的长度之后，就会转换成红黑树，我们知道链表达到一定长度之后就会影响查询的效率，而红黑树可以一层存放多个元素，大大缩短了链表的长度。
再谈HashCode的重要性:
前面讲到了，HashMap中对Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那么为什么要防止糟糕的HashCode？
糟糕的HashCode意味着的是Hash冲突，即多个不同的Key可能得到的是同一个HashCode，糟糕的Hash算法意味着的就是Hash冲突的概率增大，这意味着HashMap的性能将下降，表现在两方面：
1、有10个Key，可能6个Key的HashCode都相同，另外四个Key所在的Entry均匀分布在table的位置上，而某一个位置上却连接了6个Entry。这就失去了HashMap的意义，HashMap这种数据结构性高性能的前提是，Entry均匀地分布在table位置上，但现在确是1 1 1 1 6的分布。所以，我们要求HashCode有很强的随机性，这样就尽可能地可以保证了Entry分布的随机性，提升了HashMap的效率。
2、HashMap在一个某个table位置上遍历链表的时候的代码：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
看到，由于采用了”&&”运算符，因此先比较HashCode，HashCode都不相同就直接pass了，不会再进行equals比较了。HashCode因为是int值，比较速度非常快，而equals方法往往会对比一系列的内容，速度会慢一些。Hash冲突的概率大，意味着equals比较的次数势必增多，必然降低了HashMap的效率了。
另外载荷因子的设计也会影响HashMap的性能，载荷因子被设计为0.75，超过0.8，CPU的cache missing会急剧上升。这是因为如果没有控制好载荷因子的大小，当容器里的元素数量很大的时候，就增加了发生Hash冲突的机会，就需要进行多次的重新定位，这中间会不断地占用缓存，当缓存数量达到峰值就会自动删除原先的一部分缓存信息，从而可能造成cache missing，需要耗费时间和性能再次去加载信息
一个非常细节的地方：
transient Entry[] table;
看到table用了transient修饰，也就是说table里面的内容全都不会被序列化，不知道大家有没有想过这么写的原因？
在我看来，这么写是非常必要的。因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的：
public native int hashCode();
这意味着的是：HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。再进一步说得明白些就是，可能同一个Key在虚拟机A上的HashCode=1，在虚拟机B上的HashCode=2，在虚拟机C上的HashCode=3。
这就有问题了，Java自诞生以来，就以跨平台性作为最大卖点，好了，如果table不被transient修饰，在虚拟机A上可以用的程序到虚拟机B上可以用的程序就不能用了，失去了跨平台性，因为：
1、Key在虚拟机A上的HashCode=100，连在table[4]上
2、Key在虚拟机B上的HashCode=101，这样，就去table[5]上找Key，明显找不到
整个代码就出问题了。因此，为了避免这一点，Java采取了重写自己序列化table的方法，在writeObject选择将key和value追加到序列化的文件最后面：
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator<Map.Entry<K,V>> i =
(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
而在readObject的时候重构HashMap数据结构：
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
// set hashSeed (can only happen after VM boot)
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
sun.misc.Hashing.randomHashSeed(this));
// Read in number of buckets and allocate the bucket array;
s.readInt(); // ignored
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
int initialCapacity = (int) Math.min(
// capacity chosen by number of mappings
// and desired load (if >= 0.25)
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
int capacity = 1;
// find smallest power of two which holds all mappings
while (capacity < initialCapacity) {
capacity <<= 1;
}
table = new Entry[capacity];
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i<mappings; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
JDK1.7之前一直存在HashMap的死循环问题，原因就是因为HashMap是线程不安全的，而在JDK1.8之后做出了一些调整，通过定义两个指针来保证扩容前后的顺序从而避免死循环，由于扩容是按两倍进行扩，即 N 扩为 N + N，因此就会存在低位部分 0 - (N-1)，以及高位部分 N - (2N-1)， 所以这里分为 loHead (low Head) 和 hiHead (high head)。通过对JDK1.7源码的分析，不难发现循环的产生是因为新链表的顺序跟旧的链表是完全相反的，所以只要保证建新链时还是按照原来的顺序的话就不会产生循环。JDK8是用 head 和 tail 来保证链表的顺序和之前一样，这样就不会产生循环引用。但HashMap的线程不安全仍然可能导致数据丢失，所以在多线程环境下还是不建议使用HashMap，可以使用ConcurrentHashMap.
HashTable
hashtable在JDK1.8依旧是采用数组+链表结构实现。
public Hashtable() {
this(11, 0.75f);
}
Hasttable的默认容量(数组大小)为11，默认的负载因子为0.75。
注意：hashtable中的数组容量capacity没有限制为2的n次方，但一般会保证是奇数，从后面hashtable的扩容可以体现。
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;
}
hashtable之所以是线程安全的，原因为在put和get方法上使用synchronized关键字进行修饰。
限制了value不能为null。
由于直接使用key.hashcode(),而没有向hashmap一样先判断key是否为null,所以key为null时，调用key.hashcode()会出错，所以hashtable中key也不能为null。
hashtable中对hash值进行寻址的方法为hash%数组长度(与hashmap不同，所以不要求数组长度必须为2的n次方)。
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
如果加入新节点后，hashtable中元素的个数超过了阈值threshold，则利用rehash()对数组进行扩容。
e=table[index]，并将新节点加在了e节点的1前面，最后table[index]=e。相当于把把新节点放在table[index]位置，即整个链表的首部。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
扩容策略不同,HashMap扩容2倍，Hashtable扩容2倍+1（为了保证奇数）
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
hashtable之所以是线程安全的，原因为在put和get方法上使用synchronized关键字进行修饰。
进行hash值的寻址，找到在table数组中的位置index.
遍历table[index]链表，找到key值相同的节点的value返回，注意同样在该过程中使用到了key的equal方法，所以key被应用于hashtable时不仅要实现hashcode方法还有实现equal方法。
HashMap、HashTable和Dictionary的总结
HashMap和HashTable的区别：
1、Hashtable是线程安全的，Hashtable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是线程非安全的。
2、Hashtable不允许空的key和value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制。
3、HashMap和HashTable的rehash算法不同。
4、hashmap中出现hash冲突时，如果链表节点数小于8时是将新元素加入到链表的末尾，而hashtable中出现hash冲突时采用的是将新元素加入到链表的开头。
5、起始容量不同、继承不同、默认初始大小不同、数组容量要求不同、寻址方式不同
HashTable和Dictionary的区别：
1、一个微妙但重要的区别是Hashtable支持多个阅读器线程和一个写入器线程，而Dictionary提供线程安全性。
2、dictionary是hashtable的一种泛型的体现。
3、dictionary在算法上做了一点优化，比hashtable快。